数据结构常用算法分析(C++版)-8大排序算法

简介

这是最后一节了，虽然比预期时间晚了半个月，不过想想终于要写完了，有种如释重负的感觉.^_^

这节呢，就讨论一下8种常用的排序算法，每一种都有其代码实现，一起来看看吧！相关代码已经托管到Github上了~我是代码，快点我

首先复习一下基础知识：

排序算法的分类：

按原理分：选择排序、交换排序、插入排序、归并排序、基数排序
按时间分：O(n^2)/O(nlogn)/O(n+m)
按稳定性分：稳定排序、不稳定排序

8大对比

仿照大神们写的排序总结，肯定少不了对比表，那咱也来写写~ 下面是8种排序算法重要属性对比表，PS：文本制表真是麻烦呐！

类型	名称	稳定排序	时间复杂	空间复杂度
选择	简单选择排序	稳定	O(n^2)	O(1)
	堆排序	不稳定	O(nlogn)	O(1)
交换	冒泡排序	稳定	O(n^2)	O(1)
	快速排序	不稳定	O(nlogn)	O(nlogn)
插入	直接插入排序	稳定	O(n^2)	O(1)
	希尔排序	不稳定	O(nlogn)	O(1)
归并	归并排序	稳定	O(nlogn)	O(n)
基数	基数排序	不稳定	O(d(n+r))	O(d+r)

详细实现

接下来就是详细代码实现啦！每个排序算法由1-3个函数去完成，在mian方法中调用执行！

主函数

主函数首先初始化v，填充随机数到v中，接着调用8种排序算法中的一个进行排序，在排序算法中进行排序计时和排序结果的输出！

PS：main方法前面的注解是每种排序算法在特定软硬件环境下的真实运行时间！来一起看看吧！


/**
* 运行时间统计：1-100范围共产生10000个整数进行排序(ms)
*	(CPU: 2.4G  RAM:1G  OS:X64)
* 0:4187
* 1:46
* 2:2953
* 3:1734
* 4:6453
* 5:31
* 6:93
* 7:31
*/

int main()
{
	init(v);
	switch(mode)
	{
		case 0:select_sort(v); break;
		case 1:heap_sort(v); break;
		case 2:insert_sort(v); break;
		case 3:shell_sort(v); break;
		case 4:bubble_sort(v); break;
		case 5:quick_sort(v); break;
		case 6:merge_2_sort(v); break;
		case 7:radix_sort(v); break;
		default:sort_print(v,0);break;
	}
	return 0;
}

const int num=10000;
const int max=100;

void sort_print(vector<int> &v,double time)
{
	cout<<"排序结果为："<<endl;
	for(vector<int>::iterator it=v.begin();it!=v.end();it++)
	{
		cout<<*it<<" "<<endl;
	}
	cout<<"共耗时："<<time<<"(ms)"<<endl;
}

void init(vector<int> &v)
{
	srand(1);
	for(int i=0;i<num;i++)
	{
		v.push_back(rand()%max+1);//rand()/double(RAND_MAX)
	}
}

可以看出，对当前特定的随机序列排序，有以下时间复杂度特性：

冒泡>选择>插入»希尔»归并>堆>基数=快速

选择排序

简单选择排序

选择排序的算法思想是：

选出所有元素最小值
与当前排序部分下一位交换


void select_sort(vector<int> &v)
{
	double start=clock();
	int min=0;
	for(int i=0;i<v.size();i++)
	{
		min=i;
		for(int j=i+1;j<v.size();j++)
		{
			if(v[min]>v[j])
				min=j;
		}
		swap(v[i],v[min]);

	}
	double end=clock();
	sort_print(v,end-start);
}

堆排序

堆排序的算法思想是：

建堆（从size/2位置开始调整堆）
输出堆顶元素并重新调整堆


//堆排序
void adjustheap(vector<int> &heap,int s)
{
	int tmp=heap[s];
	for(int j=2*s;j<heap.size();j=j*2)
	{
		if(j<(heap.size()-1)&&heap[j]>heap[j+1])
		{
			j++;
		}
		if(heap[s]>heap[j])
		{
			swap(heap[s],heap[j]);
			s=j;
		}
		else
			break;
	}
	heap[s]=tmp;
}

void heap_sort(vector<int> &heap)
{
	double start=clock();
	int tmp=0;
	//建堆
	for(int i=heap.size()/2;i>=0;i--)
	{
		adjustheap(heap,i);
	}
	//输出并调整堆
	for(int j=heap.size();j>0;j--)
	{
		heap[0]=heap.back();
		heap.pop_back();
		adjustheap(heap,0);
		heap[j]=heap[0];
	}
	double end=clock();
	sort_print(v,end-start);
}

插入排序

直接插入排序

直接插入排序算法思想：

前半部有序，将前半部所有大于新结点的元素后移
新结点插入到不大于该节点的位置


//直接插入排序
void insert_sort(vector<int> &v)
{
	double start=clock();
	int tmp=0;
	for(int i=1;i<v.size();i++)
	{
		tmp=v[i];
		for(int j=i;j>0;j--)
		{
			if(v[j-1]>tmp)
				swap(v[j],v[j-1]);
			else
				break;
		}
		swap(v[j],tmp);
	}
	double end=clock();
	sort_print(v,end-start);
}

