排序的概念：

排序：所謂排序，就是使一串記錄，按照其中的某個(gè)或某些關(guān)鍵字的大小，遞增或遞減的排列起來的操作。
穩(wěn)定性：假定在待排序的記錄序列中，存在多個(gè)具有相同的關(guān)鍵字的記錄，若經(jīng)過排序，這些記錄的相對(duì)次序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，則稱這種排序算法是穩(wěn)定的；否則稱為不穩(wěn)定的。
內(nèi)部排序(內(nèi)存中排序)：數(shù)據(jù)元素全部放在內(nèi)存中的排序。
外部排序(磁盤中排序)：數(shù)據(jù)元素太多不能同時(shí)放在內(nèi)存中，根據(jù)排序過程的要求不能在內(nèi)外存之間移動(dòng)數(shù)據(jù)的排序。

? ? ? ? 注意：此文的八種排序均是內(nèi)部排序，而歸并排序即可以說是內(nèi)部排序，也可以說是外部排序。?

插入排序：

????????基本思想：把待排序的記錄按其關(guān)鍵碼值的大小逐個(gè)插入到一個(gè)已經(jīng)排好序的有序序列中，直到所有的記錄插入完為止，得到一個(gè)新的有序序列 。例如：斗地主。

直接插入排序：

????????當(dāng)插入第i(i>=1)個(gè)元素時(shí)，前面的array[0],array[1],…,array[i-1]已經(jīng)排好序，此時(shí)用array[i]的排序碼與array[i-1],array[i-2],…的排序碼順序進(jìn)行比較，找到插入位置即將array[i]插入，原來位置上的元素順序后移。

直接插入排序?qū)崿F(xiàn)：

//直接插入排序
//時(shí)間復(fù)雜度：O(n^2)  復(fù)雜度范圍：O(n)-O(n^2)
void InsertSort(int* a,int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (a[end] > tmp)
			{
				a[end + 1] = a[end];
			}
			else
			{
				break;
			}
			end--;
		}
		a[end + 1] = tmp;
	}
}

直接插入排序的特性總結(jié)：
????????1. 元素集合越接近有序，直接插入排序算法的時(shí)間效率越高
????????2. 時(shí)間復(fù)雜度：O(N^2)
????????3. 空間復(fù)雜度：O(1)，它是一種穩(wěn)定的排序算法
????????4. 穩(wěn)定性：穩(wěn)定

希爾排序( 縮小增量排序 )：

????????希爾排序法又稱縮小增量法。希爾排序法的基本思想是：先選定一個(gè)整數(shù)，把待排序文件中所有記錄分成個(gè)組，所有距離為的記錄分在同一組內(nèi)，并對(duì)每一組內(nèi)的記錄進(jìn)行排序。然后，重復(fù)上述分組和排序的工作。當(dāng)?shù)竭_(dá)=1時(shí)，所有記錄在統(tǒng)一組內(nèi)排好序。

? ? ? ? 預(yù)排序(gap>1)：大的數(shù)更快的到后面去，小的數(shù)更快到前面，gap越大跳的越快，越不接近有序，gap越小跳的越慢，越接近有序，當(dāng)gap=1時(shí)，完成排序。

//希爾排序
//時(shí)間復(fù)雜度：O(nlogn)  復(fù)雜度范圍：O(n^1.3)-O(nlogn)
void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		//gap = gap / 2;
		gap = gap / 3 + 1;
		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int tmp = a[i + gap];
			while (end >= 0)
			{
				if (a[end] > tmp)
				{
					a[end + gap] = a[end];
				}
				else
				{
					break;
				}
				end -= gap;
			}
			a[gap + end] = tmp;
		}
	}
}

希爾排序的特性總結(jié)：
????????1. 希爾排序是對(duì)直接插入排序的優(yōu)化。
????????2. 當(dāng)gap > 1時(shí)都是預(yù)排序，目的是讓數(shù)組更接近于有序。當(dāng)gap == 1時(shí)，數(shù)組已經(jīng)接近有序的了，這樣就會(huì)很快。這樣整體而言，可以達(dá)到優(yōu)化的效果。我們實(shí)現(xiàn)后可以進(jìn)行性能測(cè)試的對(duì)比。
????????3. 希爾排序的時(shí)間復(fù)雜度不好計(jì)算，因?yàn)間ap的取值方法很多，導(dǎo)致很難去計(jì)算，因此在好些樹中給出的希爾排序的時(shí)間復(fù)雜度都不固定：

