白话快速排序

译者注：博主的算法文章写得很好，简洁易懂，值得关注和借鉴。

转自：http://blog.csdn.net/morewindows/article/details/6684558/

通过相同的分拣效率实现快速分拣O(N*logN)几种分拣方法的效率比较高，所以经常采用，再加上快速分拣的思路----分而治之的方法确实实用，所以很多软件公司都会进行笔试面试，包括腾讯、微软等知名公司IT公司喜欢参加这个考试，也有软考等大型程序相关考试，在研究生入学考试时经常会出现快速排序的模样。

总的来说，直接从内存中编写快速排序仍然很困难，因为我根据自己的理解对快速排序进行了直接的解释。希望对大家的理解和实现有所帮助 快速排序，快速修复 。

快速排序 是C.R.A.Hoare于1962提议的分区交换排名。它采用分而治之的策略，通常称为分而治之的方法(Divide-and-ConquerMethod)。

这种方法的基本思想是：

1首先，从序列中取一个数字作为参考编号。

2分区过程将所有大于此数字的数字放在其右侧，将所有小于或等于它的数字放在其左侧。

3．再对左右区间重复第两步直到各区间只有一个数。

快速排序虽然叫分而治之，但这三个字显然不能概括快速排序的所有步骤。因此，我进一步解释了快速排序： 挖坑填数+分治法 ：

让我们先看一下示例，然后提供下面的定义（最好用自己的话总结定义，这将有助于实现代码）。

以数组为例，以区间中的第一个数字作为参考编号。

0

1

2

3

4

5

6

7

8

9

72

6

57

88

60

42

83

73

48

85

初始时，i = 0;  j = 9;   X = a[i] = 72

自从a[0]将号码保存到X在，它可以理解为在数组中a[0]我挖了一个洞，可以在这里填写其他数据。

从j开始期待比较X小或等于X的数。当j=8如果满足条件，a[8]把它挖出来，填到前一个坑里a[0]中。a[0]=a[8]; i++;  这样的坑a[0]它被固定了，但形成了一个新洞a[8]发生了什么事？简单，然后找到要填写的数字a[8]这个坑。这次来自i开始向后看，寻找大于X的数，当i=3如果满足条件，a[3]把它挖出来，填到前一个坑里中a[8]=a[3]; j--;

数组变为：

0

1

2

3

4

5

6

7

8

9

48

6

57

88

60

42

83

73

88

85

i = 3;   j = 7;   X=72

再次重复上述步骤， 首先从后到前看，然后从前到后看 。

从j开始向前看，当j=5如果满足条件，a[5]挖掘并填平前一个坑，a[3] = a[5]; i++;

从i开始向后看，当i=5时，由于i==j退出。

此时，i = j = 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．i =L; j = R; 挖出参考编号形成第一个坑a[i]。

2．j--从后到前找一个较小的数字，然后挖出这个数字来填满前面的坑a[i]中。

3．i++从前到后找一个较大的数字，然后挖出这个数字来填满前面的坑a[j]中。

4再次重复执行2，3两步直到i==j填写基准编号a[i]中。

按照此摘要，很容易实现挖掘和填充坑的代码：

[cpp] view plain copy

1. int AdjustArray( int s[], int l, int r) //返回到调整后的参考编号的位置

2. {

3. int i = l, j = r;

4. int x = s[l]; //s[l]即s[i]这是第一个坑

5. while (i < j)

6. {

7. // 从右到左查找小于x的数来填s[i]

8. while (i < j && s[j] >= x)

9. j--;

10. if (i < j)

11. {

12. s[i] = s[j]; //将s[j]填到s[i]中，s[j]形成了一个新的坑

13. i++;

14. }

15. // 从左到右查找大于或等于x的数来填s[j]

16. while (i < j && s[i] < x)

17. i++;

18. if (i < j)

19. {

20. s[j] = s[i]; //将s[i]填到s[j]中，s[i]形成了一个新的坑

21. j--;

22. }

23. }

24. //退出时，i等于j。将x填满这个坑。

25. s[i] = x;

26. return i;

27. }

重写分而治之的代码：

[cpp] view plain copy

1. void quick_sort1( int s[], int l, int r)
2. {
3. if (l < r)
4. {
5. int i = AdjustArray(s, l, r); //提前调整开挖和填充方法s[]
6. quick_sort1(s, l, i - 1); // 递归调用
7. quick_sort1(s, i + 1, r);
8. }
9. }

这种代码显然不够简洁，所以我们一起组织一下：

[cpp] view plain copy

1. //快速排序

2. void quick_sort( int s[], int l, int r)

3. {

4. if (l < r)

5. {

6. //Swap(s[l], s[(l + r) / 2]); //将中间数字与第一个数字交换 参见注1

7. int i = l, j = r, x = s[l];

8. while (i < j)

9. {

10. while (i < j && s[j] >= x) // 从右到左查找第一个小于x的数

11. j--;

12. if (i < j)

13. s[i++] = s[j];

14. while (i < j && s[i] < x) // 从左到右查找第一个大于或等于x的数

15. i++;

16. if (i < j)

17. s[j--] = s[i];

18. }

19. s[i] = x;

20. quick_sort(s, l, i - 1); // 递归调用

21. quick_sort(s, i + 1, r);

22. }

23. }

快速排序有很多改进版本，比如随机选择基准号，当区间内数据较少时直接使用其他方法进行排序，以减少递归深度。感兴趣的包可以进一步研究。

注1有些书使用中间数字作为参考编号，非常方便实现。只需将中间数字与第一个数字交换即可。