dawnchengx

dawnchengx 查看完整档案

填写现居城市  |  填写毕业院校  |  填写所在公司/组织填写个人主网站
编辑
_ | |__ _ _ __ _ | '_ \| | | |/ _` | | |_) | |_| | (_| | |_.__/ \__,_|\__, | |___/ 个人简介什么都没有

个人动态

dawnchengx 发布了文章 · 2018-12-27

如何选择最合适的排序算法?

1.排序算法分类

1.1 比较排序:
交换排序:基础冒泡排序、优化冒泡排序、基础快速排序、递归版优化快速排序、循环版优化快速排序
插入排序:基础插入排序、希尔优化插入排序
选择排序:选择排序、二叉堆排序、多叉堆排序
归并排序:归并排序
1.2 非比较排序:
计数排序
桶排序
基数排序

2.基础概念解读

2.1 时间复杂度
随着排序数据总量n的变大,排序总耗时的上升情况。有五个符号来表示不同的意思:
O(n^2) 大O 表示该排序算法增量情况 <= n^2
o(n^2) 小o 表示该排序算法增量情况 < n^2
θ(n^2) 希腊字母theta 表示该排序算法增量情况 == n^2
ω(n^2) 希腊字母小欧米伽 表示该排序算法增量情况 > n^2
Ω(n^2) 希腊字母大欧米伽 表示该排序算法增量情况 >= n^2

2.2 稳定性
如果a=b,排序前a在b之前,排序后a还在b之前,则稳定
如果a=b,排序前a在b之前,排序后a在b之后,则不稳定

2.3 逆序对
比如{2, 4, 3, 1}这样一个数列,就有{2, 1},{4, 3},{4, 1},{3, 1}等逆序对,数量为4

3.排序算法对比

图片描述

4.代码实现(Java)

https://github.com/dawnchengx...

5.伪代码实现

5.1 基础冒泡排序

BasicBubbleSort(A)
    for i=1 to A.length-1
        for j=A.length down to i + 1
            if A[j] < A[j-1]
                exchange A[j] with A[j-1]

5.2 优化冒泡排序

OptimizeBubbleSort(A)
    for i=1 to A.length-1
        didSwap = false;
        for j=A.length down to i + 1
            if A[j] < A[j-1]
                exchange A[j] with A[j-1]
                didExchange = true
        if didExchange == true
            return

5.3 基础快速排序

BasicQuickSort(A, p, r)
    if p < r
        q = BasicPartition(A, p, r)
        BasicQuickSort(A, p, q-1)
        BasicQuickSort(A, q+1, r)
        
BasicPartition(A, p, r)
    x = A[r]
    i = p-1
    for j=p to r-1
        if A[j] <= x
            i = i + 1
            exchange A[i] with A[j]
    exchange A[i+1] with A[r]
    return i + 1

5.4 递归优化快速排序

RecuOptimizeQuickSort(A, sort, end)
    if start < end
        mid = RecuOptimizePartition(A, start, end)
        RecuOptimizeQuickSort(A, start, mid-1)
        RecuOptimizeQuickSort(A, start+1, end)
RecuOptimizePartition(A, start, end)
    生成介于start和end之间的三个不重复的随机数r1,r2,r3
    取A[r1],A[r2],A[r3]这三个数的中位数,并将该中位数的下标赋值给r0
    x = A[r0]
    i = start - 1
    for j = start to end - 1
        if A[j] <= x
            i = i + 1
            exchange A[i] with A[j]
    exchange A[i+1] with A[end]
    return i+1

5.5 循环优化快速排序

LoopOptimizeQuickSort(A)
    stack = []
    start = 0
    end = A.length - 1
    stack.push(start)
    stack.push(end)
    while stack.isNotEmpty()
        end = stack.pop()
        start = stack.pop()
        if start < end
            base = LoopOptimizePartition(A, start, end)
            // 右半边
            stack.push(base+1)
            stack.push(end)
            // 左半边
            stack.push(start)
            stack.push(base-1)
LoopOptimizePartition(A, start, end)
    生成介于start和end之间的三个不重复的随机数r1,r2,r3
    取A[r1],A[r2],A[r3]这三个数的中位数,并将该中位数的下标赋值给r0
    x = A[r0]
    i = start - 1
    for j = start to end - 1
        if A[j] <= x
            i = i + 1
            exchange A[i] with A[j]
    exchange A[i+1] with A[end]
    return i+1