《數(shù)據(jù)結(jié)構(gòu)-用面相對(duì)象方法與C++描述》--- 殷人昆

因?yàn)檎兊膅ap是按照Knuth提出的方式取值的，而且Knuth進(jìn)行了大量的試驗(yàn)統(tǒng)計(jì)，我們暫時(shí)就按照：O(n^1.25)到O(1.6^1.25)來算。
????????4. 穩(wěn)定性：不穩(wěn)定

選擇排序：

????????基本思想：每一次從待排序的數(shù)據(jù)元素中選出最小（或最大）的一個(gè)元素，存放在序列的起始位置，直到全部待排序的數(shù)據(jù)元素排完 。

直接選擇排序：

基本思想：

????????1.在元素集合array[i]--array[n-1]中選擇關(guān)鍵碼最大(小)的數(shù)據(jù)元素
????????2.若它不是這組元素中的最后一個(gè)(第一個(gè))元素，則將它與這組元素中的最后一個(gè)（第一個(gè)）元素交換
????????3.在剩余的array[i]--array[n-2]（array[i+1]--array[n-1]）集合中，重復(fù)上述步驟，直到集合剩余1個(gè)元素

//直接選擇排序
//時(shí)間復(fù)雜度：O(n^2)  復(fù)雜度范圍：O(n^2)-O(n^2)
void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

void SelectSort(int* a, int n)
{
	int end = n - 1;
	int begin = 0;
	while (end > begin)
	{
		int maxi = begin;
		int mini = begin;
		for (int i = begin + 1; i <= end ; i++)
		{
			if (a[maxi] < a[i])
			{
				maxi = i;
			}
			if (a[mini] > a[i])
			{
				mini = i;
			}
		}
		Swap(&a[maxi], &a[end]);
		if (mini == end)
		{
			mini = maxi;
		}
		Swap(&a[mini], &a[begin]);

		end--;
		begin++;
	}
}

直接選擇排序的特性總結(jié)：
????????1. 直接選擇排序思考非常好理解，但是效率不是很好。實(shí)際中很少使用
????????2. 時(shí)間復(fù)雜度：O(N^2)
????????3. 空間復(fù)雜度：O(1)
????????4. 穩(wěn)定性：不穩(wěn)定

堆排序：

????????堆排序(Heapsort)是指利用堆積樹（堆）這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法，它是選擇排序的一種。它是通過堆來進(jìn)行選擇數(shù)據(jù)。需要注意的是排升序要建大堆，排降序建小堆。

//堆排序
//時(shí)間復(fù)雜度：O(nlogn)  復(fù)雜度范圍：O(nlogn)-O(nlogn)
//向下調(diào)整（此時(shí)建立大堆）
void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

void Adjustdown(int* a, int n, int parent)
{
	int child = (parent * 2) + 1;
	while (child < n)
	{
		if (child + 1 < n && a[child] < a[child + 1])
		{
			child++;
		}
		if (a[parent] < a[child])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = (parent * 2) + 1;
		}
		else
		{
			break;
		}
	}
}

void HeapSort(int* a, int n)
{
	for (int i = (n - 1 - 1) / 2;i > 0;i--)
	{
		Adjustdown(a, n, i);
	}

	int end = n;
	while (end > 0)
	{
		Swap(&a[0], &a[end - 1]);
		Adjustdown(a, end - 1, 0);
		end--;
	}
}

直接選擇排序的特性總結(jié)：
????????1. 堆排序使用堆來選數(shù)，效率就高了很多。
????????2. 時(shí)間復(fù)雜度：O(N*logN)
????????3. 空間復(fù)雜度：O(1)
????????4. 穩(wěn)定性：不穩(wěn)定

交換排序：

