学习与整理留存。
七大排序算法分析

亲测好用C/C++实现汇总：

#include <iostream>
#include <cstring>
#include <time.h>
#define NUM 50
using namespace std;
 
//交换函数
void swap(int *a,int i,int j)
{
	int tmp = a[i];
	a[i] = a[j];
	a[j] = tmp;
}
//输出函数
void print(int *a)
{
	for(int i=0;i<NUM;i++)
	{
		cout<<a[i]<<" ";
	}
	cout<<endl;
}
//冒泡排序
void bubble_sort(int *a,int low,int high)
{
	if(a == NULL || low >= high || high <= 0 || low < 0)
		return;
	bool flag = true;
	for(int i=0; i<high && flag; ++i)
	{
		flag = false;
		for(int j=0; j<high-i; ++j)
		{
			if(a[j]>a[j+1])
			{
				swap(a,j,j+1);
				flag = true;
			}
		}
	}
}
//选择排序
void select_sort(int *a,int low,int high)
{
	if(a == NULL || low >= high || high <= 0 || low < 0)
		return;
	int minpos;
	for(int i=0;i<high;++i)
	{
		minpos = i;
		for(int j=i+1;j<high+1;++j)
		{
			if(a[j]<a[minpos])
				minpos = j;
 
		}
		if(minpos != i) 
			swap(a,i,minpos);
	}
 
}
//插入排序
void insert_sort(int *a,int low,int high)
{
	if(a == NULL || low >= high || high <= 0 || low < 0)
		return;
	int tmp;
	for(int i=1;i<high+1;++i)
	{
		tmp = a[i];
		int j = i-1;
		for(;j>=0;--j)
		{
			if(a[j]>tmp)
				a[j+1]=a[j];
			else
				break;
		}
		if(j+1 != i)
			a[j+1]=tmp;
	}
}
//快速排序
int partition(int *a,int low,int high)
{
	int pivot = a[low];
	while(low<high)
	{
		while(low<high && a[high]>=pivot)
			--high;
		a[low]=a[high];
		while(low<high && a[low]<=pivot)
			++low;
		a[high]=a[low];
	}
	a[low]=pivot;
	return low;
}
void quick_sort(int *a,int low,int high)
{
	if(a == NULL || low >= high || high <= 0 || low < 0)
		return;
	int pos;
	while(low<high)
	{
		pos=partition(a,low,high);
		quick_sort(a,low,pos-1);
		low = pos+1;
	}
}
//归并排序
void merge(int *a,int low,int mid,int high)
{
	int tmp[high-low+1];
	int lhs=low,rhs=mid+1,k=0;
	while(lhs<=mid && rhs<=high)
	{
		if(a[lhs]<=a[rhs])
			tmp[k++]=a[lhs++];
		else
			tmp[k++]=a[rhs++];
	}
	while(lhs<=mid)
		tmp[k++]=a[lhs++];
	while(rhs<=high)
		tmp[k++]=a[rhs++];
	for(int i=low;i<=high;++i)
		a[i]=tmp[i-low];
}
void merge_sort(int *a,int low,int high)
{
	if(a == NULL || low >= high || high <= 0 || low < 0)
		return;
	int mid = (low+high)>>1;
	merge_sort(a,low,mid);
	merge_sort(a,mid+1,high);
 
	merge(a,low,mid,high); 
}
//堆排序
void adjust(int *a,int low,int high)//大顶堆
{
	int tmp=a[low];
	for(int i=(low<<1)+1;i<high;i=(i<<1)+1)
	{
		if(i<high-1 && a[i]<a[i+1])
			++i;
		if(tmp>=a[i])
			break;
		a[low]=a[i];
		low=i;
	}
	a[low]=tmp;
}
void heap_sort(int *a,int low,int high)
{
	if(a == NULL || low >= high || high <= 0 || low < 0)
		return;
	for(int i=high>>1;i>=0;--i)
		adjust(a,i,high);
	for(int i=high;i>0;--i)
	{
		swap(a,0,i);
		adjust(a,0,i);
	}
}
//希尔排序
void shell_sort(int *a,int low,int high)
{
	if(a == NULL || low >= high || high <= 0 || low < 0)
		return;
 
		/*设置增量*/
	int d = high+1;
	while (d > 1)
	{
		d = (d + 1)>>1;
		for (int i = d; i <= high; ++i)
		{						
			/*要插入的元素*/
			int tmp = a[i];
			/*从已有序序列尾向前寻找合适位置*/
			int j = i-d;
			for (; j >= low; j-=d)
			{
				if (a[j] > tmp)
					a[j + d] = a[j];
				else
					break;
			}
			a[j + d] = tmp;
		}
	}
}
int main()
{
	int a[NUM],b[NUM];
	clock_t start,end;
	srand(time(0));
	cout<<"original array:";
	for(int i=0;i<NUM;i++)
	{
		a[i] = rand() % 400;
		cout<<a[i]<<" ";
	}
	cout<<endl;
	//冒泡排序
	memcpy(b,a,sizeof(a));
	start = clock();
	bubble_sort(b,0,NUM-1);
	end = clock();
	cout<<"bubble_sort:";
	print(b);
	cout<<"time:"<<(double)(end-start)<<"ms"<<endl;
	//选择排序
	memcpy(b,a,sizeof(a));
	start = clock();
	select_sort(b,0,NUM-1);
	end = clock();
	cout<<"select_sort:";
	print(b);
	cout<<"time:"<<(double)(end-start)<<"ms"<<endl;
	//插入排序
	memcpy(b,a,sizeof(a));
	start = clock();
	insert_sort(b,0,NUM-1);
	end = clock();
	cout<<"insert_sort:";
	print(b);
	cout<<"time:"<<(double)(end-start)<<"ms"<<endl;
	//快速排序
	memcpy(b,a,sizeof(a));
	start = clock();
	quick_sort(b,0,NUM-1);
	end = clock();
	cout<<"quick_sort:";
	print(b);
	cout<<"time:"<<(double)(end-start)<<"ms"<<endl;
	//归并排序
	memcpy(b,a,sizeof(a));
	start = clock();
	merge_sort(b,0,NUM-1);
	end = clock();
	cout<<"merge_sort:";
	print(b);
	cout<<"time:"<<(double)(end-start)<<"ms"<<endl;
	//堆排序
	memcpy(b,a,sizeof(a));
	start = clock();
	heap_sort(b,0,NUM-1);
	end = clock();
	cout<<"heap_sort:";
	print(b);
	cout<<"time:"<<(double)(end-start)<<"ms"<<endl;
	//希尔排序
	memcpy(b,a,sizeof(a));
	start = clock();
	shell_sort(b,0,NUM-1);
	end = clock();
	cout<<"shell_sort:";
	print(b);
	cout<<"time:"<<(double)(end-start)<<"ms"<<endl;
	return 0;
}

