C语言-数据结构-快速排序及优化-源代码

￡神魔★判官ぃ 2022-07-13 01:16 243阅读 0赞

**1. 目标**

利用快速排序对一个数组中的数据进行排序

![Center][]

**2. 代码分析**

快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以[递归][Link 1]进行，以此达到整个数据变成有序[序列][Link 2]。

**3.时间复杂度分析**

在最优的情况下，快速排序算法的时间复杂度为O(nlogn)，最糟糕情况下的快排，其时间复杂度为O(n^2)。具体的分析可以参考[Never say Ever][]的博客。[快速排序的时间复杂度分析][Link 3]

**4.源代码**

#include<stdio.h>
    #define title "------------------------------Life is a fight!------------------------------------"
    
    void convert(int *s, int p, int e)//交换下标p 和下标e 的数据
    {
    	int mid;
    	mid= s[e];
    	s[e]=s[p];
    	s[p]=mid;
    }
    
    /*该函数用于确定新的关键点，并根据关键点，将小于关键点的值都移动到关键点的左边，大于关键点的值都移动到关键点的右边*/
    /*其中S为需要排序的对象，b为开始下标，e为结束下标*/
    int Partition(int *s, int b, int e)
    {
    	int p=b; //P用来记录关键点的下标值
    	
    	//关键点k每次选择s[b], 选择好关键点后，就是将小于关键点的值都移动到关键点的左边，大于关键点的值都移动到关键点的右边
    	int k=s[b];
    	while(b<e)
    	{
    		//从e下标开始，向左搜索，如果找到一个小于关键点k的s[e]值，或者e=b结束，
    		//k<=s[e]里的小于等于符号不可改为小于号，否则有可能死循环
    		while(b<e && k<=s[e])			
    		{
    			e--;
    		}
    		
    		//如果找到一个小于k的s[e]值，将s[e]值和关键点s[p]值交换，也就是将小于关键点的值移动到关键点的后面，并用p记录下关键点的下标
    		if(s[e]<k)
    		{
    			convert(s, p, e);
    			p=e;
    		}
    
    		//从b下标开始，向右搜索，直到找到一个大于k的s[b]值，或者e=b结束
    		//k>=s[b]里的大于等于符号不可改为大于号，否则有可能死循环
    		while(b<e &&k>=s[b] )								
     		{
    			b++;
    		}
    		if(s[b>k])//如果找到一个大于k的s[b]值，将s[b]值和s[p]值交换，并用p记录下关键点的下标
    		{	
    			convert(s, b, p);
    			p=b;
    		}
    	}
    		return p;
    }
    
    void QSort(int *s, int b, int e)
    {
    	if(b<e)//递归进行的条件
    	{
    		int p=Partition(s, b, e);//利用Partition()函数找到一个关键点
    		
    		//如果关键点满足要求，利用关键点把原来的数组进行分割，对其左边和右边分别进行递归排序
    		if(b<e && b<=p)
    			QSort(s, b, p-1);
    		
    		if(b<e && p<=e)
    			QSort(s, p+1, e);
    	}
    }
    	
    int main(void)
    {
    	int s[8]={6, 5, 7, 3, 9, 6, 8, 1};
    	int i;
    	
    	printf("%s\n\n\n",title);
    	printf("Original: ");
    	for(i=0; i<8;i++)
    		printf("%2d", s[i]);
    		
    	printf("\nQuicksort:");
    	
    	QSort(s,0,7);
    	
    	for(i=0; i<8;i++)
    		printf("%2d", s[i]);
    		
    	printf("\n");return 0;
    }

**5. 优化**

快速排序的优化方式很多，比如关键点的选取优化，小数据量时采用直接插入排序优化，尾递归优化等等。这里对Partition()函数中的数据交换部分进行优化，其他部分不变。优化后不需要convert()函数了，可以减少数据的交换次数。

源代码如下：

int Partition(int *s, int b, int e)
    {
    	int p=b; //P用来记录关键点的下标值
    	
    	//关键点k每次选择s[b], 选择好关键点后，就是将小于关键点的值都移动到关键点的左边，大于关键点的值都移动到关键点的右边
    	int k=s[b];
    	while(b<e)
    	{
    		//从e下标开始，向左搜索，如果找到一个小于关键点k的s[e]值，或者e=b结束，
    		//k<=s[e]里的小于等于符号不可改为小于号，否则有可能死循环
    		while(b<e && k<=s[e])			
    		{
    			e--;
    		}
    		
    		//如果找到一个小于k的s[e]值，将s[e]值覆盖到关键点s[p]（s[p]中的值已经备份在k里面了）
    		if(s[e]<k)
    		{
    			s[p]=s[e];
    			p=e;
    			e--;
    		}
    
    		//从b下标开始，向右搜索，直到找到一个大于k的s[b]值，或者e=b结束
    		//k>=s[b]里的大于等于符号不可改为大于号，否则有可能死循环
    		while(b<e &&k>=s[b] )								
     		{
    			b++;
    		}
    		if(s[b]>k)
    		{	
    			s[p]=s[b];
    			p=b;
    			b++;
    		}
    	}
    		s[p]=k;
    		return p;
    }

[Center]: /images/20220713/b510545e7b714c68867bb5752e080090.png
[Link 1]: http://baike.baidu.com/view/96473.htm
[Link 2]: http://baike.baidu.com/subview/71968/12546268.htm
[Never say Ever]: http://home.cnblogs.com/u/fengty90/
[Link 3]: http://www.cnblogs.com/fengty90/p/3768827.html