????????基本思想：所謂交換，就是根據(jù)序列中兩個(gè)記錄鍵值的比較結(jié)果來對(duì)換這兩個(gè)記錄在序列中的位置，交換排序的特點(diǎn)是：將鍵值較大的記錄向序列的尾部移動(dòng)，鍵值較小的記錄向序列的前部移動(dòng)。

冒泡排序：

? ? ? ? 每趟將最大的數(shù)排序到范圍內(nèi)最后一個(gè)位置，每趟結(jié)束后減少一個(gè)范圍數(shù)，第二趟將次大的數(shù)排序到倒數(shù)第二個(gè)位置，當(dāng)一趟排序沒有改變數(shù)組順序，說明排序完成，直接退出循環(huán)，否則依次排序完整個(gè)數(shù)組。

//冒泡排序
//時(shí)間復(fù)雜度：O(n^2)  復(fù)雜度范圍：O(n)-O(n^2)
void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

void BubblingSort(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		int change = 0;
		for (int j = 1; j < n - i; j++)
		{
			if (a[j - 1] > a[j])
			{
				Swap(&a[j - 1], &a[j]);
				change = 1;
			}
		}
		if (change == 0)
		{
			break;
		}
	}
}

冒泡排序的特性總結(jié)：
????????1. 冒泡排序是一種非常容易理解的排序
????????2. 時(shí)間復(fù)雜度：O(N^2)
????????3. 空間復(fù)雜度：O(1)
????????4. 穩(wěn)定性：穩(wěn)定

快速排序：

????????快速排序是Hoare于1962年提出的一種二叉樹結(jié)構(gòu)的交換排序方法，其基本思想為：任取待排序元素序列中的某元素作為基準(zhǔn)值，按照該排序碼將待排序集合分割成兩子序列，左子序列中所有元素均小于基準(zhǔn)值，右子序列中所有元素均大于基準(zhǔn)值，然后最左右子序列重復(fù)該過程，直到所有元素都排列在相應(yīng)位置上為止。

hoare版本：

? ? ? ? 右邊節(jié)點(diǎn)從右向左，如果節(jié)點(diǎn)的值大于或大于基元素(a[right] >= a[key])接著向左移動(dòng)，否則到左邊節(jié)點(diǎn)從左向右，如果節(jié)點(diǎn)的值小于或大于基元素(a[left] <= a[key])接著向右移動(dòng)，都停止后，交換當(dāng)前節(jié)點(diǎn)值，循環(huán)結(jié)束后，再將基元素與左節(jié)點(diǎn)交換。然后分治遞歸解決排序問題。

注意(可能做的過程會(huì)遺漏問題)：

? ? ? ? 1.當(dāng)前節(jié)點(diǎn)與基節(jié)點(diǎn)比較要取等于號(hào)，否則節(jié)點(diǎn)值和基節(jié)點(diǎn)值相同時(shí)，會(huì)死循環(huán)；

? ? ? ? 2.注意節(jié)點(diǎn)移動(dòng)時(shí)考慮left < right,否則可能發(fā)生數(shù)組越界；

問：相遇位置比key小，怎么做到的?
答：右邊的先走的做到的。
相遇情況分析:
????????1、R動(dòng)L不動(dòng)，去跟L相遇了（相遇位置是L的位置，L和R在上一輪交換過，交換以后L位置的值比key要?。?

????????2、L動(dòng)R不動(dòng)，去跟R相遇了（R先走，找大比key小的，停下來了，這時(shí)L找大沒有找到跟R相遇了，相遇位置比key?。?/p>

快速排序優(yōu)化：

????????1. 三數(shù)取中法選key
????????2. 遞歸到小的子區(qū)間時(shí)，可以考慮使用插入排序?

//三數(shù)取中
int Middle(int* a,int left, int right)
{
	int mid = (left + right) / 2;
	if (a[left] > a[right])
	{
		if (a[left] > a[mid])
		{
			if (a[right] > a[mid])
			{
				return right;
			}
			else
			{
				return mid;
			}
		}
		else
		{
			return left;
		}
	}
	else
	{
		if (a[right] > a[mid])
		{
			if (a[left] > a[mid])
			{
				return left;
			}
			else
			{
				return mid;
			}
		}
		else
		{
			return right;
		}
	}
}
//hoare方法
int Hoare(int* a, int left, int right)
{
	int mid = Middle(a,left, right);
	Swap(&a[left], &a[mid]);

	int key = left;
	while (left < right)
	{
		while (left < right && a[right] >= a[key])
		{
			right--;
		}
		while (left < right && a[left] <= a[key])
		{
			left++;
		}
		Swap(&a[left], &a[right]);
	}
	Swap(&a[key], &a[left]);
	return left;
}

