C语言实现：快速排序、冒泡排序、选择排序比较

左手的ㄟ右手 2022-03-22 03:43 282阅读 0赞

*本篇文章对基础快速排序、冒泡排序、简单选择排序进行比较。*  
（一）1.快速排序算法：通过一趟排序将待排记录分割为独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可对这两部分记录继续进行排序已达到整个序列有序的目的。值得注意的是，**快速排序不是一种稳定的排序算法**，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。  
2.具体实现：对于快速排序算法来讲，首先就是要选取关键字，在这里我们先介绍最简单的关键字的取法：即**将待排序数组的首元素作为关键字，然后想办法将其放到一个位置上，使得它左边的值全部比他小，右边的值都比他大**，我们将这样的关键字成为枢纽。  
例如数组\{5, 2, 1, 4, 3, 6, 9, 7, 8, 0\}，我们选取5作为关键字，在进行一次移位操作之后数组变成了\{0，2，1，4，5，6，9，7，8\}，并向用户返回5，数字5表明5放在数组下标为5的位置，此时计算机把原来的数组变成两个位于5左侧和右侧的数组（也叫低子表和高子表）即\{0，2，1，4\}和\{6，9，7，8\}，然后递归的对高低两个子表进行上述操作直到子表顺序全部正确；小编在程序中的移位操作函数叫做partition，该函数接受三个参数，第一个是数组的地址，其他两个分别是数组中的第一个元素的下标low和最后一个元素的下标high。首先将数组首元素当做关键字交给临时变量pivotkey，然后当low<high的时候将比枢纽大的元素放在右侧，比枢纽小的元素放在左侧，**注意while循环没有加大括号**具体的换位操作如果想不通的话大家可以自己动手实现一下，此处不再赘述。  
因为在排序中不停地用到了两个数据的交换操作，方便起见，直接自定义了数据交换函数swap，该函数接受三个参数，一个是数组s的地址，另外两个分别是数组中待交换元素的下标。  
![在这里插入图片描述][20190125163921101.png]  
在三种排序之后需要对排序完成的数组进行打印，因此直接定义一个打印函数用于数组元素的打印。  
![在这里插入图片描述][20190125180005167.png]  
*partition函数定义如下*  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70]  
递归部分：将上一步找到的枢纽交给临时变量。当low<high的时候递归的对高低子表进行排序，代码如下  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70 1]  
最后需要自定义一个快速排序函数来进行函数的参数传递工作，其中的length为数组的长度（数组中的元素个数），在主函数中利用sizeof函数进行求解 ，思想是用数组占用的总共的空间除以第一个元素所占的空间就是数组元素的个数，sizeof(数组名)/sizeof(数组首元素)=数组中元素个数即数组长度。  
![在这里插入图片描述][201901251709335.png]  
快速排序的缺陷：通过上面的代码我们可以看出快速排序算法的瓶颈会发生在关键字的选取上，上面我们采用的是直接选取了第一个元素作为关键字然后将数组一分为二，那么很有可能这个关键字的选取并不合理，就会导致不愉快的事情发生。  
快速排序的改进：1.为了更换关键字的选取方法有人提出，应该随机获得一个low和high之间的数rnd，让他的关键字s\[rnd\]与s\[low\]互换，此时就不容易出现关键字的值太过极端的情况这种方法被称为**随机选取枢纽法**，可以认为这个办法在某种程度上解决了快排的性能瓶颈，但是随机让我们感觉总有些碰运气的感觉，如果运气不佳，随机到了依旧是稍微极端的关键字怎么办。  
2.于是就有人提出了第二种改进方案，**三数取中法**，即取三个关键字先进行排序，将中间数作为枢纽，一般是取左端、右端和中间三个数，当然也可以是随机选取，这样一来，至少这个数一定不会是最极端的数。从概率的角度讲，取三个数均为极端的数字的可能性微乎其微，因此中间数位于较为中间的值的可能性就大大提高了。因为整个序列是无序状态，随机选取三个数和从左右中端三个数字其实是一回事，而随机数生成器本身还会带来一些时间上的开销，因此**随机生成不予考虑**。算法如下：

