排序算法概述

排序

将一组数据按指定方式进行排列的过程叫做排序，常见的排序算法有八种

排序算法的对比情况：

八大排序（原理+代码）

1.冒泡排序

原理：最经典的排序算法，每次比较相邻两数大小，如果为逆序，则交换这两个数，flag用来检查本次是否交换了，如果没有，证明已经排好序，可以直接退出。

代码：

cpp
void BubbleSort(vector<int> &a){		
	for(int i=a.size()-1;i>=0;i--){
		int flag=0;
		for(int j=0;j<i;j++){
			if(a[j]>a[j+1]){
				swap(&a[j],&a[j+1]);
				flag++;
			}
		}
		if(!flag) return;
	}
}

2.选择排序

原理：第一次从a[0]-a[n-1]选出一个最小值与a[0]交换，第二次从a[1]-a[n-1]选出最小值与a[1]交换，以此类推。

代码：

cpp
void SelectSort(vector<int> &a){		
	for(int i=0;i<(int)a.size()-1;i++){
		int value=1e9+7,index=i;
		for(int j=i;j<(int)a.size();j++){
			if(a[j]<value){
				index=j;
				value=a[j];
			}
		}
		swap(&a[i],&a[index]);
	}
}

3.插入排序

原理：将n个元素看作一个有序表与一个无序表，开始时有序表只有一个元素，排序时每次将无序表中的一个元素插入到有序表中的适当位置，使之成为一个新的有序表。

代码：

cpp
void InsertSort(vector<int> &a){		
	for(int i=1;i<(int)a.size();i++){
		int index=i-1,value=a[i];
		while(a[index]>value&&index>=0){
			a[index+1]=a[index];
			index--;
		}
		a[index+1]=value;
	}
}

4.希尔排序

原理：把数组按一定的增量分组，每组进行插入排序，随着增量减少，每组关键词越来越多，当增量减少为1的时候，整个数组恰好被分为一组，此时排序终止。 希尔排序是一种插入排序经过改进后的更高效的排序，也是一种插入排序，也称为缩小增量排序。

代码：

cpp
void ShellSort(vector<int> &a){			
	for(int gap=a.size()/2;gap>0;gap/=2){
		for(int i=gap;i<(int)a.size();i++){
			int j=i,t=a[i];
			if(a[j]<a[j-gap]){
				while(j-gap>=0&&t<a[j-gap]){
					a[j]=a[j-gap];
					j-=gap;
				}
				a[j]=t;
			}
		}
	}
}

5.快速排序

原理：是使用最广泛的排序，对冒泡排序的一种改进，通过一趟排序将数组分割成两部分，其中一部分所有数据都比另一部分小，再对这两部分分别使用快速排序（可用递归），以此达到所有数据有序。

代码：

cpp
void QuickSort(vector<int> &a,int l,int r){
	if(l>=r) return;
	int i=l,j=r;
	while(i!=j){
		while(a[j]>a[l]&&j>=i) j--;
		while(a[i]<a[l]&&i<=j) i++;
		swap(&a[i],&a[j]);
	}
	swap(&a[l],&a[i]);
	QuickSort(a,l,i-1);
	QuickSort(a,i+1,r);
}

6.归并排序

原理：利用归并思想，采用分治策略，递归拆分子序列，然后将两个有序的子序列合并成一个有序的子序列，最终合并所有的子序列得到一个有序序列。

代码：

cpp
void MergeSort(vector<int> &a,int l,int r,int *tmp){
	if(l>=r) return;
	int mid=(l+r)/2;
	MergeSort(a,l,mid,tmp);
	MergeSort(a,mid+1,r,tmp);
	int i=l,j=mid+1,t=0;
	while(i<=mid&&j<=r){
		if(a[i]<a[j]){
			tmp[t++]=a[i++];
		}
		else{
			tmp[t++]=a[j++];
		}
	}
	while(i<=mid){
		tmp[t++]=a[i++];
	}
	while(j<=r){
		tmp[t++]=a[j++];
	}
	t=0;
	int tl=l;
	while(tl<=r){
		a[tl++]=tmp[t++];
	}
}

7.基数排序

原理：基数排序是桶排序的扩展，属于分配式排序。将整数按位切割成不同数字，然后按每个位数分别比较。

代码：

cpp
void RadixSort(vector<int> &a){
	vector<int> bucket[10];
	for(int i=10;;i*=10){
		for(int j=0;j<(int)a.size();j++){
			bucket[a[j]*10/i%10].push_back(a[j]);
		}
		if(a.size()==bucket[0].size()) return;
		int t=0;
		for(int j=0;j<10;j++){
			for(int k=0;k<(int)bucket[j].size();k++){
				a[t++]=bucket[j][k];
			}
			bucket[j].clear();
		}
	}
}

8.堆排序

原理： 1）将待排序的n个数据构造成一个大顶堆 2）将根节点与末尾元素互换 3）将剩余n-1个元素重新构造一个大顶堆 4）反复执行得到有序的序列

代码：

cpp
void Sift(vector<int> &a,int head,int tail) {
	int dad=head,son=dad*2+1;
	while(son<=tail) {
		if(son+1<=tail&&a[son]<a[son+1])
			son++;
		if(a[dad]>a[son])
			return;
		else {
			swap(a[dad],a[son]);
			dad=son;
			son=dad*2+1;
		}
	}
}

void HeapSort(vector<int> &a) {
	for(int i=a.size()/2-1; i>=0; i--) {
		Sift(a,i,a.size()-1);
	}
	for(int i=a.size()-1; i>0; i--) {
		swap(a[i],a[0]);
		Sift(a,0,i-1);
	}
}