快速排序算法

发表于 | 分类于 | 阅读次数:

快排的算法在平均状况下，排序效率为 O（N*LogN），运算效率是最高的，所以最受欢迎。而且在快速排序的算法中还体现着 分冶 思想，这几天我学习了一下这个算法，整理一下他的算法思路。

快速排序算法-维基百科

算法原理

快速排序算法使用分冶法来把一个序列分为两个序列

  • 从数列中挑出一个元素，称为“基准”（pivot）
  • 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面
  • 在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作
  • 递归地把 小于基准值元素的子数列 和 大于基准值元素的子数列 排序

下面的图片来自于维基百科，通过看这张图可以观察到使用该算法后数据的变化

白话快排

我在CSDN看到一篇非常好的文章讲解了这个算法的原理，在这里转载过来一部分

白话经典算法系列之六 快速排序 快速搞定

虽然快速排序称为分治法，但分治法这三个字显然无法很好的概括快速排序的全部步骤。因此我的对快速排序作了进一步的说明：挖坑填数+分治法：

先来看实例吧，定义下面再给出（最好能用自己的话来总结定义，这样对实现代码会有帮助）

以一个数组作为示例，取区间第一个数为基准数。

0 1 2 3 4 5 6 7 8 9
72 6 57 88 60 42 83 73 48 85

初始时，start = 0; end = 9; pivot = a[i] = 72

由于已经将a[0]中的数保存到pivot中，可以理解成在数组a[0]上挖了个坑，可以将其它数据填充到这来。

从j开始向前找一个比pivot小或等于pivot的数。当 end=8，符合条件，将a[8]挖出再填到上一个坑a[0]中。a[0]=a[8]; start++; 这样一个坑a[0]就被搞定了，但又形成了一个新坑a[8]，这怎么办了？简单，再找数字来填a[8]这个坑。这次从start开始向后找一个大于X的数，当start =3，符合条件，将a[3]挖出再填到上一个坑中a[8]=a[3]; end–;

数组变为：

0 1 2 3 4 5 6 7 8 9
48 6 57 88 60 42 83 73 88 85

start = 3; end = 7; pivot =72

再重复上面的步骤，先从后向前找，再从前向后找。

从j开始向前找，当end =5，符合条件，将a[5]挖出填到上一个坑中，a[3] = a[5]; start ++;

从i开始向后找，当start =5时，由于start == end退出。

此时，start = end = 5，而a[5]刚好又是上次挖的坑，因此将X填入a[5]。

数组变为：

0 1 2 3 4 5 6 7 8 9
48 6 57 42 60 72 83 73 88 85

可以看出a[5]前面的数字都小于它，a[5]后面的数字都大于它。因此再对a[0…4]和a[6…9]这二个子区间重复上述步骤就可以了

对挖坑填数进行总结

1．start end pivot共三个参数; 将基准数挖出形成第一个坑a[start]。

2．end–由后向前找比它小的数，找到后挖出此数填前一个坑a[start]中。

3．start++由前向后找比它大的数，找到后也挖出此数填到前一个坑a[end]中。

4．再重复执行2，3二步，直到 start == end，将基准数填入a[start]中。

照着这个总结很容易实现挖坑填数的代码：

代码示例

  • 在这个类中，为了方便理解，我创建了多个方法互相调用，并在函数上面加上了注释
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
public class QuickSort {
    //判断数组是否为空
    private static boolean isEmpty(int[] arr) {
        return arr == null || arr.length == 0;
    }
    
    //在主类中调用该方法，对数组进行排序
    public static void quickSort(int[] arr) {
        if (isEmpty(arr))
            System.out.println("数组为空，请输入数据后再排序！！！");
        quickSort(arr, 0, arr.length - 1);
    }
	
    //也可以选择在主类中调用该方法，对数组指定位置进行排序
    public static void quickSort(int[] arr, int low, int high) {
        if (isEmpty(arr))
            return;
        if (low < high) {
            //基准数据在数组中所在的角标
            int pivotKey = partion(arr, low, high);
            //将基准左部递归排序
            quickSort(arr, low, pivotKey - 1);
            //将基准右部递归排序
            quickSort(arr, pivotKey + 1, high);
        }
    }

    private static int partion(int[] arr, int start, int end) {
        //以第一个数据为基准
        int pivot = arr[start];
        while (start < end) {
            //从数组右端开始，若数据大于基准值，end指针-1
            //反之则交换该数据值和基准值，并且将start++
            while (arr[end] >= pivot && start < end)
                end--;
            if (start < end) {
                arr[start] = arr[end];
                start++;
            }
            
            //从数组左端开始，若数据小于基准值，start指针+1
            //反之则交换该数据值和基准值，并且将end--
            while (arr[start] < pivot && start < end)
                start++;
            if (start < end) {
                arr[end] = arr[start];
                end--;
            }
        }
        //返回基准值在数组中的角标
        return start;
    }
    
    //函数功能：交换数组中两个数据值
    private static void swap(int[] arr,int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

优化

  • 在上面可以发现，代码的基准一直选取的是第一个数，在某些糟糕的情况下，该算法效率并不佳
  • 过段时间，我会再补上优化的部分