快速排序算法原理与实现

快速排序算法原理与实现
快速排序是对冒泡排序的一种改进。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
假设要排序的数组是A[1]……A[N],首先任意选取一个数据(通常选用第一个数据)作为关键数据,然后将所有比它小的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一趟快速排序。一趟快速排序的算法是:

1)、设置两个变量I、J,排序开始的时候I = 1,J = N;
2)、以第一个数组元素作为关键数据,赋值给X,即X = A[1];
3)、从J开始向前搜索,即由后开始向前搜索(J = J – 1),找到第一个小于X的值,两者交换;
4)、从I开始向后搜索,即由前开始向后搜索(I = I + 1),找到第一个大于X的值,两者交换;
5)、重复第3、4步,直到I = J;

   例如:待排序的数组A的值分别是:(初始关键数据X:=49)
                   A[1]     A[2]     A[3]     A[4]     A[5]      A[6]     A[7]
                     49        38       65       97       76       13        27

进行第一次交换后:   27        38       65       97       76       13        49
                  	( 按照算法的第三步从后面开始找第一个小于X的值,此时J = 7)

进行第二次交换后:   27        38       49       97       76       13        65
                  	( 按照算法的第四步从前面开始找第一个大于X的值,65 > 49,两者交换,此时I = 3 )

进行第三次交换后:   27        38       13       97       76       49        65
			( 按照算法的第五步将又一次执行算法的第三步从后开始找,此时J = 6)

进行第四次交换后:   27        38       13       49       76       97        65
			( 按照算法的第四步从前面开始找大于X的值,97 > 49,两者交换,此时I = 4 )

此时再执行第三步的时候就发现I = J,从而结束一趟快速排序,那么经过一趟快速排序之后的结果是:27       38       13       49       76       97        65,即所有大于49的数全部在49的后面,所有小于49的数全部在49的前面。

快速排序就是递归调用此过程——以49为中点分割这个数据序列,分别对前面一部分和后面一部分进行类似的快速排序,从而完成全部数据序列的快速排序,最后把此数据序列变成一个有序的序列,根据这种思想对于上述数组A的快速排序的全过程如图6所示:

初始状态 {49 38 65 97 76 13 27}
进行一次快速排序之后划分为 {27 38 13} 49 {76 97 65}
分别对前后两部分进行快速排序 {13} 27 {38} 49 {65} 76 {97}

1)、设有N(假设N=10)个数,存放在S数组中;
2)、在S[1。。N]中任取一个元素作为比较基准,例如取T=S[1],起目的就是在定出T应在排序结果中的位置K,这个K的位置在:S[1。。K-1]<=S[K]<=S[K+1..N],即在S[K]以前的数都小于S[K],在S[K]以后的数都大于S[K]; 3)、利用分治思想(即大化小的策略)可进一步对S[1。。K-1]和S[K+1。。N]两组数据再进行快速排序直到分组对象只有一个数据为止。 如具体数据如下,那么第一趟快速排序的过程是:

数组下标: 
	1      2      3      4      5      6      7      8      9      10

	45     36     18     53     72     30     48     93     15     36

	I                                                              J

(1)      36     36     18     53     72     30     48     93     15      45
(2)      36     36     18     45     72     30     48     93     15      53
(3)      36     36     18     15     72     30     48     93     45      53
(4)      36     36     18     15     45     30     48     93     72      53
(5)      36     36     18     15     30     45     48     93     72      53

通过一趟排序将45放到应该放的位置K,这里K=6,那么再对S[1。。5]和S[6。。10]分别进行快速排序。

一般来说,冒泡法是程序员最先接触的排序方法,它的优点是原理简单,编程实现容易,但它的缺点就是–程序的大忌–速度太慢。下面我介绍一个理解上简单但编程实现上不是太容易的排序方法,我不知道它是不是现有排序方法中最快的,但它是我见过的最快的。排序同样的数组,它所需的时间只有冒泡法的 4% 左右。我暂时称它为“快速排序法”。

“快速排序法”使用的是递归原理,下面我结合一个例子来说明“快速排序法”的原理。首先给出一个数组{53,12,98,63,18,72,80,46, 32,21},先找到第一个数–53,把它作为中间值,也就是说,要把53放在一个位置,使得它左边的值比它小,右边的值比它大。{21,12,32, 46,18,53,80,72,63,98},这样一个数组的排序就变成了两个小数组的排序–53左边的数组和53右边的数组,而这两个数组继续用同样的方式继续下去,一直到顺序完全正确。

我这样讲你们是不是很胡涂,不要紧,我下面给出实现的两个函数:

/*
	n就是需要排序的数组,left和right是你需要排序的左界和右界,
	如果要排序上面那个数组,那么left和right分别是0和9
*/
void quicksort(int n[], int left,int right)
{
	int dp;
	if (left

我们上面提到先定位第一个数,然后整理这个数组,把比这个数小的放到它的左边,大的放右边,然后返回这中间值的位置,下面这函数就是做这个的。

int partition(int n[],int left,int right)
{
	int lo,hi,pivot,t;
	
	pivot = n[left];
	lo = left - 1;
	hi = right + 1;
	
	while(lo + 1 != hi) {
	     if(n[lo + 1] <= pivot)
	       lo++;
	     else if(n[hi - 1] > pivot)
	       hi--;
	     else {
	       t = n[lo + 1];
	       n[++lo]=n[hi - 1];
	       n[--hi]=t;
	     }
	}
	
	n[left] = n[lo];
	n[lo] = pivot;
	return lo;
}

这段程序并不难,应该很好看懂,我把过程大致讲一下,首先你的脑子里先浮现一个数组和三个指针,第一个指针称为p指针,在整个过程结束之前它牢牢的指向第一个数,第二个指针和第三个指针分别为lo指针和hi指针,分别指向最左边的值和最右边的值。lo指针和hi指针从两边同时向中间逼近,在逼近的过程中不停的与p指针的值比较,如果lo指针的值比p指针的值小,lo++,还小还++,再小再++,直到碰到一个大于p指针的值,这时视线转移到hi指针,如果 hi指针的值比p指针的值大,hi--,还大还--,再大再--,直到碰到一个小于p指针的值。这时就把lo指针的值和hi指针的值做一个调换。持续这过程直到两个指针碰面,这时把p指针的值和碰面的值做一个调换,然后返回p指针新的位置。

 
// 快速排序的递归实现 
void QuickSort(int arr[], int n)
{
     if(n <= 1)
     return;
     
     int i =0 , j = n - 1;
     int key = arr[0];
     int index = 0;
     
     while(i < j)
     {
             // 从后向前搜索 
             while(j > i && arr[j] > key)
             		j--;
             		
             if(j == i)
             		break;
             else
             {
             		//交换 a[j] a[i]
             		int tmp = arr[i];
             		arr[i] = arr[j];
             		arr[j] = tmp;
                index = j;
             }
             
             // 从前向后搜索
             while(i < j && arr[i] < key)
             		i++;
             		
             if(i == j)
             		break;
             else
             {
             		// 交换 a[i] a[j] 
             		int tmp = arr[i];
             		arr[i] = arr[j];
             		arr[j] = tmp;
                index = i;
             }             
     }    
      
     QuickSort(arr, index);
     QuickSort(arr + index + 1, n - 1 - index);
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*

code

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据