void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}

	int key = Hoare(a, begin, end);
	QuickSort(a, begin, key - 1);
	QuickSort(a, key + 1, end);
}

?快速排序的特性總結(jié)：
????????1. 快速排序整體的綜合性能和使用場(chǎng)景都是比較好的，所以才敢叫快速排序
????????2. 時(shí)間復(fù)雜度：O(N*logN)

????????3. 空間復(fù)雜度：O(logN)
????????4. 穩(wěn)定性：不穩(wěn)定

挖坑法：

? ? ? ? 先將第一個(gè)元素存放在臨時(shí)變量front中，形成一個(gè)坑位(空),然后重復(fù)hoare法的步驟，最終將存放元素與坑位填上。然后分治遞歸解決排序問題。

//三數(shù)取中
int Middle(int* a,int left, int right)
{
	int mid = (left + right) / 2;
	if (a[left] > a[right])
	{
		if (a[left] > a[mid])
		{
			if (a[right] > a[mid])
			{
				return right;
			}
			else
			{
				return mid;
			}
		}
		else
		{
			return left;
		}
	}
	else
	{
		if (a[right] > a[mid])
		{
			if (a[left] > a[mid])
			{
				return left;
			}
			else
			{
				return mid;
			}
		}
		else
		{
			return right;
		}
	}
}
//挖坑法
int Hold(int* a, int left, int right)
{
	int mid = Middle(a, left, right);
	Swap(&a[left], &a[mid]);

	int front = a[left];
	int hold = left;

	while (left < right)
	{
		while (left < right && a[right] >= front)
		{
			right--;
		}
		a[hold] = a[right];
		hold = right;

		while (left < right && a[left] <= front)
		{
			left++;
		}
		a[hold] = a[left];
		hold = left;
	}
	a[hold] = front;
	return hold;
}

void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}

	int key = Hold(a, begin, end);
	QuickSort(a, begin, key - 1);
	QuickSort(a, key + 1, end);
}

上下指針法：

? ? ? ? 初始時(shí)，prev指針指向序列開頭，cur指針指向prev指針的后一個(gè)位置，當(dāng)a[cur] < a[key]且++prev != cur時(shí)，交換prev和cur節(jié)點(diǎn)，否則cur單獨(dú)+1；循環(huán)結(jié)束后，開頭與prev節(jié)點(diǎn)值交換。然后分治遞歸解決排序問題。

1cur找小，++prev，交換prev和cur的值
prev的有兩種:
????????1、在cur還沒遇到比key大的值時(shí)候，prev緊跟著cur
????????2、在cur還遇到比key大的值時(shí)候，prev在比key大的一組值的前面

????????本質(zhì)是把一段大于key的區(qū)間，推箱子似的往右推，同時(shí)小的甩到左邊去?

//三數(shù)取中
int Middle(int* a,int left, int right)
{
	int mid = (left + right) / 2;
	if (a[left] > a[right])
	{
		if (a[left] > a[mid])
		{
			if (a[right] > a[mid])
			{
				return right;
			}
			else
			{
				return mid;
			}
		}
		else
		{
			return left;
		}
	}
	else
	{
		if (a[right] > a[mid])
		{
			if (a[left] > a[mid])
			{
				return left;
			}
			else
			{
				return mid;
			}
		}
		else
		{
			return right;
		}
	}
}
//上下指針法
int Pointer(int* a, int left, int right)
{
	int mid = Middle(a, left, right);
	Swap(&a[left], &a[mid]);

	int key = left;
	int prev = left;
	int cur = left + 1;

	while (cur <= right)
	{
		if (a[cur] < a[key] && ++prev != cur)
		{
			Swap(&a[prev], &a[cur]);
		}
		cur++;
	}
	Swap(&a[key], &a[prev]);
	return prev;
}
void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}

	int key = Pointer(a, begin, end);
	QuickSort(a, begin, key - 1);
	QuickSort(a, key + 1, end);
}

