快速排序

快速排序是一种比选择排序更优秀的排序算法，选择排序运行的时间为：$O(n^2)$，而快速排序法的运行时间为：$O(nlog_2n)$，快速排序使用了D&C的思想（一种分而治之的思想）。下面我们来分析快速排序算法。

假设我们使用快速排序算法对数组进行排序，对排序算法来说，最简单的数组是什样子的呢？其实间的数组是不需要排序的数组。

所以，基线条件为数组为空或只包含一个元素，这样只需要返回数组即可。

1
2
3
def quicksort(array):
  if len(array)<2:
  	return array

如果数组长度为2，只需要将数组的两个元素对调。

如果数组长度为3，那么我们就要使用D&C，将数组做适当的分解，知道满足基线条件，所以首先，需要从数组中选择一个元素，这个元素称之为基准值(pivot)。

假设我们将数组的第一个元素用作基准值，接下来，找出比基准值小的元素以及比基准值大的元素。

这被称作分区（partitioning）。现在我们就有了满足快速排序的一些条件：

  • 一个由所有小于基准值的数字组成的子数组；
  • 基准值；
  • 一个由所有大于基准值的数字组成的子数组；

虽然我们进行了分区，但得到的两个子数组是无序的。当然如果这两个数组是有序的，那对整个数组的排序将非常容易。

如果子数组是有序的，就可以像下面这样合并得到一个有序地数组：左边的数组 + 基准值 +右边的数组。在这里，就是$[10, 15] + [33] + [ ]$，结果为有序数组$[10, 15, 33]$。

现在u，我们需要将两个子数组进行快速排序，在合并结果，就能得到一个有序数组。

1
2
qicksort([15,10] + [33] )+ quicksort([])
> [10,15,33]       #一个有序数组

不管选取谁作为基准值，都适用。

总结一下，无论是什么长度的数组，进行快速排序都需要经历下面这几个步骤：

(1) 选择基准值。
(2) 将数组分成两个子数组：小于基准值的元素和大于基准值的元素。
(3) 对这两个子数组进行快速排序。

代码实现

下面我们来写一个快速排序的代码：

1
2
3
4
5
6
7
8
9
def quicksort(array):
  if len(array) < 2:
 	 return array       #基线条件：为空或只包含一个元素的数组是“有序”的
  else:
    pivot = array[0]    #递归条
    less = [i for i in array[1:] if i <= pivot]   #由所有小于基准值的元素组成的子数组
    greater = [i for i in array[1:] if i > pivot]  #由所有大于基准值的元素组成的子数组
    return quicksort(less) + [pivot] + quicksort(greater)
print quicksort([10, 5, 2, 3])

上面是一个python的代码，我们再来写一个Java的：

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
public class QuickSort {
    public static void sort(int a[], int low, int hight) {
        int i, j, index;
        if (low > hight) {
            return;
        }
        i = low;   //首位
        j = hight; //末位
        index = a[i]; // 用子表的第一个记录做基准
        while (i < j) { // 从表的两端交替向中间扫描
            while (i < j && a[j] >= index)
                j--;
            if (i < j)
                a[i++] = a[j];// 用比基准小的记录替换低位记录
            while (i < j && a[i] < index)
                i++;
            if (i < j) // 用比基准大的记录替换高位记录
                a[j--] = a[i];
        }
        a[i] = index;// 将基准数值替换回 a[i]
        sort(a, low, i - 1); // 对低子表进行递归排序
        sort(a, i + 1, hight); // 对高子表进行递归排序
    }
    public static void quickSort(int a[]) {
        sort(a, 0, a.length - 1);
    }
   
  //方法测试
    public static void main(String[] args) {
        int a[] = { 2,1,3,5,4 };
        quickSort(a);
        System.out.println(Arrays.toString(a));
    }
}

上面代码的图解思路：

参考文献

《算法图解》 【美】Aditya Bhargava

欢迎关注：Lvshen’s Blog