5.6 基础插入排序

InsertionSort(A)
    for j=2 to A.length
        key = A[j]
        i = j - 1
        while i > 0 and A[i] > key
            A[i+1] = A[i]
            i = i - 1
        A[i+1] = key

5.7 希尔优化插入排序

ShellInsertionSort(A)
    increment = A.length
    do {
        increment = increment/3 + 1
        for j = increment to A.length
            key = A[j]
            i = j - increment
            while 0 <= i and A[i] > key
                A[i+increment] = A[i]
                i = i - increment
            A[i+increment] = key
    }while(1 < increment);

5.8 选择排序

SelectionSort(A)
    for i=1 to n-1
        min = i
        for j=i+1 to n
            if A[min] > A[j]
                min = j
        exchange A[min] with A[i]

5.9 二叉堆排序

HeapSort(A)
    BuildMaxHeap(A)
    for i = A.length downto 2
        exchange A[1] with A[i]
        A.heap-size = A.heap-size - 1
        MaxHeapify(A, 1)
BuildMaxHeap(A)
    A.heap-size = A.length
    for i = A.length/2 downto 1
        MaxHeapify(A, i)
MaxHeapify(A, i)
    l = LEFT(i)
    r = RIGHT(i)
    if l <= a.heap-size and A[l] > A[i]
        largest = l
    else largest = i
    if r <= A.heap-size and A[r] > A[largest]
        largest = r
    if largest != i
        exchange A[i] with A[largest]
        MaxHeapify(A, largest)
LEFT(i)
    return 2i
RIGHT(i)
    return 2i+1

5.10 多叉堆排序
5.11 归并排序

MergeSort(A, p, r)
    if p < r
        q = (p+r)/2 (向下取整)
        MergeSort(A, p, q)
        MergeSort(A, q+1, r)
        Merge(A, p, q, r)
Merge(A, p, q, r)
    n1 = q - p + 1
    n2 = r - q
    let L[1..n1+1] and R[1..n2 + 1] be new arrays
    for i = 1 to n1
        L[i] = A[p + i - 1]
    for j = 1 to n2
        R[j] = A[q + j]
    L[n1+1] = 正无穷大
    R[n2+1] = 正无穷大
    i = 1
    j = 1
    for k = p to r
        if L[i] <= R[j]
            A[k] = L[i]
            i = i + 1
        else
            A[k] = R[j]
            j = j + 1

5.12 计数排序

CountingSort(A, B, k)
    let C[0...k] be a new array
    for i = 0 to k
        C[i] = 0
    for j = 1 to A.length
        C[A[j]] = C[A[j]] + 1
    for i = 1 to k
        C[i] = C[i] + C[i-1]
    for j = A.length downto 1
        B[C[A[j]]] = A[j]
        C[A[j]] = C[A[j]] - 1        

5.13 基数排序
https://www.jianshu.com/p/68b...
5.14 桶排序

https://www.cnblogs.com/zer0Black/p/6169858.html
BucketSort(A)
    n = A.length
    let B[0.. n-1] be a new array
    for i = 0 to n-1
        make B[i] an empty list
    for i = 1 to n
        insert A[i] into list B[<nA[i]向下取整>]
    for i = 0 to n-1
        sort list B[i] with insertion sort
    concatenate the lists B[0],B[1],...,B[n-1] together in order
查看原文

赞 1 收藏 1 评论 0

dawnchengx 发布了文章 · 2018-12-17

Redis使用手册 - 基础篇

一、Redis使用禁忌

Redis作为常驻内存的存储器,相对于常驻硬盘MySQL多了很多隐藏的禁忌,一不小心就会影响线上业务。
所以本手册会在最前面把所有的Redis使用禁忌列举出来。(禁忌是相对,特殊情况也可以打破禁忌)

1.阻塞

为什么会阻塞:

Redis作为高性能内存服务器在处理命令时为何使用单线程呢?
当单个线程任务运行时间过长时,我们常常用多线程技术,让其他线程处理其他的任务,从而不让其他任务阻塞等待,更快的跑完所有任务。
但是多线程会增加程序的复杂性。
如果单个线程任务运行时间很短,那么单线程也能很快的跑完所有任务。
由于Redis的数据存储在内存中,具有非常好的IO性能,通常情况下处理速度也很快,所以用单线程也具有很高的性能。
与此同时,Redis通过多路复用技术(epoll)尽可能多的接收请求命令,让所有命令排队一个个进入处理程序,进行处理。
也就是说Redis接收客户端请求如下图所示:
Redis服务端命令运行机制
正因为Redis的运行机制,所以当有命令运行时间很长时就会阻塞队列中的其他命令,照成其他命令一直等待。严重影响公司业务正常运行。