shell排序

希尔排序思想：(分阶梯插入排序，缩小每次排序数组的大小)

从size/2开始，每次分半，直到1为止
对每个阶梯，进行“直接插入排序”


//希尔排序
void shell_sort(vector<int> &v)
{
	double start=clock();
	int tmp =0;
	for(int m=v.size()/2;m>0;m=m/2)//shell排序 + 直接插入排序
	{
		for(int i=0;i<v.size();i=i+m)
		{
			tmp=v[i];
			for(int j=i;j-m>0;j=j-m)
			{
				if(v[j-m]>tmp)
					v[j]=v[j-m];
				else
					break;
			}
			v[j]=tmp;
		}
	}
	double end=clock();
	sort_print(v,end-start);
}

交换排序

冒泡排序

冒泡排序是一种古老而形象的排序算法！算法思想：

2部分，后半部分有序，前半部分无序！
每次比较相近的2个值，大值向后冒泡，直到冒泡到有序序列，有序+1，无序-1，重新产生气泡

//冒泡排序
void bubble_sort(vector<int> &v)
{
	double start=clock();
	for(int i=0;i<v.size();i++)
	{
		for(int j=0;j<v.size()-i-1;j++)
		{
			if(v[j+1]<v[j])
				swap(v[j+1],v[j]);
		}
	}
	double end=clock();
	sort_print(v,end-start);
}

快速排序

快速排序思想：（切分数组大小）

以最后一个元素为游标，将数组分为大于和小于2部分
分别对前、后2部分进行快速排序，直到数组大小为1


//快速排序
void quick(vector<int> &v,int start,int end)
{
	if(start>end) return;//返回条件
	int tmp;
	tmp=v[end];
	for(int i=start,j=end;i<j;)
	{
		while(v[i]<=tmp&&i<j)	i++; //相等情况下也要继续
		v[j]=v[i];
		while(v[j]>=tmp&&i<j)	j--; //相等情况下也要继续
		v[i]=v[j];
	}
	v[i]=tmp;
	quick(v,start,i-1);//递归
	quick(v,i+1,end);
}

void quick_sort(vector<int> &v)
{
	double start=clock();
	quick(v,0,v.size()-1);
	double end=clock();
	sort_print(v,end-start);
}

### 归并排序

归并排序算法思想(分制、递归)

数组分割2部分，并分别对前、后部分进行排序，直到数组大小为1
对前后2部分排序结果进行归并


//归并排序
void merge(vector<int> &v,int low,int mid,int hight)
{
	vector<int> vtmp;
	int i=low,j=mid+1;
	while(i<=mid&&j<=hight)
	{
		while(i<=mid&&v[i]<=v[j])//注意相等的情况
			vtmp.push_back(v[i++]);
		while(j<=hight&&v[j]<v[i])
			vtmp.push_back(v[j++]);
	}
	while(i>mid&&j<=hight)
		vtmp.push_back(v[j++]);
	while(j>hight&&i<=mid)
		vtmp.push_back(v[i++]);
	for(int n=low;n<=hight;n++)
		v[n]=vtmp[n-low];
}

void merge_sort(vector<int> &v1,int low,int hight)
{
	if(low<hight)
	{
		int mid=(low+hight)/2;
		merge_sort(v1,low,mid);
		merge_sort(v1,mid+1,hight);
		merge(v1,low,mid,hight);
	}
}

void merge_2_sort(vector<int> &v)
{
	double start=clock();

	merge_sort(v,0,v.size()-1);

	double end=clock();
	sort_print(v,end-start);
}

基数排序

基数排序的思想：

按照某一基数进行分配，对分配结果进行收集
更换基数，重新上述过程，直到所有基数排序完毕


//按照低位优先，对1-20  2位数进行排序
void distribute(vector<int> &v,vector<vector<int> > &vv,int redix)
{
	for(vector<int>::iterator it=v.begin();it!=v.end();it++)
		vv[(*it)%(int)(pow(10,redix+1))/pow(10,redix)].push_back(*it);
}

void collect(vector<int> &v,vector<vector<int> > &vv,int redix)
{
	int count=0;
	for(int i=0;i<10;i++)
	{
		for(vector<int>::iterator it=vv[i].begin();it!=vv[i].end();it++)
		{
			v[count]=*it;
			count++;
		}
	}
}

void radix_sort(vector<int> &v)
{
	double start=clock();

	vector<vector<int> > vv(10);
	for(int i=0;i<log10(max)+1;i++)
	{
		vv.swap(vector<vector<int> > (10));
		distribute(v,vv,i);
		collect(v,vv,i);
	}
	double end=clock();
	sort_print(v,end-start);
}//	_sleep(0);

总结

8大排序算法写完了，可以说他们各有特色吧！

有很多排序算法将大数组分割成小数组进行排序，使用了“分制、递归”的思想：

快速排序：先整体有序，后部分有序
堆排序：先整体有序，后部分有序
归并排序：先部分有序，后整体有序
基数排序：先部分有序，后整体有序
希尔排序：先部分有序，后整体有序

还有一些使用整体移位的思想：

冒泡排序：先前半部分，直到后整体有序
插入选择：先前半部分，直到后整体有序

参考文献

8大排序算法可视化

小鸟在嗷嗷