文章目录

• 前言
• 八大排序算法的实现
• • 1、插入排序（直接插入排序、希尔排序）
  • 2、选择排序(简单选择排序、堆排序)
  • 3、交换排序（冒泡排序、快速排序）
  • 4、归并排序
  • 5、基数排序
• 总结

前言

我们在学习数据结构或者算法的过程中不可避免地需要用到排序，所谓排序就是将记录按照一定的次序排列起来。
而在数据结构中主要介绍了，八种常见排序，本次就让我们一起来学习吧。

提示：以下是本篇文章正文内容，下面讲解可供参考

八大排序算法的实现

1、插入排序（直接插入排序、希尔排序）

核心思想：
将待排序的序列分成有序区和无序区两部分，将无序区中一记录在有序区内排序插入，使得有序区长+1.

（1）直接插入排序：

思想：
先循环找到无序区中待插入的记录，并置于“哨兵位”，然后将有序区中最后一位逐一与其比较，若大则后移让位，若小则不动，直到确定插入位置并插入。

动图演示：

参考代码：

void InsertSort(RcdType &L) {	//对顺序表进行直接插入排序 
	int i,j;
	for (i=1;i<L.length;++i) {
		if (L.rcd[i].key>L.rcd[i+1].key) {	
		//循环找到无序区中待插入的记录L.rcd[i+1]
		//将其存放在“哨兵位” 
			L.rcd[0] = L.rcd[i+1];
			j = i+1;
			while (L.rcd[j-1].key>L.rcd[0].key) {
				L.rcd[j] = L.rcd[j-1];
				j--;	
			} 
			L.rcd[j] = L.rcd[0];	//插入 
		}
	} 
} 

（2）希尔排序：
希尔排序是对直接插入排序的一种改良，但也是一种不稳定的排序算法。
思想：
将待排序序列看成是一个等差数列，按一定的公差从中选出若干个子数列，并对各子数列进行直接插入排序，依次减少公差，重复以上操作，直至公差为1.
动图演示：

参考代码：

一趟希尔排序：

//对顺序表做一次希尔排序，增量为d(可理解为公差） 
void ShellInsert(RcdSqList &L,int d) {
	int i,j;
	for (i=1;i<L.length-d;++i) {
		if (L.rcd[i].key>L.rcd[i+d].key) {	
		//循环找到无序区中待插入的记录L.rcd[i+d]
		//将其存放在“哨兵位” 
			L.rcd[0] = L.rcd[i+d];
			j = i+d;
			while (L.rcd[j-d].key>L.rcd[0].key) {
				L.rcd[j] = L.rcd[j-d];
				j--;	
			} 
			L.rcd[j] = L.rcd[0];	//插入 
		}
	} 	 
} 

由此可见，一趟希尔排序的代码和直接插入排序的代码高度相似。其实，直接插入排序可以看成是增量为1的希尔排序。

希尔排序：

void ShellSort(RcdSqList &L,int d[],int t) {
	//按照增量序列d[0...t-1]对顺序表L做希尔排序
	int k;
	for (k=0;k<t;k++) {
		ShellInsert(L,d[k]);	//一趟增量为d[k]的插入排序 
	}
} 

2、选择排序(简单选择排序、堆排序)

**思想：**选择排序是指在无序区中选出关键字最小的记录，置于有序区的最后，直到全部记录有序。

（1）简单选择排序：

动图演示：

参考代码：

void select_sort(int a[],int n) {       //传入数组的要排序的元素个
	int i,j,min,t;
	for(i=0;i<n-1;i++) { 
		min=i;      //min:当前最小值下标
		for(j=i+1;j<n;j++) {       //扫描余下的部分
			if(a[min]>a[j])        //若有其它元素更小，就记录其下标
			min=j;
			if(min!=i) {       //保若最小值不在排序区首位，就换到首位
				t=a[min]; a[min]=a[i]; a[i]=t;
			}
		}
	} 
}

（2）堆排序：

核心思想：
将待排序序列构造成一个大顶堆（或者小顶堆），此时，整个序列的最大值（最小值）就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值（最小值）。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值（次大值）。如此反复执行，便能得到一个有序序列了。

大顶堆进行升序，小顶堆进行降序

动图演示：

3、交换排序（冒泡排序、快速排序）

两两比较（可相邻或否），逆序交换

（1）冒泡排序

思想：相邻两两比较，逆序交换

但是在这里要注意的是需要比较的趟数和次数。
n个记录需要比较n-1趟，就好比两个数只需要比较1一趟；第i趟只需要比较n-i次（每一趟之后的比较次数都会减一）
动图演示：

参考代码：

void bubble_sort(int a[], int n) {       //传入数组的要排序的元素个数
	int i, j, t;
	for (j=0; j<n-1; j++) {       //n个元素比较n-1轮
		for (i= 0; i<n-1-j;i++) {  //比较相邻的两个数
			if(a[i]>a[i+1]) {          //若大小顺序不符，就交换
				t=a[i];  a[i]=a[i+1]; a[i+1]=t;
				}
		}
	} 
}