阻塞的危害:

a. 导致主从切换

那么哪些命令会导致Redis阻塞呢?

a. flushallflushdb

flushall会清空所有db的数据
flushdb会清空当前db的所有数据

害怕生产环境被经验不足的工程师误操作怎么办?
① 使用 rename-command将flushall和flushdb改为一个随机字符串
万一误操作了如何恢复呢?
① 如果AOF还没有重写,则在AOF中删除flushall或者flushdb
然后重新载入AOF即可
② 如果RDB还没有生成,马上备份RDB,然后载入RDB即可

b. keys

keys会一次性获取所有的Redis key,如果一个Redis实例中的key很多就会执行很久,阻塞其他命令执行。
所以生产环境禁止使用keys

如果需要去遍历key该怎么办呢?
① 用scan去迭代遍历,比如每次取50个
害怕生产环境被经验不足的工程师误操作怎么办?
① 使用 rename-command将keys改为一个随机字符串

c. hgetall
当一个hash很大时,hgetall会获取所有的field和value,照成阻塞

如果需要去遍历hash该怎么办呢?
① 用hscan去迭代遍历,比如每次取50个

d. del
当删除一个很大的hash、list、set、zset时,因为其中存储的内容需要循环释放,所以会阻塞

4.x版本可以使用unlink开启新线程异步删除,但是要注意复制线程所带来的内存开销和cpu开销,在内存和cpu有足够剩余空间时才能使用
最稳的方式还是下面几个
hash,可以使用hscan逐个删除
list,可以一个一个pop,或者使用LTRIM一次删除较少数据
set, 可以使用sscan逐个删除
zset,可以使用zscan逐个删除

e. sort

还有哪些原因会阻塞Redis线程呢
a. cpu饱和
cpu跑满,命令无法继续处理
b. 持久化阻塞
RDB和AOF重写时,需要fork当前线程,如果fork操作时间很长,就会阻塞主线程
AOF做fsync时,如果主线程发现距离上一次fsync成功超过2秒,为了数据安全性它会阻塞知道后台线程执行fsync操作完成。

查看原文

赞 0 收藏 0 评论 0

dawnchengx 关注了专栏 · 2018-12-09

腾讯云技术社区

最专业的云解读社区

关注 11495

dawnchengx 关注了专栏 · 2018-12-09

前端修炼之路

每天多学一点,幸福多攒一点。

关注 535

dawnchengx 关注了专栏 · 2018-12-09

ES2049 Studio

阿里巴巴 - CRO 技术部 - 体验技术

关注 2266

dawnchengx 关注了专栏 · 2018-12-09

PHP安全实践

分享正在普及的安全知识

关注 2367

dawnchengx 关注了用户 · 2018-12-09

命名最头痛 @george_es

a == b ? a : b

关注 653

dawnchengx 关注了专栏 · 2018-12-09

树莓派

树莓派DIY

关注 424

dawnchengx 关注了专栏 · 2018-12-09

开源分布式关系型数据库 TiDB

TiDB 是一款定位于在线事务处理/在线分析处理( HTAP: Hybrid Transactional/Analytical Processing)的融合型数据库产品,实现了一键水平伸缩,强一致性的多副本数据安全,分布式事务,实时 OLAP 等重要特性。同时兼容 MySQL 协议和生态,迁移便捷,运维成本极低。

关注 3468

dawnchengx 关注了专栏 · 2018-12-09

前端工匠公众号

我是浪里行舟,每周分享至少两篇前端文章,致力于打造一系列能够帮助初中级工程师提高的优质文章

关注 7049

认证与成就

  • 获得 1 次点赞
  • 获得 0 枚徽章 获得 0 枚金徽章, 获得 0 枚银徽章, 获得 0 枚铜徽章

擅长技能
编辑

(゚∀゚ )
暂时没有

开源项目 & 著作
编辑

(゚∀゚ )
暂时没有

注册于 2016-12-23
个人主页被 174 人浏览