复习备考数据结构与算法（五）——排序方法比较

数据结构与算法复习总结（五）

写在前面

明天考试了，今天是最后的复习时间，这学期以来直到期末才认认真真把教材翻完，我的教材现在被翻得糜烂的，嗯······这才是读书人的书应该有的样子，感觉真的比之前上课听天书一样的好多了，期末考试考什么内容和题型我都摸清了，估计应付考试不难，可能最后的算法设计题会有些困难，随缘吧不管了

一、随便介绍几种重要的排序

1. 桶排序
   我们要在数据范围为1-1000的若干个数里进行排序，那么需要1000个桶，来记录每一个数出现的次数，令初始数组a[1]-a[1000]的每一个数都为0，意味着数据为1，2，…，1000的个数都为0，哪一个数出现一次，对应的数组项加1

#include<stdio.h>
int main(){
	int a[1001],i,j,t,n;
	for(i=1;i<=1000;i++)
		a[i]=0;
	
	printf("输入n：");
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf("%d",&t);
		a[t]++;
	}
	for(i=1;i<=1000;i++){
		for(j=1;j<=a[i];j++)
		printf("%d ",i);
	}
	return 0;
} 

案例实现

2. 快速排序
快速排序是最常用的排序方法，在排序数据完全无序的情况下最易发挥其长处，当数据基本有序时，快速排序有最坏时间复杂度为O(n²)
快速排序的基本思想就是：每次排序时设置一个基准点，把序列中小于等于基准数的数放在基准点左边，大于等于基准数的数放在基准点右边。快速排序需要用到递归思想，每一趟排序把基准点的数放在最终的位置，在分别对基准点左右两边的数据进行快速排序。
看看代码：

#include <stdio.h> 
int a[101],n;  
 
void quicksort(int left,int right) {
    int i,j,t,temp;
    if(left>right)        
		return;             
	temp=a[left]; //temp中存的就是基准数      
	i=left;     
	j=right;     
	while(i!=j){
	    //顺序很重要，要先从右往左找          
		while(a[j]>=temp && i<j)             
			j--;        
		//再从左往右找          
		while(a[i]<=temp && i<j)             
			i++; 
 
        //交换两个数在数组中的位置          
		if(i<j){
	        t=a[i];             
			a[i]=a[j];             
			a[j]=t;         
		}     
	}       
    a[left]=a[i]; 
	a[i]=temp;          
	quicksort(left,i-1);
	quicksort(i+1,right); 
} 
 
int main() {     
	int i,j,t; 
	scanf("%d",&n);     
	for(i=1;i<=n;i++)        
	scanf("%d",&a[i]); 
 
    quicksort(1,n); 
	for(i=1;i<=n;i++)         
	printf("%d ",a[i]); 
 
    return 0; 
} 

案例实现

3. 冒泡排序
基本思想是每次比较两个相邻的元素，如果顺序错误就交换位置
时间复杂度比较高O(n²)

//冒泡排序
#include<stdio.h>
int main(){
	int a[100],i,j,t,n;
	scanf("%d",&n);  //n个数排序
	for(i=0;i<n;i++)
	scanf("%d",&a[i]); 
	
	for(i=0;i<n-1;i++){
		//n个数排序，进行n-1趟即可 
		for(j=0;j<n-i-1;j++){
			if(a[j]>a[j+1]){
				t=a[j];
				a[j]=a[j+1];
				a[j+1]=t;
			}
		}
	}
	
	for(i=0;i<n;i++)
	printf("%d ",a[i]);
	return 0; 
} 

案例实现

二、内部排序方法比较

• 先进的排序算法有快速排序、堆排序、归并排序，当n较大时，应该选用先进排序方法
• 空间复杂度最大的是归并排序，O(n)
• 不稳定的排序方法有希尔排序、快速排序、堆排序
• 堆是一种选择排序