常见排序算法（比较排序）及比较

#include<iostream> using namespace std; #include<assert.h>    //稳定性：指两个相同数排序后位置是否变化 //冒泡排序思想：相邻两数据比较交换，外层循环控制次数，内层比较   //void BubbleSort(int *a, size_t len) //{ //	assert(a); //	for (size_t i = 0; i < len - 1; ++i) //	{   //相邻位置数据进行比较，每趟排序都会排出一个最大或最小数 //	for (size_t j = 0; j < len - i - 1; ++j) //	{ //	if (a[j] > a[j + 1]) //	{ //	swap(a[j], a[j + 1]); //	} //	} //	} //} // //鸡尾酒排序思想：即就是双向冒泡排序，一趟排序就可以找到一个最大的和最小元素 void cooktail_sort(int *arr, size_t size) {	assert(arr);	int tail = size - 1;	int i, j ;	for (i = 0; i < tail; ++i)	{	for (int j = tail; j>i; --j)	{	if (arr[j] < arr[j - 1])	{	swap(arr[j], arr[j - 1]);	}	}	++i;	for (j = i; j < tail; ++j)	{	if (arr[j]>arr[j + 1])	swap(arr[j], arr[j + 1]);	}	--tail;	} } //思想：将当前位置的下一个数据插入到前边以有序的块中，再将该数与前边有序的数据逐一比较。 //每插入一个该位置以前的数据都已有序 //void InsertSort(int *a, size_t len)//插入排序 //{ //	assert(a); //	for (size_t i = 0; i < len-1; ++i)//当i=len-1时，tmp访问的位置越界 //	{ //	int end = i; //	int tmp = a[end + 1]; //	while (end >= 0 && a[end]>tmp)//最后一次进去end=0位置要比 //	{ //	a[end + 1] = a[end]; //	--end; //	} //	a[end + 1] = tmp; //	} //} //思想：将一个数组分成两半，再将每一半分半，递归类推，当分出来的只有一个数据时，可认为该小组组内已经有序，然后合并相邻小组，即先递归分解数列，在合并数列 void Mergesort(int *arr, int begin1, int end1, int begin2, int end2) {	//assert(arr);	//if (begin1 >= end1 || begin2 >= end2)	//	return;	//int one = end1 - begin1;	//int two = end2 - begin2;	//int *L = new int[one];//开辟两个数组，一个保存前半部分，一个保存后半部分	//int *R = new int[two];	//int i = 0, j = 0;	//for (; i < one; ++i)	//{	//	L[i] = arr[begin1 + i];	//}	//for (i=0; i < two; ++i)	//{	//	R[i] = arr[begin2 + i];	//}	//int index = begin1;	//for (i = 0, j = 0; index < end2&&i<one&&j<two; ++index)	//{	//	if (L[i] <= R[j])	//	{	//	arr[index] = L[i];	//	++i;	//	}	//	else 	//	{	//	arr[index] = R[j];	//	++j;	//	}	//}	//if (i < one)//如果一个子序已排完，将剩另一个余的数据直接连接到后边	//{	//	for (int k = i; k < one; ++k)	//	arr[index++] = L[k];	//}	//else	//{	//	for (int k = j; k <two; ++k)	//	arr[index++] = R[k];	//}	//delete[] L;	//delete[] R; } //void _merge_sort(int *arr, int begin, int end) //{ //	assert(arr); //	if (begin + 1 < end) //	{ //	int mid = begin + ((end - begin) >> 1); //	_merge_sort(arr, begin, mid); //	_merge_sort(arr, mid, end); //	Mergesort(arr, begin, mid, mid, end); //	//memcpy(src + begin, dst + begin, (end - begin)*sizeof(int)); //	} //	else //	return; //} //两个同样数组，将源数组按序放入目标数组中 void Mergesort(int *src,int *dst, int begin1,int end1,int begin2,int end2) {	assert(src&&dst);	size_t index = begin1;//两个同样大小的数组	while (begin1 < end1 && begin2 < end2)	{	if (src[begin1] < src[begin2])	{	dst[index++] = src[begin1++];	}	else	{	dst[index++] = src[begin2++];	}	}	if (begin1 < end1)	{	while (begin1 < end1)	{	dst[index++] = src[begin1++];	}	}	else	{	while (begin2 < end2)	{	dst[index++] = src[begin2++];	}	} } void _merge_sort(int *src, int *dst, int begin, int end) {	assert(src && dst);	if (begin + 1 < end)	{	int mid = begin + ((end - begin) >> 1);	_merge_sort(src, dst, begin, mid);	_merge_sort(src, dst, mid , end);	Mergesort(src, dst, begin, mid, mid, end);	memcpy(src + begin, dst + begin, (end - begin)*sizeof(int));	}	else	return; } void _Merge_sort(int* src, size_t size) {	int* dst = new int[size];	_merge_sort(src, dst, 0, size);	delete[] dst; } //思想：采用分治法思想，选定一个基数，通过一趟排序将要排序的数组一分为二，其中基数前的数据都比它小，基数后的数据都比它大，然后在将这两部分数据分别进行快排 int QSort(int *a, int left, int right)//快速排序 {	assert(a);	if (left >= right)	return left;	int key = a[right];	int begin = left;	int end = right-1;	while (begin < end)	{	while (begin < end && a[begin] <= key)	begin++;	while (begin < end && a[end] > key)	end--;	if (begin < end)	swap(a[begin], a[end]);	}	if (a[end] >= a[right])	swap(a[end], a[right]);	return end; } //void QuiSort(int* a, int  left, int right)//挖坑法 //{ //	assert(a); //	if (right <= left) //	return; //	int tmp = a[left]; //	int begin = left; //	int end = right; //	while (begin < end) //	{ //	while (begin < end&&a[end] >= tmp) //	end--; //	if (begin < end) //	{ //	a[begin++] = a[end]; //	} //	while (begin < end&&a[begin] <= tmp) //	begin++; //	if (begin < end) //	{ //	a[end--] = a[begin]; //	} //	} //	a[begin] = tmp; //	QuiSort(a, left, begin - 1); //	QuiSort(a, begin + 1, right); //} void QuickSort(int *a, int left,int right) {	assert(a);	if (left < right)	{	int mid = QSort(a, left, right);	QuickSort(a, left, mid - 1);	QuickSort(a, mid + 1, right);	} } //思想：第一次查找最小元素所在位置的下标，与第一个元素交换，之后查找次小元素下标，与第二个元素交换，以此类推 //void SelectSort(int* a, size_t len)//选择排序 //{ //	assert(a); //	size_t min_index ; //	for (size_t i = 0; i < len; ++i) //	{ //	min_index = i; //	for (size_t j = i+1; j < len ; ++j) //	{ //	if (a[min_index] >= a[j]) //	{ //	min_index = j;//找最小元素所在的下标 //	} //	} //	swap(a[min_index], a[i]);//让最小元素位于第i个位置 //	} //} //思想：将数组按某个增量gap分成若干组，每组中记录的下标相差gap，对每组中全部元素进行排序  //，然后用一个较小增量再进行上述循环排序，当增量减到1时，整个要排序的数被分成单个组，排序完成 void Shell_sort(int *a,size_t size) {	assert(a);	int gap = size / 3 + 1;	while (1)	{	for (int i = 0; i < size - gap; ++i)	{	int end = i;	int tmp = a[end + gap];	while ((a[end] > tmp)&&end >= 0)	{	a[end+gap] = a[end];	end -= gap;	}	a[end + gap] = tmp;	}	if (gap == 1)	break;	gap = gap / 3 + 1;//保证gap最后为1时能执行	} } void TestSelectSort() {	int a[10] = { 9, 1, 3, 4, 8, 6, 0, 2, 5, 0 };	int len = sizeof(a) / sizeof(a[0]);	cout << "before:";	for (int i = 0; i < len; ++i)	{	cout << a[i] << " ";	}	cout << endl;	Shell_sort(a,len);	//QuickSort(a, 0, 9);	//SelectSort(a, 10);	cout << "after: ";	for (int i = 0; i < len; ++i)	{	cout << a[i] << " ";	}	cout << endl; } void TestMergeSort() {	int a[10] = { 9, 1, 3, 4, 8, 6, 7, 2, 5, 0 };	int len = sizeof(a) / sizeof(a[0]);	cout << "before:";	for (int i = 0; i < len; ++i)	{	cout << a[i] << " ";	}	cout << endl;	//_merge_sort(a,0, len);	_Merge_sort(a, len);	cout << "after: ";	for (int i = 0; i < len; ++i)	{	cout << a[i] << " ";	}	cout << endl; } //堆排序思想：先建成一个大堆或小堆，堆顶元素是最大（最小），让堆顶元素与最后一个元素交换，数组长度-1，然后向下调整一次，重复上述循环 //template<class T> //class Heap //{ //public: //	Heap(T* a, size_t size) //	{ //	for (size_t i = 0; i < size; ++i) //	{ //	_array.push_back(a[i]); //	} //	for (int i = (_array.size() - 2) / 2; i >= 0;--i) //	{ //	AdjustDown(i,_array.size()); //	} //	} // //	void AdjustDown(int root,int size) //	{ //	size_t lchild = 2 * root + 1; //	while (lchild < size) //	{ //	if ((lchild + 1 < size) && _array[lchild + 1] < _array[lchild]) //	{ //	lchild++; //	} //	if (_array[lchild] < _array[root]) //	{ //	swap(_array[lchild], _array[root]); //	root=lchild; //	lchild = 2 * root + 1; //	} //	else //	break; //	} //	} // //	void AdjustUp(size_t child) //	{ //	size_t root = (child - 1) / 2; //	while (child > 0)//若root和child为size_t型，永远都不会小于0，因此不能用它为循环条件 //	{ //	if (_array[child] < _array[root]) //	{ //	swap(_array[child], _array[root]); //	child = root; //	root = (child - 1) / 2; //	} //	else //	break; //	} //	} // //	void push_elem(const T&x) //	{ //	_array.push_back(x); //	AdjustUp(_array.size() - 1); //	} // //	void Pop_elem() //	{ //	swap(_array[0], _array[(_array.size() - 1])); //	_array.pop_back();//将堆顶元素与最后一个元素交换并删除，再进行向下调整 //	AdjustDown(0); //	} // //	void Heap_Sort() //	{ //	int size = _array.size(); //	while (size>0) //	{ //	swap(_array[0], _array[size-1]); //	cout << _array[size - 1] << " "; //	//_array.pop_back(); //	AdjustDown(0,size-1); //	--size; //	} //	} //	void Display() //	{ //	cout << "heap is:"; //	for (int i = 0; i < _array.size(); ++i) //	{ //	cout << _array[i] << " "; //	} //	cout << endl; //	} //protected: //	vector<T> _array; // //}; //

算法的适用场景及比较：

比较排序：（1）插入（直接插入、希尔排序）、（2）选择（选择排序、堆排序）、（3）交换（冒泡排序、快排）（4）外排序（归并）

1)时间复杂度：

平均性能为O(N^2):插入、选择、冒泡

数据规模小时:直接插入排序较好

数据规模大时：冒泡排序时间代价最高

平均性能为O(NlgN)：堆、快速、归并

数据规模大时：适用堆排序（例：在一千万个数中找最小的前100个数）

数据规模小时：快速排序较好，当小到一定区间使用插入排序

希尔排序平均时间复杂度为O(N^1.3)

稳定性指的是两个相同的数排序后位置是否变化，若无变化则稳定

2).稳定性分析：

稳定：冒泡、插入、归并

不稳定：选择、希尔、堆、快排