快速排序非遞歸實(shí)現(xiàn)：

int Pointer(int* a, int left, int right)
{
	int mid = Middle(a, left, right);
	Swap(&a[left], &a[mid]);

	int key = left;
	int prev = left;
	int cur = left + 1;

	while (cur <= right)
	{
		if (a[cur] < a[key] && ++prev != cur)
		{
			Swap(&a[prev], &a[cur]);
		}
		cur++;
	}
	Swap(&a[key], &a[prev]);
	return prev;
}
//快速排序非遞歸
void QuickSortNonR(int* a, int begin, int end)
{
	SL sl;
	SLInit(&sl);

	SLPush(&sl, end);
	SLPush(&sl, begin);

	while (!SLEmpty(&sl))
	{
		int left = SLTTop(&sl);
		SLPop(&sl);

		int right = SLTTop(&sl);
		SLPop(&sl);

		int key = Pointer(a, left, right);
		if (key + 1 < right)
		{
			SLPush(&sl, right);
			SLPush(&sl, key + 1);
		}
		if (left < key - 1)
		{
			SLPush(&sl, key - 1);
			SLPush(&sl, left);
		}
	}
}

快速排序(優(yōu)化)：

? ? ? ? 當(dāng)排序分治遞歸元素剩余十個(gè)的時(shí)候，直接插入排序來完成排序(剩余十個(gè)時(shí)還進(jìn)行分治遞歸，多次遞歸有空間的浪費(fèi))。

void QuickSort2(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	//優(yōu)化：剩余十個(gè)時(shí)直接插入排序
	if (end - begin + 1 > 10)
	{
		int key = Pointer(a, begin, end);
		QuickSort2(a, begin, key - 1);
		QuickSort2(a, key + 1, end);
	}
	else
	{
		InsertSort(a + begin,end - begin +1);
	}
}

歸并排序：

? ? ? ? 基本思想：歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide andConquer）的一個(gè)非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個(gè)子序列有序，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表，稱為二路歸并。

//歸并排序(遞歸)
void _MergeSort(int* a,int* tmp,int begin,int end)
{
	if (begin >= end)
	{
		return;
	}
	int mid = (begin + end) / 2;

	_MergeSort(a, tmp, begin, mid);
	_MergeSort(a, tmp, mid + 1, end);

	int begin1 = begin;
	int end1 = mid;
	int begin2 = mid + 1;
	int end2 = end;
	int cur = begin;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
		{
			tmp[cur++] = a[begin1++];
		}
		else
		{
			tmp[cur++] = a[begin2++];
		}
	}
	while (begin1 <= end1)
	{
		tmp[cur++] = a[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[cur++] = a[begin2++];
	}

	memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}

//歸并排序
void MergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		return;
	}

	_MergeSort(a, tmp, 0, n - 1);

	free(tmp);
}

歸并排序的特性總結(jié)：
????????1. 歸并的缺點(diǎn)在于需要O(N)的空間復(fù)雜度，歸并排序的思考更多的是解決在磁盤中的外排序問題。
????????2. 時(shí)間復(fù)雜度：O(N*logN)
????????3. 空間復(fù)雜度：O(N)
????????4. 穩(wěn)定性：穩(wěn)定

歸并排序非遞歸實(shí)現(xiàn)：

//歸并排序非遞歸
void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		return;
	}

	int gap = 1;
	while (gap < n)
	{
		for (int i = 0; i < n; i += 2 * gap)
		{
			int begin1 = i;
			int end1 = i + gap - 1;
			int begin2 = i + gap;
			int end2 = i + 2 * gap - 1;
			int cur = i;

            if (begin2 > n - 1)
			{
				break;
			}
			if (end2 > n - 1)
			{
				end2 = n - 1;
			}

			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] < a[begin2])
				{
					tmp[cur++] = a[begin1++];
				}
				else
				{
					tmp[cur++] = a[begin2++];
				}
			}
			while (begin1 <= end1)
			{
				tmp[cur++] = a[begin1++];
			}
			while (begin2 <= end2)
			{
				tmp[cur++] = a[begin2++];
			}
			memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));
		}
		gap *= 2;
	}
	free(tmp);
}

