前端菜鸡的算法——排序算法总结

发表于 | 分类于
字数统计: 1.5k字 | 阅读时长 ≈ 5分钟

快速排序算法

简介

​ 快速排序也是一种分治的思想，和归并排序是互补的。归并排序是先进行递归操作之后在进行归并排序，而快速排序算法是先进行排序后递归操作。归并排序的时候，一般切分的位置恰好在数组的中心位置，但是快速排序的切分的位置是取决于数据的内容。

简单的思路

​ 快速排序的思路是随机的取a[lo]为划分元素，之后指定两个左指针i和右指针j分别指向a[lo]以及数组的最后一个元素的下一个元素。然后开始左指针扫描，遇到比a[lo]大的元素就停止，右指针开始从后往前扫描，遇到比a[lo]小的元素就停止。然后左右指针指向的那个两个数相互交换位置，左指针又开始扫描，重复以上的过程，直到两个指针相遇为止。这样的话，所有在左指针的元素都比a[lo]小，在a[lo]右边的元素都比他大。最后再交换a[j]和`a[lo]，本次的整个过程排序完毕。接下来就是要把a[i]两边的数进行递归排序，直到递归到只剩一个数。

1542441375905

​ 这是第四版算法对于整个快速排序的过程图示，其中，j代表了在每一次递归排序的结束的时候和a[lo]交换位置的那个数的地址。并且在每次排序的时候，大小为1的子数组由于lo == hi所以不进行排序。

代码的实现

接下来是对上述算法的代码实现：

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
31
32
33
34
35
36
37
38
39
40
41
42
43
package QuickSort;

public class Quick {
    public static void sort(int[] a){
        sort(a,0,a.length-1);
    }
    public static void sort(int[] a,int lo,int hi){
        if (hi <= lo){
            return;
        }
        int j = partition(a,lo,hi);
    }
    public static int partition(int[] a,int lo,int hi){
        int i = lo,j = hi + 1;
        int v = a[lo];
        while(true){
            while(a[++i] < v)
                if (i >= hi)
                    break;
            while(a[--j] > v){
                if (j <= lo){
                    break;
                }
            }
            if (i >= j) break;
            exchange(a,i,j);
        }
        exchange(a,lo,j);
        return j;
    }
    public static void exchange(int[] a,int i,int j){
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    public static void main(String[] args) {
        int arr[] ={5,2,9,4,3,1,6,8,5};
        Quick.sort(arr);
        for (int i = 0;i < arr.length;i++)
            System.out.println(arr[i]);
    }
}

算法分析

​ 快速排序算法相较于希尔排序算法和归并排序算法而言，其优势在于进行的时候主要是在和一个数进行比较，在内循环中不需要太多的移动。其次就是快排得到比较次数相较于其他的两个算法而言少了很多。排序的效率取决于划分的位置，接下来我们将要来探讨这个算法的时间复杂度的影响。

​ 理想的情况下，快排的时间复杂度最好是每次划分的时候划分点正好位于数组的中心，即正好能够将整个数组对半分。这个时候快排的比较次数正好满足分治递归的$$C_n=2C_N/_2+N$$。那么这个时候$$C_N~Nlg_n$$.但是，并不是所有的情况都能使划分点恰好落在中心位置，这种情况总是以一定的概率出现的，这就需要我们去计算这个算法的平均消耗代价。

​ 结论：长度为N的无重复数组排序，快排平均需要$$~2NlnN$$次比较。这里是根据相关的数学推导得到的，具体的推导过程在算法第四版的186页，这里不做深入的探究

快排的改进算法

快排最糟糕的情况，无非就是当数组划分的时候不均匀，尤其是如果一个数组顺序的时候，可能会出现一边的数组总是空的的情况，这个时候的时间复杂度：

​ $$N+(N-1)+(N-2)+….+2+1=(N+1)N/2$$

​ 也就是说算法比较的次数约在$$N^2/2$$这个级别上。这是一种相当糟糕的情况，但是可以将待排的数组打乱，这样将会把比较次数降低很多。

切换插入排序

​ 通过实验发现，在数据量很小的情况下，快速排序的性能不如插入排序，所以我们可以考虑在快速排序到小数组的时候利用插入排序来解决排序问题。这样可以明显提升。一般可以把代码中的

1
2
3
if (hi <= lo){
            return;
        }

更改为：

1
2
3
4
if (hi <= lo + M){
     insertSort(a,lo,hi)；
     return;
}
三取样划分

​ 我们也可以通过三取样划分来提升性能。这时候实际上是将数组划分为了三部分，并设置了三个指针lt,i和gt。a[lo...lt-1]是小于当前比较的数，a[`lt…i-1]一部分是等于当前比较的数，a[i…gt]一部分是不确定的元素，a[gt+1…hi]大于当前比较的数。初始化的时候，首先将lt置为lo，将i置为lo+1，将gt置为hi，之后开始进行比较。如果：

a[i]小于v，将a[lt]和a[i]交换，并将lt和i加一

a[i]大于v，将a[gt]和a[i]交换，将gt减一

a[i]等于v，将i加一

具体的代码见下面所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static void threeQuick(int[] a,int lo,int hi){
        if (hi <= lo) return ;
        int lt = lo,i = lo + 1,gt = hi;
        int v = a[lo];
        while(i <= gt){
            if (a[i] > v){
                exchange(a,gt,i);
                gt--;
            } else if(a[i] < v){
                exchange(a,lt,i);
                i++;
                lt++;
            } else {
                i++;
            }
        }
        threeQuick(a,lo,lt - 1);
        threeQuick(a,gt + 1,hi);
    }
0%