详解快速排序

2020-06-19

感觉又是一个容易忘记的东西，记下笔记，用于日后复习

写法一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public static void sort(int[] ints, int l , int r){
    int left = l;
    int right = r;

    int base = ints[(l+r)/2];

    while(left <= right){

        while (ints[left] < base)
            left++;

        while (ints[right] > base)
            right--;

        if(left <= right){
            int tmp = ints[left];
            ints[left] = ints[right];
            ints[right] = tmp;
            left++;
            right--;
        }
    }
    // only one
    if(l < right){
        sort(ints, l, right);
    }
    if(left < r){
        sort(ints, left, r);
    }
}

递归实现的快排，重点就是快排的思想分治，以及递归出口的理解

分治

选取一个基准值，保证基准值不变，比基准值小的放左边，大的放右边，一次排序的完结标志就是，left = right ，结果是把一个元素放在它该放的位置

1
2
3
4
5
while (ints[left] < ints[base])
    left++;

while (ints[right] > ints[base])
    right--;

上面代码的解释就是：

如果左边的值比基准值小就不处理（因为已经符合当次排序的结果），直到找到大于等于基准值的，于是左边的下标一直往右移动

如果右边的值比基准值大就不处理（因为已经符合当次排序的结果），直到找到小于等于基准值的，于是右边的下标一直往左移动

当他们碰撞以后，也就说明，左边的都比基准值小，右边的都比基准值大，一次排序完成

递归出口

当只有一个元素的时候便不用排序了

未完待定

Tags: 算法 数据结构
← Linux 如何定位文件锁的问题 php7 安装phalcon 扩展 -- docker centos7 →
赏
使用支付宝打赏
使用微信打赏

若你觉得我的文章对你有帮助，欢迎点击上方按钮对我打赏

扫描二维码，分享此文章