非比較排序：

????????基本思想：計(jì)數(shù)排序又稱為鴿巢原理，是對(duì)哈希直接定址法的變形應(yīng)用。

操作步驟：
????????1. 統(tǒng)計(jì)相同元素出現(xiàn)次數(shù)
????????2. 根據(jù)統(tǒng)計(jì)的結(jié)果將序列回收到原來的序列中

計(jì)數(shù)排序：

? ? ? ? ?將每個(gè)元素有多少個(gè)，記錄到一個(gè)數(shù)組中，然后從這個(gè)數(shù)組中依次遍歷打印出來。

//計(jì)數(shù)排序
void CountSort(int* a, int n)
{
	int max = a[0];
	int min = a[0];
	for (int i = 0; i < n; i++)
	{
		if (a[i] > max)
		{
			max = a[i];
		}
		if (a[i] < min)
		{
			min = a[i];
		}
	}
    //范圍
	int range = max - min + 1;

	int* count = (int*)calloc(range,sizeof(int));
	if (count == NULL)
	{
		perror("ralloc fail");
		return;
	}

	for (int i = 0; i < n; i++)
	{
		count[a[i] - min]++;
	}

	int j = 0;
	for (int i = 0; i < range; i++)
	{
		while (count[i]--)
		{
			a[j++] = i + min;
		}
	}
}

計(jì)數(shù)排序的特性總結(jié)：
????????1. 計(jì)數(shù)排序在數(shù)據(jù)范圍集中時(shí)，效率很高，但是適用范圍及場(chǎng)景有限。
????????2. 時(shí)間復(fù)雜度：O(MAX(N,范圍))
????????3. 空間復(fù)雜度：O(范圍)

? ? ? ? 4. 穩(wěn)定性：穩(wěn)定

排序算法復(fù)雜度及穩(wěn)定性分析：

穩(wěn)定性：

? ? ? ? 穩(wěn)定性：指的是當(dāng)未排序前，數(shù)組中有相同元素，在排序完成后沒有改變相同元素的相對(duì)位置的情況下，說明該排序穩(wěn)定。反之，不穩(wěn)定。（考試分?jǐn)?shù)相同，先交卷的在前面）

例：

? ? ? ? 排序前：2? 5? 9? 6? 5? 3? 7? 1

? ? ? ? 排序后：1? 2? 3? 5? 5? 6? 7? 9? ? 說明此排序算法穩(wěn)定！

? ? ? ? 反之：排序后：1? 2? 3? 5? 5? 6? 7? 9? ? 說明此排序算法不穩(wěn)定！

不穩(wěn)定分析：

????????希爾排序：預(yù)排序時(shí)，相同的元素分配到不同的組中。

????????選擇排序： 例：3? 3? 1? 1;這種情況第一個(gè)3已經(jīng)被交換位置。

????????堆排序：例：9? 8? 9? 6? 2；這種情況按大堆排升序，第一個(gè)調(diào)換到最后以后就不穩(wěn)定了。

????????快速排序：例：5?8 5?4?5；這種因?yàn)橄嗤詻]有去交換，到結(jié)束時(shí)第一個(gè)與left交換時(shí)不穩(wěn)定。

擴(kuò)展：

????????因?yàn)橐韵屡判?，?shí)用性低，除了考試以外，基本上不會(huì)進(jìn)行考察，工作也基本用不上，就不多描述。

????????基數(shù)排序：按個(gè)，十，百，千位依次進(jìn)行排序的算法。

? ? ? ? 桶排序：

以上就是個(gè)人學(xué)習(xí)線性表的個(gè)人見解和學(xué)習(xí)的解析，歡迎各位大佬在評(píng)論區(qū)探討！

感謝大佬們的一鍵三連！?感謝大佬們的一鍵三連！?感謝大佬們的一鍵三連！?

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文章來源地址http://www.zghlxwxcb.cn/news/detail-716568.html

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)：一篇拿捏十大排序(超詳細(xì)版)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！