—————————文中的部分代码思路参考自《大话数据结构》一书。 

 目录

冒泡排序

插入排序

希尔排序

堆排序 

选择排序 

归并排序

快速排序 

冒泡排序

原始的冒泡排序是对整个序列相邻两数字间重复做循环，并未考虑的序列实际的有序情况，而对冒泡排序的分析可知，若某一趟排序完成后没有相邻元素的交换即说明序列已经有序，可以结束循环，从而大大缩减运行时间，所以优化后的冒泡排序该设置一个“交换标记”，来促成循环的结束。

---

#include 
#include 
#define arr_len 8
void Swap(int *a, int *b){
	int temp;
	temp = *a;
	*a = *b;
	*b = temp;
}
void BubbleSort(int a[]){
	int i, j;
	bool flag = true;		//交换标记 
	for(i=1;ia[j+1]){
				Swap(&a[j],&a[j+1]);
				flag = true;
			}
		}
	}
}
void main(){
	int arr[arr_len+1]={0,52,86,43,31,95,7,89,42};
	int i;
	BubbleSort(arr);
	for(i=1;i<=arr_len;i++){
		printf("%dt", arr[i]);
	}
}

  

冒泡排序是一种稳定的算法，其平均时间复杂度为O(n^2)，最好情况下为 O(n)，最坏情况下为O(n^2)，辅助空间为O(1)。

---

插入排序

插入排序即初始时认为序列的第一个元素是个有序的子列，然后循环从第二个元素(i=2)开始，比较a[i]和子列最后一个元素a[i-1]，若满足a[i] < a[i-1]则将a[i]插入到子列合适的位置，否则直接将a[i]视为新子列最后一个元素，重复上述过程直到遍历至序列最后一个数。 

---

#include 
#include 
#define arr_len 8
void InsertSort(int a[]){
	int i, j;
	for(i=2;i<=arr_len;i++){
		if(a[i]a[0];j--)
				a[j+1]=a[j];	//元素后移腾位置 
            //此时a[j]

  

 简单插入排序是一种稳定的排序，平均、最好、最坏情况下的时间复杂度均为O(n^2)，辅助空间为O(1)，当序列基本有序时选用插入排序可使效率达到最高。

---

希尔排序

 希尔排序是一种结合了插入排序的排序方法，其核心是给序列分成几个小块，在小块内排序，逐步使得序列基本有序，再利用插入排序的性质，此时性能相比大部分的O(n^2)类排序算法有很大提升。 

---

#include 
#include 
#define arr_len 8
void ShellSort(int a[]){
	int i, j;
	int increment=4;
	do{
		increment--;//增量序列设置为3、2、1
		//插入排序的变形 
		for(i=1+increment;i<=arr_len;i++){
			if(a[i]0 && a[j]>a[0];j-=increment)	//多一步对j的判断是否为正 
					a[j+increment]=a[j];
				a[j+increment]=a[0]; 
				}
			}
		}
	}while(increment!=1);
}
void main(){
	int arr[arr_len+1]={0,52,86,43,31,95,7,89,42};
	int i;
	ShellSort(arr);
	for(i=1;i<=arr_len;i++){
		printf("%dt", arr[i]);
	}
}

   

 希尔排序是一种不稳定的排序，平均情况下时间复杂度为O(nlogn~n^2)，最好情况时为O(n^1.3)，最坏情况下为O(n^2)，辅助空间为O(1)。

---

堆排序 

堆排序首先建立了大根堆这样一个概念，假想着将序列表示成一个堆(实际并没有真正构造出一棵树形结构)，每次筛选堆得到最大元素后将其与尾结点交换并脱离出去，这样一趟就得到“最大元素”的最终位置，重复筛选即得到有序序列。

---

#include 
#include 
#define arr_len 8
void Swap(int *a, int *b){
	int temp;
	temp = *a;
	*a = *b;
	*b = temp;
}
//调整序列使a[s..m]为大根堆 
void HeapAdjust(int a[], int s, int m){
	int temp, j;
	temp=a[s];
	for(j=2*s;j<=m;j*=2){		//沿较大孩子结点向下筛选 
		
		//j从s的左孩子开始，经过筛选始终置为较大元素的下标 
		if(j=1;i--){		//初始化大根堆 
		HeapAdjust(a,i,arr_len);
	}
	for(i=arr_len;i>1;i--){
		Swap(&a[1],&a[i]);		//大根堆的根结点与尾结点交换 
		HeapAdjust(a,1,i-1);		//调节除尾结点后的根堆 
	}
}
void main(){
	int arr[arr_len+1]={0,52,86,43,31,95,7,89,42};
	int i;
	HeapSort(arr);
	for(i=1;i<=arr_len;i++){
		printf("%dt", arr[i]);
	}
}

  

 堆排序是一种不稳定的排序，其平均、最好、最坏情况下的时间复杂度均为O(nlogn)，辅助空间为O(1)，适用于快速确定出序列中较大(小)元素的最终位置。

---

选择排序 

选择排序应该是提到的几种排序方法中思路最简单且易理解的一种排序法，其核心就是从第一个元素开始向后，逐步选择出需要放在该位置的元素，即第一个位置找到最小元素、第二个位置找到次小元素、第三个位置找到倒数第三小的元素......。

#include 
#include 
#define arr_len 8
void Swap(int *a, int *b){
	int temp;
	temp = *a;
	*a = *b;
	*b = temp;
}
SelectSort(int a[]){
	int i, j, k;
	for(i=1;i

  

简单选择排序是一种稳定的算法，其平均、最好、最坏情况下的时间复杂度均为O(n^2)，辅助空间为O(1)。

---

归并排序

归并排序的核心思路就是分而治之，将待排序的序列从中间一分为二，再将分出的两个子序列又一分为二，重复下去直至所有子列长度为1时为止，这时每个子列可视为一个有序的序列，然后再将子列按从小到大的顺序归并为一个更大的序列(按照分割时的配对情况)，重复下去直至归并后的序列长度为原序列长度，这时得到的序列有序。

---

#include 
#include 
#define arr_len 8
void Merge(int A[], int B[], int s, int m, int t){		//将已排好的 A[s..m]和 A[m+1..t]归并为 B[s..t]
	int j, k, l;
	for(j=m+1, k=s;s<=m && j<=t;k++){		//A左右两部分元素从小到大并入B
		if(A[s]

  

由运行时间可以看到归并排序的效率是很高的，但缺点就是需要的内存相比其他几种算法要多。归并排序是一种稳定的算法，其平均、最坏、最好的时间复杂度均为O(nlogn)，辅助空间为O(n)。

---

快速排序 

快速排序的算法利用的是双指针，其核心思想就是每趟排序确定一个序列元素pivotkey的最终位置，通常选序列中的第一个元素作为这个元素，然后比pivotkey小的都置于左边，比pivotkey大的都置于右边，接着对两边又作快速排序，重复下去直到某趟排序后pivotkey的左右序列均只有一个元素位置，容易想到用递归来实现该算法。

---

#include 
#include 
#define arr_len 8
QuickSort(int a[], int low, int high){		//对区间a[low..high]作快速排序 
	if(low=pivotkey)		j--;
		if(i 
  
 
快速排序是一种不稳定的算法，其平均、最好情况的时间复杂度均为O(nlogn)，最坏情况为O(n^2)，辅助空间为O(logn)~O(n)。