我的算法笔记—快速排序

Love The Way You Lie 2022-02-27 07:46 120阅读 0赞

# 算法介绍 #

由C.A.R.Hoare在1962年提出，因为此算法而获得图灵奖。它是一种递归算法，核心思想是：先找出一个数的应该在的位置，将数列分为左右两部分，左右两部分分别进行排序。

# 图片示例 #

![clipboard.png][]

我们先找到 K 的位置，i 指针先向后移动，所指元素如果比K大，就停止，此时再由 j 由队尾向前遍历，如果 j 指向元素比K小，j 停止移动，此时将 i 和 j 指向元素对调。  
比如：

![clipboard.png][clipboard.png 1]

此时 i 指向元素R比 K 大，j 指向元素C比K小 ，对调R，C。

![clipboard.png][clipboard.png 2]

此时 i j 根据上述规则 继续移动，一直到 指针 j 超过了i ，K 和 j 对调

![clipboard.png][clipboard.png 3]

![clipboard.png][clipboard.png 4]

此时K已经在位置上了，将数列分为左右两边，左右再进行递归排序

# 实现代码 #

//主方法
    private static void sort(Comparable[] a, int lo, int hi) {
            if (lo >= hi) {
                return;
            }
            int j = partition(a, lo, hi);
            sort(a, 0, j - 1);
            sort(a, j + 1, hi);
        }
    
    private static int partition(Comparable[] a, int lo, int hi) {
            int i = lo ;
            int j = hi+1;
    //a[lo]即为第一个元素，先将它的位置找到
            while (true){
    // 找到 i ，i 小于 a[lo]的话，继续移动
                while (less(a[++i],a[lo])){
                    if(i == hi){
                        break;
                    }
                }
    // j 也类似
                while (less(a[lo],a[--j])){
                    if(j==lo){
                        break;
                    }
                }
    // 两指针擦肩而过的话，就跳出循环
                if(i>=j){
                    break;
                }
    // 交换 i和j
                change(a,i,j);
            }
    // 交换 lo和j
            change(a,lo,j);
            return j;
        }

# 复杂度推导 #

假设 Cn 为快速排序N个数需要比较的次数。  
找到第一个数所在位置，我们需要比较 N+1次。指针 i 和 j 每移动一次就需要比较一次，一共是 N-1次， 加上相遇比较一次 ，擦肩而过还需要比较一次，所以是N+1次。  
这个数会把数组分割成各种情况，会分割成(1,n-1),(2,n-2),(3,n-3).......(n-1,1)各种情况，所以Cn的表达式如下：

![clipboard.png][clipboard.png 5]  
![clipboard.png][clipboard.png 6]

平均复杂度为1.39NlgN

# 缺点与不足 #

1. 为了保证性能，快速排序前一定要打乱数组顺序，正序下，快排复杂度需要1/2 
        乘以n的二次方
        
    
     2. 如果数组存在大量相同的数，性能也是平方级的

第一次写博客，这是我的理解，如果有误请指出，我会立即纠正，谢谢

[clipboard.png]: /images/20220227/c7a55573aa56471091158fcf332815c0.png
[clipboard.png 1]: /images/20220227/3388123ce15c4409bfcfff3f362d327c.png
[clipboard.png 2]: /images/20220227/4a3f363af9474699a6896d53c2114f07.png
[clipboard.png 3]: /images/20220227/4c037185a9e84e6ab539fa90a2423488.png
[clipboard.png 4]: /images/20220227/6fde63ec3551493f9e968473c98ae9b3.png
[clipboard.png 5]: /images/20220227/34b5e03b4b9f4039af140489b9e6905a.png
[clipboard.png 6]: /images/20220227/f889e9a9288b4b128ab390cc6993458e.png