int m = low + (high - low) / 2;		//计算数组中间元素的下标
    	if(s[low] > s[high])
    		swap(s, low, high);		//交换左端与右端数据，保证左端最小
    	if(s[m] > s[high])
    		swap(s, high, m);		//交换中间与有端数据，保证中间最小
    	if(s[m] > s[low])
    		swap(s, m, low);		//交换中间与左端数据，保证左端数据最小	 
    	//这时，s[low]已经是整个序列左中右三个关键字的中间值

三数取中法对于小数组来讲还是会选择到一个比较好的枢纽值，但是对于非常大的待排序的序列来讲还不足以保证能够选出一个好的枢纽，因此就有了**九数取中法**，他先从数组中分三次抽样，每次取三个数，从三个样品中取出中间数，然后再从这三个中间数中再取出一个中间数作为枢纽。这样我们就会保证取到的枢纽更接近中间值的关键字。  
3.之前我们提到过说，直接插入排序对于数组元素的量很少的时候效率非常高，如果这个时候我们还是用快排的话反而不如直接插入来的更快一些，因此我们可以**给定一个阈值**（有资料认为7比较合适，也有认为50更加合理，在实际应用的时候我们可以做适当的调整，我们这里假设阈值为7）当数组元素的个数小于阈值的时候我们用直接插入排序，元素个数大于阈值的时候我们用快排。 思想：通过宏定义的方式给出阈值，在排序的时候先进行一次比较，如果待排序列元素个数大于阈值的话我们就调用快排函数，否则调用直接插入函数。  
（二）1.冒泡排序算法：它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素已经排序完成。在该排序算法中越大（越小）的元素会通过交换慢慢的“浮”到最顶端，就像水中的气泡一样，故名冒泡排序。  
2.具体实现：本例程中将数组中的元素从大到小进行排序，因此当前一个元素比后一个元素小的时候进行交换，采用两个 for循环完成排序，代码如下  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70 2]  
3.那么我们会想到一个问题，如果我们给定的序列已经排好序，那么照理来讲我们不应该进行排序操作，但是如果参考上面的排序算法的话，我们会发现程序仍然会将整个序列遍历一次，这样子是不是有些犯不上，因此，我们可以在循环里面再加上一个条件，当我们发现这个序列是一个已经排好序的序列的话，我们就不用再花时间一次一次的去遍历整个序列。算法如下：

void swap_list(int *a, int length)
    {
    	int i, j, shaobing = 1;
    	for(i = 0;i < length && shaobing;i++)
    	{
    		shaobing = 0;
    		for(j = i + 1;j <= length;j++)
    		{
    			if(a[i] > a[j])
    			{
    				swap(a, i, j);		//交换数值
    				shaobing = 1;
    			}	 
    		}
    	} 
    }

（三）简单选择排序算法：通过n - i次关键字之间的比较，从n - i + 1个记录中选出关键字最小的记录，并和第i(1 <= i <= n)个记录交换之。简单的说 ，在第一个for循环假设第一个元素为最小元素，然后在第二个for循环中进行比较，当目前的最小值比数组中的元素数值小的时候直接将该关键字的下标数值给min，当min不等于i的时候就说明找到了最小值，进行交换，代码如下  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70 3]  
*完整的代码及测试数据运行结果如下*