（2）快速排序
动图演示：

参考代码：

对记录的顺序表L进行快速排序：

void QuickSort(RcdSqList &L) {	//对记录的顺序表L进行快速排序 
	QSort(L.rcd,1,L.length);
} 

对记录序列rcd[s…t]进行快速排序：

void QSort (RcdType rcd[],int s,int t) {
	//对记录序列rcd[s...t]进行快速排序
	int pivotloc ;
	if (s<t) {	//长度大于一
		 pivotloc = Partition(rcd,s,t);
		 QSort(rcd,s,pivotloc-1);z
		 QSort(rcd,pivotloc+1,t) ;
	} 
} 

划分算法：

int Partition (RcdType rcd[],int low,int high) {
	//对子序列rcd[low...high]进行一次划分，并返回枢轴应当所处的位置
	//使得在枢轴之前的关键字均不大于它的关键字，
	//枢轴之后的关键字均不小于它的关键字
	rcd[0] = rcd[low];
	while (low < high) {
		//low和high从待排序序列的两端交替地向中间移动
		while (low < high && rcd[high].key >= rcd[0].key) {
			--high;
		} 
		rcd[low] = rcd[high];	//将比枢轴关键字小的关键字移到低端 
		while (low < high && rcd[low].key <= rcd[0].key) {
			++low;
		} 
		rcd[high] = rcd[low];	//将比枢轴关键字大的关键字移到高端 
	} 
}

4、归并排序

核心思想：
将待排序序列等比例划分成几个子序列，重复以上步骤，直至子序列长度为1，逐层将各子序列有序合并组成有序序列。

2-路归并：

动图演示：

参考代码：

void Merge(RcdType SR[],RcdType TR[],int i,int m,int n) {
	//将相邻的有序区间SR[i..m]和SR[m+1...n]归并为有序的TR[i..n] 
	int k,j;
	for (j = m+1,k=1;i<=m && j<=n;++k) {
		//SR中的记录按关键字从小到大复制到TR中
		if (SR[i].key<=SR[j].key) {
		//此处注意，若<=改为<,则归并排序不稳定 
			TR[k] = SR[i++] ;
		} 
		else {
			TR[k] = SR[j++] ; 
		}
	}
	while (i<=m) {	//将剩余的SR[i..m]复制到TR 
		TR[k++] = SR[i++];	
	}
	while (j<=n) {	//将剩余的SR[j..n]复制到TR
		TR[k++] = SR[j++];	
	}
}

递归归并排序：

动图演示：

参考代码：

void MSort(RcdType R1[],RcdType R2[],int i,int s,int t) {
	//对R1[s..t]进行归并排序，若i%2==1，则排序后的记录存入R2[s...t],
	//否则存入R1[s..t]
	int m;
	if (s == t) {	//此时子序列长度为 1 
		if (1 == i%2) {		
		//排序过程是交替使用R1和R2的，而最后要回到R1
		//所以才会有这个要求 
			R2[s] = R1[s];
		}
	} 
	else {
		m = (s+t)/2;		//拆分 
		MSort(R1,R2,i+1,s,m);
		MSort(R1,R2,i+1,m+1,t);
		if (1 == i%2) {
			Merge(R1,R2,s,m,t);		//归并 
		}
		else {
			Merge(R2,R1,s,m,t);
		}
	}
}

对顺序表进行2-路归并排序：

void MergeSort(RcdSqList &L) {
	//对顺序表L进行2-路归并排序
	RcdType *R;
	//申请辅助空间 
	R = (RcdType*)malloc((L.lenght+1)*sizeof(RcdType)); 
	//对L.rcd[1..L.lenght]归并排序 
	MSort(L.rcd,R,0,1,L.lenght); 
	free(R); 
} 

5、基数排序

核心思想：
（在这里，为了更好的理解，我们以一个三位数的关键字为例，如：321）
“312”这个关键字可以看成是由多个关键字组合而成，个位、十位、百位。如果从最低位（个位）的关键字起，先按关键字的不同值将记录“分配”到r个子序列，再从小到大将各子序列依次首尾相接“收集”在一起，如此重复m趟（由m个关键字组合而成的关键字），最终完成整个记录的排序。

动图演示：


参考代码：

//一趟基数排序
void Radixpass(KeysRcdType rcd[],KeysRcdType rcd[],int n,int i,int count[],int pos[],int radix) {
	//对数组rcd中记录关键字的第i位计数，计算得到起始位置数组pos[]
 	//并按照pos[]数组将rcd中记录复制到数组rcd1中
	 int k,j;
	 for (k=1;k<=n;k++) {
	 	count[rcd[k].keys[i]]++;	//对各种取值计数 
	 } 
	 pos[0] = 1;
	 for (j=1;j<radix;++j) {
	 	pos[j] = count[j-1] + pos[j-1];		//求起始位置 
	 } 
	 for (k=1;k<=n;k++) {	//收集
	 	j = rad[k].keys[i]; 
	 	rcd1[pos[j]++] = rcd[k];	//复制记录，对应起始位置+1 
	 } 
} 

总结