快速排序里的学问:快速排序的过程

理解快速排序的工作机制
服务器君一共花费了156.726 ms进行了4次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

通过前面问题以及引入了“信息熵”的概念,我们可以重新来理解排序的本质:

一组未排序的N个数字,它们一共有N!种重排,其中只有一种排列是满足题意的(譬如从大到小排列)。

换句话说,排序问题的可能性一共有N!种。任何基于比较的排序的基本操作单元都是“比较a和b”,这就相当于猜数字游戏里面的一个问句,显然这个问句的答案只能是“是”或“否”,一个只有两种输出的问题最多只能将可能性空间切成两半,根据上面的思路,最佳切法就是切成1/2和1/2(将数组切成一半)。也就是说,我们希望在比较了a和b的大小关系之后,如果发现a < b的话剩下的排列可能性就变成N!/2,如果发现a>b也是剩下N!/2种可能性。

由于假设每种排列的概率是均等的,所以这也就意味着支持a < b的排列一共有N!/2个,支持a > b的也是N!/2个,换言之,a < b的概率等于a > b的概率。

我们希望每次在比较a和b的时候,a < b和a > b的概率是均等的,这样我们就能保证无论如何都能将可能性缩小为原来的一半的最优下界。

一个直接的推论是,如果每次都像上面这样的完美比较,那么N个元素的N!种可能排列只需要log2N!就排查完了,而log2N!近似于NlogN。这正是快排的复杂度。

快速排序的实现

我们先理解一下快速排序的工作机制吧,下面是《算法导论》里的快排:

QUICKSORT(A, p, r)
 if p < r
	then q ← PARTITION(A, p, r)   //关键
         QUICKSORT(A, p, q - 1)
         QUICKSORT(A, q + 1, r)

快速排序算法的关键是PARTITION过程,它对A[p..r]进行就地重排:

PARTITION(A, p, r)
  x ← A[r]
  i ← p - 1
  for j ← p to r - 1
       do if A[j] ≤ x
             then i ← i + 1
                  exchange A[i] <-> A[j]
  exchange A[i + 1] <-> A[r]
  return i + 1

我们将上面的过程用C语言描述一下:

#include "stdio.h"
#include "math.h"
#include "stdlib.h"

void PrintArray(int *arr);
void swap(int *a,int *b);

int num = 10;

void QuickSort(int *arr, int beg, int end)
{
	if(beg < end)
	{
		int pivot = Partition(arr, beg, end);
		QuickSort(arr, beg, pivot-1);
		QuickSort(arr, pivot+1, end);
	}
}

void swap(int *a,int *b)
{
    int tmp;
    tmp = *a;
    *a = *b;
    *b = tmp;
}

int Partition(int *arr, int beg, int end)
{
    int j;
	int sentinel = arr[end];
	printf("\n    sentinel = arr[%d] = %d", end, sentinel);
	int i = beg-1;
	for(j=beg; j<=end-1; ++j)
	{
		if(arr[j] <= sentinel)
		{
		    printf("\n    arr[%d](%d) <= sentinel(%d)", j, arr[j], sentinel);
			i++;
			swap(&arr[i], &arr[j]);
		}
	}
	swap(&arr[i+1], &arr[end]);

	printf("\n排序过程:");
	PrintArray(arr);
	return i+1;
}

void PrintArray(int arr[])
{
    int i;
	for(i=0; i < num; ++i)
	{
	    printf("%d ", arr[i]);
	}
}

int main()
{
    int i;
	int arr[10];

	srand(time(0));
    for(i=0; i < 10; i++)
    {
        arr[i] = rand()%100+1;
        //printf("%d ", rand()%100+1);
    }
    printf("初始数组:");
    PrintArray(arr);

	QuickSort(arr, 0, num-1);
	printf("\n最后结果:");
	PrintArray(arr);
	return 0;
}
初始数组:59 40 55 92 73 69 27 79 3 30
    sentinel = arr[9] = 30
    arr[6](27) <= sentinel(30)
    arr[8](3) <= sentinel(30)
排序过程:27 3 30 92 73 69 59 79 40 55
    sentinel = arr[1] = 3
排序过程:3 27 30 92 73 69 59 79 40 55
    sentinel = arr[9] = 55
    arr[8](40) <= sentinel(55)
排序过程:3 27 30 40 55 69 59 79 92 73
    sentinel = arr[9] = 73
    arr[5](69) <= sentinel(73)
    arr[6](59) <= sentinel(73)
排序过程:3 27 30 40 55 69 59 73 92 79
    sentinel = arr[6] = 59
排序过程:3 27 30 40 55 59 69 73 92 79
    sentinel = arr[9] = 79
排序过程:3 27 30 40 55 59 69 73 79 92
最后结果:3 27 30 40 55 59 69 73 79 92
Process returned 0 (0x0)   execution time : 0.564 s
Press any key to continue.

从程序的运行结果我们就可以很清晰地看出快速排序的工作工程:

  1. 定点sentinel设为数组最后一个元素30
  2. 把比30小的划成一个小组(27,3,30),并把它们放在数组的前面。
  3. 定点sentinel设为小组的最后一个,不包含30,即(27,3)中的3。
  4. 对小组原地排序,即(3,27)。这样就完成这个小组的排序了(3,27,30)。
  5. 定点sentinel再次设为数组最后一个元素55。
  6. 把小于55的元素找出来划分为另外的小组(40)。
  7. 那个小组的排序也已经完成(40,55)。
  8. 定点再设为73,同样分组(69,59,73),排序为(59,69,73)。
  9. 定点再设为79,分组(79)
  10. 完成排序:3 27 30 40 55 59 69 73 79 92

总结下快排的过程:随机选择一个元素做“轴元素”(上面的定点sentinel),将所有小于轴元素的移到左边,其余移到右边。根据这个过程,快排的第一次比较就是将一个元素和轴元素比较,这个时候显而易见的是,“大于”和“小于”的可能性各占一半。这是一次漂亮的比较。

延伸阅读

此文章所在专题列表如下:

  1. 快速排序里的学问:从猜数字开始
  2. 快速排序里的学问:再看看称球问题
  3. 快速排序里的学问:信息熵
  4. 快速排序里的学问:快速排序的过程
  5. 快速排序里的学问:霍尔与快速排序
  6. 快速排序里的学问:霍尔快排的实现
  7. 快速排序里的学问:枢纽元选择与算法效率
  8. 快速排序里的学问:随机化快排

本文地址:http://www.nowamagic.net/librarys/veda/detail/2390,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.nowamagic.net/librarys/veda/detail/2390

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

大家都在看

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知道他要表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《代码之美》 聂雪军 (译者)

《代码之美》介绍了人类在一个奋斗领域中的创造性和灵活性:计算机系统的开发领域。在每章中的漂亮代码都是来自独特解决方案的发现,而这种发现是来源于作者超越既定边界的远见卓识,并且识别出被多数人忽视的需求以及找出令人叹为观止的问题解决方案。《代码之美》33章,有38位作者,每位作者贡献一章。每位作者都将自己心目中对于“美丽的代码”的认识浓缩在一章当中,张力十足。38位大牛,每个人对代码之美都有自己独特的认识,现在一览无余的放在一起,对于热爱程序的每个人都不啻一场盛宴。 虽然《代码之美》的涉猎范围很广,但也只能代表一小部分在这个软件开发这个最令人兴奋领域所发生的事情。

更多计算机宝库...