#include<stdio.h>			
     
    void swap(int *s, int i, int j) 	//交换数据的函数 
    { 
    	int temp = s[i]; 
    	s[i] = s[j]; 
    	s[j]= temp; 
    }
    /*
    int partition(int *s, int low, int high)	//改进之后的partition 
    {
    	int m = low + (high - low) / 2;		//计算数组中间元素的下标
    	if(s[low] > s[high])
    		swap(s, low, high);		//交换左端与右端数据，保证左端最小
    	if(s[m] > s[high])
    		swap(s, high, m);		//交换中间与有端数据，保证中间最小
    	if(s[m] > s[low])
    		swap(s, m, low);		//交换中间与左端数据，保证左端数据最小	 
    	//这时，s[low]已经是整个序列左中右三个关键字的中间值	
    		
    	int pivotkey = s[low];		//用子表的第一个作为枢纽 
    	while(low < high)
    	{
    		while(low < high && s[high] >= pivotkey)		//将比枢纽大的数值交换到右半边 
    			high--;
    			swap(s, low, high);
    		while(low < high && s[low] <= pivotkey)		将比枢纽小的数值交换到左半边
    			low++;
    			swap(s, low, high); 
    	}
    	return low;		//返回枢纽所在的位置 
    }
    */
    /*
    int partition(int *s, int low, int high)
    {
    	int pivotkey = s[low];		//用子表的第一个作为枢纽 
    	while(low < high)
    	{
    		while(low < high && s[high] >= pivotkey)		//将比枢纽大的数值交换到右半边 
    			high--;
    			swap(s, low, high);
    		while(low < high && s[low] <= pivotkey)		将比枢纽小的数值交换到左半边
    			low++;
    			swap(s, low, high); 
    	}
    	return low;		//返回枢纽所在的位置 
    }*/
    
    void digui(int *s, int low, int high)
    {
    	int pivot = partition(s, low, high);
    	if(low < high)
    	{
    		digui(s, low, pivot - 1);
    		digui(s, pivot + 1, high);
    	}
    }
    
    void quick_sort(int *s, int length)
    {
    	//	int length = sizeof(s) / sizeof(s[0]); 	主函数中length的求法 
    	digui(s, 0, length);
    }
    
    void print(int *s, int length)
    {
    	int i;
    	for(i = 0;i < length;i++)
    		printf("%d, ", s[i]);
    	printf("\n");
    }
    
    void maopao_sort(int *s, int length)
    {
    	int i, j;
    	for(i = 0;i < length; i++)
    		for(j = i +1;j < length;j++)
    		{
    			if(s[i] < s[j])
    			{
    				int temp = s[i]; 
    				s[i] = s[j]; 
    				s[j]= temp;
    			}
    		 } 
    }
    
    void select_sort(int *s, int length)
    {
    	int i, j, min;
    	for(i = 1;i < length;i++)
    	{
    		min = i;						//当前下标定义为最小值下标 
    		for(j = i + 1;j <= length;j++)
    		{
    			if(s[min] > s[j])			//如果有小于当前最小值的关键字  
    				min = j;				//将这个下标赋值给min 
    		}
    			if(i != min)				//如果Min不等于i,说明找到了最小值，然后交换两个下标对应的元素值 
    			{
    				int tem = s[min];
    				s[min] = s[j];
    				s[j] = tem;
    			}
    		
    	}	
    } 
     
    int main()
    {
    	int s[] = {5, 2, 1, 4, 3, 6, 9, 7, 8, 0};
    	int length = sizeof(s) / sizeof(s[0]); 
    	int low = 0;
    	int high = length;
    
    	quick_sort(s, length);
    	puts("快速排序的结果为（从小到大）");
    	print(s, length);
    
    	printf("\n\n");
    
    	maopao_sort(s, length);
    	puts("冒泡排序的结果为（从大到小）");
    	print(s, length);
    	
    	printf("\n\n");
    	
    	select_sort(s, length);
    	puts("选择排序的结果为（从大到小）");
    	print(s, length);	
    	
    	return 0;
     }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70 4]

[20190125163921101.png]: /images/20220322/0bb5b97e75584a76836af9a92299da23.png
[20190125180005167.png]: /images/20220322/8788a6d5221242ad9ac8c8c2306f1d0b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70]: /images/20220322/a05234cbb1af4fbe921aa07d86029079.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70 1]: /images/20220322/ce6026435a414e89821cf2b176c0b37a.png
[201901251709335.png]: /images/20220322/5362d4be9236449ab41700cef084afe4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70 2]: /images/20220322/5f5c87b3450949138b4f64f2b3665101.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70 3]: /images/20220322/c4e230fc6a024987b818e26ecd0cbb64.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70 4]: /images/20220322/ed20bd9404554c03a16959b7a8cf943e.png