测试：

original array:295 233 178 260 312 24 81 106 220 184 243 109 383 178 184 325 10 370 363 2 26 314 129 366 8 118 384 152 137 224 292 385 9 23 245 274 399 278 380 219 62 175 280 398 353 64 275 315 34 238 
bubble_sort:2 8 9 10 23 24 26 34 62 64 81 106 109 118 129 137 152 175 178 178 184 184 219 220 224 233 238 243 245 260 274 275 278 280 292 295 312 314 315 325 353 363 366 370 380 383 384 385 398 399 
time:12ms
select_sort:2 8 9 10 23 24 26 34 62 64 81 106 109 118 129 137 152 175 178 178 184 184 219 220 224 233 238 243 245 260 274 275 278 280 292 295 312 314 315 325 353 363 366 370 380 383 384 385 398 399 
time:8ms
insert_sort:2 8 9 10 23 24 26 34 62 64 81 106 109 118 129 137 152 175 178 178 184 184 219 220 224 233 238 243 245 260 274 275 278 280 292 295 312 314 315 325 353 363 366 370 380 383 384 385 398 399 
time:4ms
quick_sort:2 8 9 10 23 24 26 34 62 64 81 106 109 118 129 137 152 175 178 178 184 184 219 220 224 233 238 243 245 260 274 275 278 280 292 295 312 314 315 325 353 363 366 370 380 383 384 385 398 399 
time:5ms
merge_sort:2 8 9 10 23 24 26 34 62 64 81 106 109 118 129 137 152 175 178 178 184 184 219 220 224 233 238 243 245 260 274 275 278 280 292 295 312 314 315 325 353 363 366 370 380 383 384 385 398 399 
time:8ms
heap_sort:2 8 9 10 23 24 26 34 62 64 81 106 109 118 129 137 152 175 178 178 184 184 219 220 224 233 238 243 245 260 274 275 278 280 292 295 312 314 315 325 353 363 366 370 380 383 384 385 398 399 
time:5ms
shell_sort:2 8 9 10 23 24 26 34 62 64 81 106 109 118 129 137 152 175 178 178 184 184 219 220 224 233 238 243 245 260 274 275 278 280 292 295 312 314 315 325 353 363 366 370 380 383 384 385 398 399 
time:7ms