快速排序

发表于:，更新于:，By Guodong
大纲
  1. 1. 一个视频让你清晰了解快速排序的流程。
  2. 2. 算法介绍
  3. 3. 代码实现
  4. 4. 算法精妙之处

本文介绍快速排序算法的设计中的精妙之处。

一个视频让你清晰了解快速排序的流程。

感谢博文提供的视频。
加个友情链接。http://blog.dinggangchui.cn/
貌似有45秒广告，不过值得一看，过目难忘啊。
http://v.youku.com/v_show/id_XMzMyODk4NTQ4.html

算法介绍

数组为a，采用递归方式实现，子数组左右下标分别为left，right。
算法中没有讨论程序何时退出等边界条件。

  1. 如果left<right，选择数组关键元素key=a[left]，设置两个游标i，j，初始时分别指向left和right；否则退出；
  2. while(a[i]>key&&i<j)j–;
  3. if (i < j) a[i++] = a[j];
  4. while (a[i] <= key && i < j) i++;
  5. if (i < j) a[j–] = a[i];
  6. 如何i<j，返回2，否则进入7；
  7. 最终将key元素放入a[i]，也就是a[j]；
  8. 在数组的left,i-1和数组的i+1,right区间上，重复进行1至7的递归操作。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static void quickSort(int[] a) {
    quickSort(a, 0, a.length - 1);
}
    public static void quickSort(int[] a, int left, int right) {
    if (left < right) {
        int key = a[left];
        int i = left;
        int j = right;
        do {
            while (a[j] >= key && i < j) j--;
            if (i < j) a[i++] = a[j];
            while (a[i] <= key && i < j) i++;
            if (i < j) a[j--] = a[i];
        } while (i < j);

        a[i] = key;
        quickSort(a, left, i - 1);
        quickSort(a, i + 1, right);
    }
}

算法精妙之处

上面的可以不看，下面的建议看看。
可能很少有人想过为什么要分别从数组的左右两端与选取的key做比较。这是一种比较难理解的方式，很多人可能为了记住算法直接把代码背下来了，但是很快忘掉。

其实比较好理解的方式是这样的：
假设我们对快排做一点修改，在元素对比的过程中，不是从左右两端分别进行对比，而是从左端开始对比，比key小的元素左移，大的元素右移，这样扫描一次数组，所有比目标元素小的都在key的坐标，反之都在右边。

这样说起来有问题吗？有。
假设数组为[5,4,3,6,7,0]。
按照上诉算法，
第1次比较后4左移[4,5,3,6,7,0]，注意，是左移，不是交换。
第2次比较后3左移[4,3,5,6,7,0]。
第3次比较后6位置不变[4,3,5,6,7,0]。
第4次比较后7位置不变[4,3,5,6,7,0]。

问题来了，第5次比较时，发现0比key小，0要左移到key的左侧。由于是数组，非链表。此移动过程，需要将5，6，7右移，0放在5的位置。

如果真这样设计了，快排的时间复杂度平均起来还是o(nlogn)，但是对比最开始提到的两端比较的方式，免不了多做了很多次的数组移动，这样在真是的时间消耗上，o(nlogn)前面要加上一个大大的常量系数。