#include
using namespace std;
#include
 
 //穩(wěn)定性：指兩個(gè)相同數(shù)排序后位置是否變化
//冒泡排序思想：相鄰兩數(shù)據(jù)比較交換，外層循環(huán)控制次數(shù)，內(nèi)層比較  
//void BubbleSort(int *a, size_t len)
//{
//	assert(a);
//	for (size_t i = 0; i < len - 1; ++i)
//	{   //相鄰位置數(shù)據(jù)進(jìn)行比較，每趟排序都會(huì)排出一個(gè)大或最小數(shù)
//		for (size_t j = 0; j < len - i - 1; ++j)
//		{
//			if (a[j] > a[j + 1])
//			{
//				swap(a[j], a[j + 1]);
//			}
//		}
//	}
//}
//
//雞尾酒排序思想：即就是雙向冒泡排序，一趟排序就可以找到一個(gè)大的和最小元素
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;
	}
}
//思想：將當(dāng)前位置的下一個(gè)數(shù)據(jù)插入到前邊以有序的塊中，再將該數(shù)與前邊有序的數(shù)據(jù)逐一比較。
//每插入一個(gè)該位置以前的數(shù)據(jù)都已有序
//void InsertSort(int *a, size_t len)//插入排序
//{
//	assert(a);
//	for (size_t i = 0; i < len-1; ++i)//當(dāng)i=len-1時(shí)，tmp訪問(wèn)的位置越界
//	{
//		int end = i;
//		int tmp = a[end + 1];
//		while (end >= 0 && a[end]>tmp)//最后一次進(jìn)去end=0位置要比
//		{
//			a[end + 1] = a[end];
//			--end;
//		}
//		a[end + 1] = tmp;
//	}
//}
//思想：將一個(gè)數(shù)組分成兩半，再將每一半分半，遞歸類推，當(dāng)分出來(lái)的只有一個(gè)數(shù)據(jù)時(shí)，可認(rèn)為該小組組內(nèi)已經(jīng)有序，然后合并相鄰小組，即先遞歸分解數(shù)列，在合并數(shù)列
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];//開辟兩個(gè)數(shù)組，一個(gè)保存前半部分，一個(gè)保存后半部分
	//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> 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;
//}
//兩個(gè)同樣數(shù)組，將源數(shù)組按序放入目標(biāo)數(shù)組中
void Mergesort(int *src,int *dst, int begin1,int end1,int begin2,int end2)
{
	assert(src&&dst);
	size_t index = begin1;//兩個(gè)同樣大小的數(shù)組
	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;
}

//思想：采用分治法思想，選定一個(gè)基數(shù)，通過(guò)一趟排序?qū)⒁判虻臄?shù)組一分為二，其中基數(shù)前的數(shù)據(jù)都比它小，基數(shù)后的數(shù)據(jù)都比它大，然后在將這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快排
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);
	}
}

//思想：第一次查找最小元素所在位置的下標(biāo)，與第一個(gè)元素交換，之后查找次小元素下標(biāo)，與第二個(gè)元素交換，以此類推
//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;//找最小元素所在的下標(biāo)
//			}
//		}
//		swap(a[min_index], a[i]);//讓最小元素位于第i個(gè)位置
//	}
//}

//思想：將數(shù)組按某個(gè)增量gap分成若干組，每組中記錄的下標(biāo)相差gap，對(duì)每組中全部元素進(jìn)行排序  //，然后用一個(gè)較小增量再進(jìn)行上述循環(huán)排序，當(dāng)增量減到1時(shí)，整個(gè)要排序的數(shù)被分成單個(gè)組，排序完成
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時(shí)能執(zhí)行
	}
}

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;
}
//堆排序思想：先建成一個(gè)大堆或小堆，堆頂元素是大（最?。?，讓堆頂元素與最后一個(gè)元素交換，數(shù)組長(zhǎng)度-1，然后向下調(diào)整一次，重復(fù)上述循環(huán)
//template
//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型，永遠(yuǎn)都不會(huì)小于0，因此不能用它為循環(huán)條件
//		{
//			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();//將堆頂元素與最后一個(gè)元素交換并刪除，再進(jìn)行向下調(diào)整
//		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 _array;
//
//};
//

算法的適用場(chǎng)景及比較：

成都創(chuàng)新互聯(lián)公司秉承實(shí)現(xiàn)全網(wǎng)價(jià)值營(yíng)銷的理念，以專業(yè)定制企業(yè)官網(wǎng)，網(wǎng)站設(shè)計(jì)制作、成都網(wǎng)站制作，微信平臺(tái)小程序開發(fā)，網(wǎng)頁(yè)設(shè)計(jì)制作，手機(jī)網(wǎng)站開發(fā)，網(wǎng)絡(luò)營(yíng)銷推廣幫助傳統(tǒng)企業(yè)實(shí)現(xiàn)“互聯(lián)網(wǎng)+”轉(zhuǎn)型升級(jí)專業(yè)定制企業(yè)官網(wǎng),公司注重人才、技術(shù)和管理，匯聚了一批優(yōu)秀的互聯(lián)網(wǎng)技術(shù)人才,對(duì)客戶都以感恩的心態(tài)奉獻(xiàn)自己的專業(yè)和所長(zhǎng)。

比較排序：（1）插入（直接插入、希爾排序）、（2）選擇（選擇排序、堆排序）、（3）交換（冒泡排序、快排）（4）外排序（歸并）

1)時(shí)間復(fù)雜度：

平均性能為O(N^2):插入、選擇、冒泡

數(shù)據(jù)規(guī)模小時(shí):直接插入排序較好

數(shù)據(jù)規(guī)模大時(shí)：冒泡排序時(shí)間代價(jià)最高

平均性能為O(NlgN)：堆、快速、歸并

數(shù)據(jù)規(guī)模大時(shí)：適用堆排序（例：在一千萬(wàn)個(gè)數(shù)中找最小的前100個(gè)數(shù)）

數(shù)據(jù)規(guī)模小時(shí)：快速排序較好，當(dāng)小到一定區(qū)間使用插入排序

希爾排序平均時(shí)間復(fù)雜度為O(N^1.3)

穩(wěn)定性指的是兩個(gè)相同的數(shù)排序后位置是否變化，若無(wú)變化則穩(wěn)定

2).穩(wěn)定性分析：

穩(wěn)定：冒泡、插入、歸并

不穩(wěn)定：選擇、希爾、堆、快排

創(chuàng)新互聯(lián)www.cdcxhl.cn，專業(yè)提供香港、美國(guó)云服務(wù)器，動(dòng)態(tài)BGP最優(yōu)骨干路由自動(dòng)選擇，持續(xù)穩(wěn)定高效的網(wǎng)絡(luò)助力業(yè)務(wù)部署。公司持有工信部辦法的idc、isp許可證， 機(jī)房獨(dú)有T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確進(jìn)行流量調(diào)度，確保服務(wù)器高可用性。佳節(jié)活動(dòng)現(xiàn)已開啟，新人活動(dòng)云服務(wù)器買多久送多久。

分享文章：常見排序算法（比較排序）及比較-創(chuàng)新互聯(lián)
文章位置：http://weahome.cn/article/gohsd.html