文章目錄

• 前言
• 1.插入排序
• 2.希爾排序
• 3.選擇排序
• 4.堆排序
• 5.冒泡排序
• 6.快速排序
• • hoare方式版本快排實(shí)現(xiàn)
  • 非遞歸方式實(shí)現(xiàn)快排
  • 挖坑法實(shí)現(xiàn)快排
  • 前后指針法(雙指針法）
  • 快排的各種優(yōu)化
  • • 1.減少后幾層的遞歸調(diào)用(小區(qū)間優(yōu)化）
    • 2.三數(shù)取中優(yōu)化
  • 3.三路劃分(處理大量重復(fù)數(shù)據(jù)）
• 7.歸并排序
• • 1.遞歸實(shí)現(xiàn)歸并排序
  • 2.歸并排序的非遞歸實(shí)現(xiàn)
• 8.計(jì)數(shù)排序
• 9.額外知識關(guān)于各類排序算法的穩(wěn)定性
• 10.總結(jié)

創(chuàng)新互聯(lián)專注于企業(yè)營銷型網(wǎng)站建設(shè)、網(wǎng)站重做改版、天鎮(zhèn)網(wǎng)站定制設(shè)計(jì)、自適應(yīng)品牌網(wǎng)站建設(shè)、HTML5、商城網(wǎng)站建設(shè)、集團(tuán)公司官網(wǎng)建設(shè)、外貿(mào)網(wǎng)站制作、高端網(wǎng)站制作、響應(yīng)式網(wǎng)頁設(shè)計(jì)等建站業(yè)務(wù)，價(jià)格優(yōu)惠性價(jià)比高，為天鎮(zhèn)等各大城市提供網(wǎng)站開發(fā)制作服務(wù)。前言

排序是對一種比較常見的對數(shù)據(jù)處理方式。排序算法在計(jì)算機(jī)領(lǐng)域中應(yīng)用廣泛且重要。本文主要對幾種比較經(jīng)典的排序算法進(jìn)行講解，之前對冒泡排序和堆排序有過講解，本文也會(huì)回顧一下這兩種排序算法。(本文動(dòng)圖均來自菜鳥教程，如有侵權(quán)聯(lián)系可刪）

---

1.插入排序

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

其實(shí)我們玩撲克牌的時(shí)候就用了插入排序的思想，在起牌時(shí)數(shù)值較大的排往后放，數(shù)值較小的牌往前放。起排結(jié)束后手里的牌就按一定的順序排列了。

聯(lián)想玩牌時(shí)插入，6暫時(shí)放在13的后面，從尾到頭進(jìn)行比較。6比13大，13到6的位置上，6往前走到13原來的位置接著比較；6比10大，6往前走，10往后走，接著比較；6比9小，6往前走，9往后走，接著比較。6比7小，7往后走，6往前走，接著比較；6比4大，6走到了合適的位置，插入過程結(jié)束。

這是模擬一次插入過程，當(dāng)然我知道數(shù)組中數(shù)據(jù)不一定是有序的，所以我們假設(shè)第一個(gè)元素就是有序的，依次對往后的數(shù)據(jù)進(jìn)行插入排序，整個(gè)插入插入過程就是有序的了。這就相當(dāng)于假設(shè)起牌時(shí)第一張就是有序的，后序起到的牌依次進(jìn)行調(diào)整。

我們先將的一趟的插入寫出來
對比著上面圖中的插入流程，一躺插入就可以確定了。完整的插入流程是從第一個(gè)元素開始重復(fù)上述插入比較流程，所以外層套個(gè)循環(huán)整個(gè)插入排序就寫出來了。

---

完整代碼示例

void InsertSort(int* a, int n)
{for (int i = 0;iint end = i;
		//防止越界i= 0)
	    {	if (a[end] >tem)
			{		a[end + 1] = a[end];
				end--;
			}
			else
			{		break;
			}
		}
		a[end+1] = tem;
	}
}

插入排序的時(shí)間復(fù)雜度我們分析一下

總的來說插入排序的時(shí)間復(fù)雜度是O(n^2),空間復(fù)雜度是O(1)

---

2.希爾排序

希爾排序法又稱縮小增量法。希爾排序法的基本思想是：先選定一個(gè)整數(shù)作為間距，把待排序數(shù)據(jù)按間距分成個(gè)組，并對每一組內(nèi)的記錄進(jìn)行插入排序。然后不斷縮小間距重復(fù)上述分組和排序的工作。當(dāng)?shù)介g距==1時(shí)，進(jìn)行最后一次排序。

上述的操作基本可以分為兩步：1.預(yù)排序（不斷縮小間距分組進(jìn)行插入排序）;2.間距為1時(shí)最后一次排序（也就是直接進(jìn)行插入排序）

我們畫圖分析一下：

這個(gè)間距劃分只要數(shù)組中元素位置滿足條件就可以歸為同一組。圖中第一組從2位置劃到3位置時(shí)，3往后的間距不夠5了所以就沒有接著劃分了。第二組劃分從2開始接著是7，最后到10，10后面只有一個(gè)位置，不滿足間距劃分條件。

---

那么代碼怎么寫呢？希爾排序本質(zhì)還是采用插入排序，唯一的區(qū)別就是插入排序的區(qū)間被劃分了出來。確定了排序區(qū)間希爾排序就寫出來了。我們從圖可以看出其實(shí)起始還是從第一個(gè)元素開始，分組時(shí)第一個(gè)元素后面的第二個(gè)元素就是要插入的元素，第一次區(qū)間劃分時(shí)，2后面要插入的是3；第二次區(qū)間劃分時(shí)，分組中2后面是7。通過觀察發(fā)現(xiàn)插入的元素和第一個(gè)元素相差了一個(gè)間距的距離。這就確定了end后面不再是加1，而是在end基礎(chǔ)上加上間距。

代碼示例

void ShellSort(int* arr, int n)
{int gap = n;
	while (gap >1)
	{//這個(gè)間距+1確保最后一次gap為1
		gap = gap / 3 + 1;
		for (int i = 0; i< n - gap; i++)
		{	int end = i;
			int tem = arr[end + gap];
			while (end >= 0)
			{		if (tem< arr[end])
				{arr[end + gap] = arr[end];
					end-=gap;
				}
				else
				{break;
				}
			}
			arr[end + gap] = tem;
		}
	}
}

我們發(fā)現(xiàn)如果gap==1，上述代碼就是插入排序。通過gap分組預(yù)排序會(huì)使數(shù)據(jù)越來越趨近于有序。當(dāng)間距gap越來越小時(shí)，數(shù)據(jù)也會(huì)越來越有序。數(shù)據(jù)越有序，插入排序的性能越好。希爾排序就是根據(jù)這一特點(diǎn)在插入排序的基礎(chǔ)上延申出了預(yù)排序。
因?yàn)槊看蝕ap先進(jìn)行更新再執(zhí)行排序邏輯，循環(huán)條件也應(yīng)該是gap>1,不用取等。當(dāng)然gap每次縮小3倍所以為了保證最后的結(jié)果為1，需要加1。如果gap=gap/2就不用加1，這樣除2，無論gap為何值最后的結(jié)果一定是1.

希爾排序的時(shí)間復(fù)雜度很不算，需要用到高等數(shù)學(xué)進(jìn)行推導(dǎo)。所以只用記住希爾排序的時(shí)間復(fù)雜度為O(n^1.3),空間復(fù)雜度為O(1)

---

3.選擇排序

基本思想：每一次從待排序的數(shù)據(jù)元素中選出最?。ɑ虼螅┑囊粋€(gè)元素，存放在序列的起始位置，直到全部待排序的數(shù)據(jù)元素排完 。

選擇排序就是直接選出大或最小的元素放在合適的位置
不過選擇排序選大元素和最小元素可以同時(shí)進(jìn)行，畫圖詳解一下。

從圖中可以看出選擇排序就是每次選再一個(gè)區(qū)間范圍中選出大或者最小的元素移動(dòng)到區(qū)間邊界的位置上去。每次處理一趟過后，區(qū)間就會(huì)相應(yīng)的縮小。直到區(qū)間范圍重合時(shí)，這個(gè)排序過程就結(jié)束了。

---

代碼示例

//交換函數(shù)
void swap(int* a, int* b)
{int tem = *a;
	*a = *b;
	*b = tem;
}
void SelectSort(int* a, int n)
{int begin = 0, end = n - 1;
	while (begin< end)
	{int max = begin, min = begin;
		//找最小元素和大元素的位置
		for (int i = begin + 1; i<= end; i++)
		{	if (a[max]< a[i])
			{		max = i;
			}
			if (a[min] >a[i])
			{		min = i;
			}
		}
		swap(&a[begin], &a[min]);
		//防止begin和max重合
		if (begin == max)
		{	max = min;
		}
		swap(&a[end], &a[max]);
		end--;
		begin++;
	}
}

這個(gè)交換函數(shù)需要自己寫。同時(shí)如果begin剛好和max重合或者end和min重合，因?yàn)榻粨Q順序的問題可能會(huì)造成bug，所以重要單獨(dú)處理，只針對一種情況判斷處理即可。根據(jù)代碼中的交換順序設(shè)置不同的判斷，我這里是先交換的begin和min位置上的元素，所以判斷的是begin和max.
選擇排序的時(shí)間復(fù)雜度是O(n^2)，其實(shí)結(jié)合選擇排序思想來看，它的時(shí)間復(fù)雜度也就是等差數(shù)列求和，空間復(fù)雜度O(1).

---

4.堆排序

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

堆排序之前的博客有過介紹，這里就不畫圖分析了。它實(shí)現(xiàn)就是兩步，第一步對對數(shù)據(jù)建堆，第二步每次將堆頂數(shù)據(jù)換到末尾位置進(jìn)行堆調(diào)整。

代碼示例

//向下調(diào)整
void AdjustDown(int* arr, int n,int parents)//向下調(diào)整
{//n的作用只是用來約束孩子和雙親防止越界
    int child = parents * 2 + 1;
    while (child< n)
    {//保證child是指向大孩子的
        if (child + 1< n && arr[child + 1] >arr[child])
        {child++;
        }
        if (arr[parents]< arr[child])
        {Swap(&arr[parents], &arr[child]);
            parents = child;
            child = parents * 2 + 1;
        }
        else
        {break;
        }
    }
    return;
}

//交換函數(shù)
void Swap(int* a, int* b)
{int tem = *a;
	*a = *b;
	*b = tem;
}
void HeapSort(int* a, int n)
{//建堆
    for (int i = (n - 1 - 1) / 2; i>=0; i--)
    {AdjustDown(a, n, i);
    }
    int end = n - 1;
    while (end >0)
    {Swap(&a[0], &a[end]);
        AdjustDown(a, end, 0);
        end--;
    }
    return;
}

堆排序時(shí)間復(fù)雜度是O(N*logN),空間復(fù)雜度O(1).
堆排序具體介紹可以看之前寫的關(guān)于實(shí)現(xiàn)堆的博客

---

5.冒泡排序

基本思想：重復(fù)地走訪過要排序的數(shù)列，一次比較兩個(gè)元素，如果它們的順序錯(cuò)誤就把它們交換過來。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說該數(shù)列已經(jīng)排序完成。這個(gè)算法的名字由來是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端。

每趟冒泡排序可以將搞定一個(gè)數(shù)，也就是讓較大的數(shù)依次到右端。這個(gè)冒泡排序排序我之前的博客也有介紹，這里就不畫圖分析了。

代碼示例

void  BubbleSort(int* a, int n)
{for (int i = 0; i< n; i++)
	{for (int j = 1; j< n - i; j++)
		{	if ( a[j - 1]>a[j])
			{		int tem = a[j - 1];
				a[j - 1] = a[j];
				a[j] = tem;
			}
		}
	}
}

冒泡排序算是一種比較簡單的排序算法，時(shí)間復(fù)雜度O(n^2),空間復(fù)雜度為O(1)。關(guān)于冒泡排序的具體介紹可以翻我之前的博客。

---

6.快速排序

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

hoare方式版本快排實(shí)現(xiàn)

快速排序是排序中的重點(diǎn)之一，同時(shí)排序有多個(gè)版本我們依次分析，首先來畫圖分析一下hoare版本的排序。

hoare版本的快排就是先選一個(gè)元素作為key值，然后用兩個(gè)變量left right分別指向數(shù)據(jù)的起始位置和末尾位置。該位置的數(shù)據(jù)元素分別和key值進(jìn)行比較。left指向的值如果大于key就停下來，等right停下來的時(shí)候和right位置處的元素交換，否則就往下走。right指向的值如果小于key值就停下來，等left停下來來的時(shí)候和left位置處的元素交換，否則right就往下走。直到right和left相遇，相遇之后，如果最開始選的key是最左邊的元素，就把key位置和left位置上的元素進(jìn)行交換，否則就是right位置。同時(shí)，注意如果選的是left做key，那么right先走比較，否則就是right后走。然后就是遞歸處理了。

但是要注意選誰做key，如果選最左邊的位置的元素做key，右邊一定先走。反之亦然。left和right并不是同時(shí)走的。如果左邊做key，right先走。遇到小于key的，right停住，left開始走，遇到大于key的值也停住，然后left和right位置上的元素進(jìn)行交換。然后接著right先走，重復(fù)上述的過程。直到left和right相遇，key和left位置上的元素交換。

---

代碼示例

void swap(int* a, int* b)
{int tem = *a;
	*a = *b;
	*b = tem;
}
void QuickSort_1(int* a, int begin, int end)
{if (begin >end)
	{return;
	}
	int left = begin;
	int right = end;
	int key = left;
	while (left< right)
	{//左邊作為key，右邊先走,反之亦然
		while (left< right && a[right] >= a[key])
		{	right--;
		}
		while (left< right && a[left]<= a[key])
		{	left++;
		}
		swap(&a[left], &a[right]);
	}
	swap(&a[left], &a[key]);
	key = left;
	QuickSort_1(a, begin, key - 1);
	QuickSort_1(a, key + 1, end);
}

這個(gè)遞歸條件就是begin>end，隨著區(qū)間不斷分隔，區(qū)間會(huì)范圍會(huì)越縮越小。當(dāng)區(qū)間范圍不存在時(shí)就停止遞歸。誰做key，最后key就和誰交換。key就更新成誰，誰就后走。

left

快排的實(shí)現(xiàn)很像二叉樹的前序遍歷，先將要一趟排序處理的情況情況分析確定好，同時(shí)，確定遞歸邊界條件。剩下的就是對左半?yún)^(qū)間和對右半?yún)^(qū)間的遞歸處理。

---

分析一下這個(gè)代碼時(shí)間復(fù)雜度。

---

快排很有優(yōu)化方式，在介紹優(yōu)化方式之前我們先介紹其他幾種快排的實(shí)現(xiàn)。

---

非遞歸方式實(shí)現(xiàn)快排

遞歸就是程序的重復(fù)調(diào)用，也就是說對每個(gè)問題的處理方式都是一樣的。對于快排的遞歸來說，每次排序的流程都是確定好的，遞歸主要是為了對分隔出的區(qū)間進(jìn)行處理。我們只用借助別的數(shù)據(jù)結(jié)構(gòu)將每次劃分的區(qū)間先存儲起來，在對每個(gè)區(qū)間進(jìn)行同樣的排序處理即可。遞歸我們用的是函數(shù)棧幀，非遞歸實(shí)現(xiàn)我們就借助棧這種數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)。

為了使代碼邏輯更加清晰，我們將排序處理邏輯封裝成一個(gè)函數(shù)。在快排內(nèi)調(diào)用這個(gè)函數(shù)對區(qū)間進(jìn)行處理即可。

代碼示例

int QuickSort_2(int* a, int begin, int end)
{int left = begin;
	int right = end;
	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[left], &a[key]);
	return left;
}
void QuickSortNonR(int* a, int begin, int end)
{//先建立棧
	Stack st;
	StackInit(&st);
	StackPush(&st, begin);
	StackPush(&st, end);
	while (!StackEmpty(&st))
	{//先進(jìn)去的是左區(qū)間后進(jìn)的右區(qū)間，出來是先出右邊區(qū)間后出左區(qū)間
		int right = StackTop(&st);
		StackPop(&st);
		int left = StackTop(&st);
		StackPop(&st);
		int key = QuickSort_2(a, left, right);
		//if判斷相當(dāng)于之前的遞歸中止條件
		//分割成只有一個(gè)數(shù)的區(qū)間事就不用繼續(xù)分隔割
		if (left< key - 1)
		{//前面已經(jīng)確定先左后右，接著按這個(gè)順序
			StackPush(&st, left);
			StackPush(&st, key - 1);
		}
		if (key + 1< right)
		{	StackPush(&st, key + 1);
			StackPush(&st, right);
		}
	}
	StackDestroy(&st);
}

我們先將數(shù)組的整個(gè)的區(qū)間范圍入棧，在出棧區(qū)間調(diào)用函數(shù)排序處理。處理完了之后再進(jìn)左右區(qū)間，直到棧中數(shù)據(jù)為空為止。注意入棧的順序。先入棧的后出棧。代碼中先入棧的是左邊界，后入棧的右邊界。所以先出棧的是右邊界，后出的左邊界。同時(shí)注意，每次數(shù)據(jù)出棧后都要Pop掉。之前遞歸的時(shí)候有遞歸邊界條件，現(xiàn)在是非遞歸所以要保證區(qū)間范圍的合法性，需要添加if判斷，合法的區(qū)間邊界才能入棧。

c語言中沒有不提供數(shù)據(jù)結(jié)構(gòu)的接口，所以需要直接實(shí)現(xiàn)棧的相關(guān)接口。我之前的博客有講棧的相關(guān)實(shí)現(xiàn)。

---

挖坑法實(shí)現(xiàn)快排

挖坑法是在hoare版本的基礎(chǔ)進(jìn)行的變形。其中元素比較的過程和left right移動(dòng)過程差不多類似，但是它不涉及交換。它是用元素覆蓋也就是賦值的形式更新數(shù)據(jù)。挖洞法會(huì)先找一個(gè)位置為坑位，如果left和rigt指向的元素不滿足條件了就會(huì)將這個(gè)元素放入坑位。同時(shí)更新坑位，最后left和right相遇時(shí)，將key放入坑位。一般最開始選擇最左邊的位置作為坑位。

/挖坑法寫快排 元素覆蓋挪動(dòng)，不涉及位置上的元素交換
void QuickSort_2(int* a, int begin, int end)
{if (begin >end)
	{return;
	}
	int left = begin;
	int right = end;
	int key = a[begin];
	int hole = begin;
	while (left< right)
	{//左邊做key，右邊先走
		while (left< right && a[right] >= key)
		{	right--;
		}
		a[hole] = a[right];
		hole = right;
		while (left< right && a[left]<= key)
		{	left++;
		}
		a[hole] = a[left];
		hole = left;
	}
	a[hole] = key;
	int index = hole;
	QuickSort_2(a, begin, index - 1);
	QuickSort_2(a, index + 1, end);
}

挖坑法比較容易理解，不滿足條件的就放入坑位，之后更新坑位。left和right相遇后，只用將key填入坑位，坑位是最后為key準(zhǔn)備的。

---

前后指針法(雙指針法）

雙指針實(shí)現(xiàn)快排就是用兩個(gè)變量，一前一后。如果走在前面的變量指向的元素小于key，后面的變量就向前一步走，再將這兩個(gè)變量指向的元素進(jìn)行交換。之后前面的指針接著走，就是說無論何種情況前面的變量肯定會(huì)往前走。后面的變量只有在特定情況下才能走一步。前面的變量走完所有的位置后，key和后面變量指向的元素進(jìn)行交換。

畫圖分析

可以看出這樣的實(shí)現(xiàn)方法每次排序也可以分割區(qū)間和排定一個(gè)key。

---

代碼示例

void swap(int* a, int* b)
{int tem = *a;
	*a = *b;
	*b = tem;
}
void QuickSort_3(int* a, int begin, int end)
{if (begin >end)
	{return;
	}
	int cur = begin + 1;
	int prev = begin;
	int key = begin;
	while (cur<= end)
	{if (a[cur]< a[key] && ++prev != cur)
		{	swap(&a[cur], &a[prev]);
		}
		cur++;
	}
	swap(&a[prev], &a[key]);
	QuickSort_3(a, begin, prev - 1);
	QuickSort_3(a, prev + 1, end);
}

現(xiàn)在區(qū)間相當(dāng)于分割成了[begin,prev-1] prev [prev+1,end]。代碼中可以看到加了++prev與cur判斷，這樣可以過濾無用的交換。

---

快排的各種優(yōu)化 1.減少后幾層的遞歸調(diào)用(小區(qū)間優(yōu)化）

遞歸調(diào)用可能有棧溢出的風(fēng)險(xiǎn)。我們可以在遞歸的最后幾層進(jìn)行插入排序的處理。對分割出來的小區(qū)間進(jìn)行優(yōu)化。之前提到快排的遞歸調(diào)用類似于二叉樹的前序遍歷，每次遞歸調(diào)用都是以2的指數(shù)倍增長，所以最后幾層的調(diào)用占總調(diào)用的次數(shù)比例是很大的，最后3到5層的調(diào)用大概占總次數(shù)的80%，因此在最后幾層不用遞歸采用插入排序可以大大較少遞歸次數(shù)。

---

代碼示例

void swap(int* a, int* b)
{int tem = *a;
	*a = *b;
	*b = tem;
}
void QuickSort_1_2(int* a, int begin, int end)
{if (begin >end)
	{return;
	}
	// 小區(qū)間用直接插入替代，減少遞歸調(diào)用次數(shù)

	else if ((end - begin + 1)< 15)
	{//插入排序的第二個(gè)參數(shù)是元素個(gè)數(shù)需要加1
		//第二個(gè)參數(shù)的數(shù)組的起始空間地址，隨著區(qū)間的分割起始空間就是a+begin
		InsertSort(a + begin, end - begin + 1);
	}
	int mid = GetMidIndex(a, begin, end);
	swap(&a[begin], &a[mid]);
	int left = begin;
	int right = end;
	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[left], &a[key]);
	key = left;
	QuickSort_1_2(a, begin, key - 1);
	QuickSort_1_2(a, key + 1, end);
}

插入排序是需要自己去實(shí)現(xiàn)的，代碼中間區(qū)間范圍控制在15，也就是如果劃分的區(qū)間中有15個(gè)以內(nèi)個(gè)數(shù)的數(shù)據(jù)就進(jìn)行插入排序。

---

2.三數(shù)取中優(yōu)化

之前分析快排時(shí)間復(fù)雜度提到了如果每次選取的key都是較為中間的值，快排的效果非常好。所以我們將begin end和這個(gè)區(qū)間的中間位置的元素進(jìn)行比較，選取中間的元素作為key。

代碼示例

//得到較為中間的數(shù)
int GetMidIndex(int* a, int begin, int end)
{int mid = begin + (end - begin) / 2;
	if (a[begin]< a[mid])
	{if (a[mid]< a[end])
		{	return mid;
		}
		else if (a[begin] >a[end])
		{	return begin;
		}
		else
		{	return end;
		}
	}
	else
	{if (a[begin]< a[end])
		{	return begin;
		}
		else if (a[mid] >a[end])
		{	return mid;
		}
		else
		{	return end;
		}
	}
}
//三路取中優(yōu)化快排
void QuickSort_1_1(int* a, int begin, int end)
{if (begin>end)
	{return;
	}
	int mid = GetMidIndex(a, begin, end);
	swap(&a[begin], &a[mid]);
	int left = begin;
	int right = end;
	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[left], &a[key]);
	key = left;
	QuickSort_1_1(a, begin, key - 1);
	QuickSort_1_1(a, key + 1, end);
}

這個(gè)3數(shù)取中就是在begin和end以及mid這3個(gè)位置選取中間大的元素作為key。但是實(shí)際上還是可以進(jìn)行優(yōu)化，這個(gè)mid是固定位置，mid位置應(yīng)該更隨機(jī)一定比較好，這樣選到中間數(shù)作為key的概率就會(huì)大大增加。

可以做出如下改動(dòng)：

int mid = begin + rand()%(end-begin+1);

rand() % (b-a+1)+ a ，表示 a~b 之間的一個(gè)隨機(jī)整數(shù)。這樣產(chǎn)生的key就會(huì)較為隨機(jī)了。關(guān)于rand函數(shù)可以在官網(wǎng)文檔中進(jìn)行查閱。

---

3.三路劃分(處理大量重復(fù)數(shù)據(jù)）

三路劃分大概的思想就是將劃分3個(gè)區(qū)間 [begin，key-1] [key] [key+1,end]?？此迫齻€(gè)區(qū)間的劃分和之前沒區(qū)別，但是key這個(gè)區(qū)間中放入的都是和key相同的元素。這樣能夠處理有大量相同數(shù)據(jù)的情況，如果不將和key相同的元素劃分到同一區(qū)間中，一旦出現(xiàn)大量重復(fù)的元素，快排的效率其實(shí)是大幅度降低的。

大致思路就是最開始cur指向left前一個(gè)位置，cur指向的元素大于key就和right交換，right退一步，cur不動(dòng)。如果cur指向的元素小于key，cur和left交換，left和cur都向前一步。如果cur指向元素等于key,cur往前走就可以了。

代碼示例

void QuickSort(int* a, int begin, int end)
{if (begin >end)
	{return;
	}
	int left = begin;
	int right = end;
	int key = a[begin];
	int cur = begin + 1;
	while (cur<= right)
	{if (a[cur]< key)
		{	swap(&a[cur], &a[left]);
			left++;
			cur++;
		}
		else if (a[cur] >key)
		{	swap(&a[cur], &a[right]);
			right--;
		}
		else
		{	cur++;
		}
	}
	
	QuickSort(a, begin, left- 1);
	QuickSort(a, right + 1, end);
}

代碼中通過引入一個(gè)變量cur實(shí)現(xiàn)區(qū)間的劃分，cur會(huì)將小于key的元素集中到左邊，大于key的元素集中到右邊，中間的位置留給等于key的元素。代碼中只是涉及l(fā)eft和right位置的元素移動(dòng)，最后循環(huán)結(jié)束時(shí)并沒有將key交換移動(dòng)。這里的循環(huán)條件是left<=right取等了，也就是說在循環(huán)中就已經(jīng)處理了和key的交換。和cur交換時(shí)lcur要移動(dòng)，開始時(shí)cur和left只差一個(gè)位置，cur不移動(dòng)就可能在交換時(shí)造成元素覆蓋，影響結(jié)果。

---

綜上所述，快排的時(shí)間復(fù)雜度是N*logN到N^2之間，輔助空間是logN和N之間。這都取決于數(shù)據(jù)元素好壞的情況。
對了，之前的幾種優(yōu)化方法都可以寫在都一份快排代碼中，使得快排優(yōu)化到最好成為名副其實(shí)的快排。

---

7.歸并排序 1.遞歸實(shí)現(xiàn)歸并排序

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

歸并排序就是不斷拆分區(qū)間，當(dāng)區(qū)間只有一個(gè)元素時(shí)就暫時(shí)認(rèn)為它是有序的，再回頭對拆分出的區(qū)間排序合并。但是拆分出的區(qū)間數(shù)據(jù)需要用另一個(gè)臨時(shí)空間保存，這個(gè)臨時(shí)空間保存排序好了的元素?cái)?shù)據(jù)。最后將臨時(shí)空間的數(shù)據(jù)在拷貝回原數(shù)組空間中即可。

這個(gè)不斷拆分區(qū)間的過程就需要用到遞歸。但是臨時(shí)空間的開辟只需要開一次即可，所以我們將排序邏輯拆開單獨(dú)寫成一個(gè)函數(shù)。在歸并排序的函數(shù)中調(diào)用這個(gè)排序邏輯即可。

接著我們就思考排序邏輯怎么確定。區(qū)間每次都是在上一個(gè)區(qū)間基礎(chǔ)上二分出來的。假定有這么有個(gè)區(qū)間【begin，end】，二分之后就是【begin,mid】【mid+1,end】。這兩個(gè)區(qū)間就當(dāng)于兩個(gè)數(shù)組，將兩個(gè)數(shù)組的元素進(jìn)行排序合并到另一個(gè)數(shù)組中。之前的力扣習(xí)題有講解過類似的合并處理，我們用bgein1和begin2兩個(gè)變量開始指向區(qū)間元素的首部，然后依次比較。最后如果有一個(gè)區(qū)間的沒有比較完，直接將該區(qū)間的剩余元素接上直接放入臨時(shí)數(shù)組即可。

圖中的代碼邏輯就是排序的主要邏輯。因?yàn)闅w并排序是先將數(shù)據(jù)分割成只有一個(gè)元素的區(qū)間，再排序合并。對于只有一個(gè)元素的區(qū)間來說，這個(gè)區(qū)間就是有序的。隨著不斷排序合并，臨時(shí)數(shù)組中的元素也會(huì)越來越有序。同時(shí)既然是遞歸那么遞歸邊界條件就是區(qū)間分隔成只有一個(gè)元素時(shí)停止，也就是begin==end.

那么代碼就很好寫了，代碼示例如下：

void  merge_sort_1(int* a, int* tem, int begin, int end)
{if (begin == end)
	{return;
	}
	int mid = (begin + end) / 2;
	merge_sort_1(a, tem, begin, mid);
	merge_sort_1(a, tem, mid + 1, end);
	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;
	int i = begin;
	while (begin1<= end1 && begin2<= end2)
	{if (a[begin1]<= a[begin2])
		{	tem[i++] = a[begin1++];
		}
		else
		{	tem[i++] = a[begin2++];
		}
	}

	while (begin1<= end1)
	{tem[i++] = a[begin1++];
	}

	while (begin2<= end2)
	{tem[i++] = a[begin2++];
	}
	memcpy(a + begin, tem + begin, sizeof(int) * (end - begin + 1));
}
void MergeSort_1(int* a, int n)
{int* tem = (int*)malloc(sizeof(int) * n);
	if (tem == NULL)
	{perror("malloc fail !");
		return;
	}
	merge_sort_1(a, tem, 0, n - 1);
	free(tem);
	tem = NULL;
}

雖然快排和歸并排序都是分割區(qū)間遞歸。但是兩者還是有區(qū)別的，當(dāng)數(shù)據(jù)是最開始的完整區(qū)間時(shí)，就可以進(jìn)行排序處理。然后接著分割排序。但是歸并排序是將數(shù)據(jù)分隔成有一個(gè)元素的區(qū)間時(shí)，再回過頭來進(jìn)行排序，也就是先分區(qū)間，再排序。快排是類似于先序遍歷，歸并相當(dāng)于后序遍歷。

---

2.歸并排序的非遞歸實(shí)現(xiàn)

歸并排序的遞歸是后序遍歷，所以不能像快排那樣很輕松借助額外的數(shù)據(jù)結(jié)構(gòu)就能解決。這個(gè)時(shí)候我們直接用迭代的方式來解決。斐波那契數(shù)列相信很多人都寫過，斐波那契數(shù)列的非遞歸就是從頭開始算往前迭代。那我們也可以先從只有一個(gè)元素的的時(shí)候開始算，從也就當(dāng)于區(qū)間分割到底了。定義一個(gè)變量用來控制區(qū)間范圍，從只有一個(gè)元素開始排序，區(qū)間范圍逐漸增大。這樣迭代著往前走。

代碼示例

void MergeSort_2(int* a, int n)
{int* tem = (int*)malloc(sizeof(int) * n);
	if (tem == NULL)
	{perror("malloc fail!");
		return;
	}

	//歸并每組數(shù)據(jù)個(gè)數(shù)，從1開始，因?yàn)?個(gè)認(rèn)為是有序的，可以直接歸并
	int range = 1;
	while (range< n)
	{for (int i = 0; i< n; i += range * 2)
		{	int begin1 = i, end1 = i + range - 1;
			int begin2 = i + range, end2 = i + 2 * range - 1;
			int j = i;
			//對邊界條件處理防止越界
			if (end1 >= n)
			{		break;
			}
			else if (begin2 >= n)
			{		break;
			}
			else if (end2 >= n)
			{		end2 = n - 1;
			}
			while (begin1<= end1 && begin2<= end2)
			{		if (a[begin1]<= a[begin2])
				{tem[j++] = a[begin1++];
				}
				else
				{tem[j++] = a[begin2++];
				}
			}
			while (begin1<= end1)
			{		tem[j++] = a[begin1++];
			}
			while (begin2<= end2)
			{		tem[j++] = a[begin2++];
			}
			memcpy(a + i, tem + i, sizeof(int) * (end2 - i + 1));
		}
		range *= 2;
	}

	free(tem);
	tem = NULL;
}

上面的代碼有很多要注意的細(xì)節(jié)，我們來好好分析一下。

代碼大致思路：range控制區(qū)間范圍，之前是通過遞歸的方式來達(dá)到將區(qū)間分隔的目的。從區(qū)間只有一個(gè)元素開始逐漸擴(kuò)大區(qū)間的范圍。排序邏輯和遞歸版的都是類似的，然后用拷貝函數(shù)將臨時(shí)數(shù)組拷貝到原數(shù)組中?？截惪梢苑诺匠朔诺窖h(huán)里面每次拷貝外，還可以放到for循環(huán)外面整體拷貝，也就是將數(shù)據(jù)排序好了放入臨時(shí)數(shù)組中，再將臨時(shí)數(shù)組的拷貝到原數(shù)組。

細(xì)節(jié)注意(區(qū)間可能越界的處理）

這里看到begin1=i,end1=i+range-1;begin2=i+range.end2=i+range*2-1;因?yàn)閕始終是小于n的所以begin1沒有越界的風(fēng)險(xiǎn)。當(dāng)數(shù)組的元素個(gè)數(shù)不是2的指數(shù)倍，就可能越界了。我們將每次劃分的區(qū)間打印出來，同時(shí)屏蔽掉防止區(qū)間越界的處理代碼

打印結(jié)果如下

我們看到打印如圖所示，沒啥問題。此時(shí)n的大小是8，如果我們將它換成10呢？

可以看到這里面有些區(qū)間已經(jīng)越界了。對此，我們必須做出區(qū)間越界的處理。

分析區(qū)間越界，無非就是以下幾種情況：首先bgein1不會(huì)越界，那么就是end1越界，如果end1越界后面的begin2和end2肯定必會(huì)越界。接著就是begin2越界，begin2越界后面的end2也肯定越界，最后一種情況就是只有end2越界了。所以分析下來只要處理3種情況即可，end1和begin2以及end2越界的處理。

這里處理防止區(qū)間越界有兩種方式，一種是修正區(qū)間，還有一種是跳出循環(huán)。對于在循環(huán)里的每次拷貝來說，這兩種方法都可以，但是對于循環(huán)外的整體拷貝來說只能修正區(qū)間。

像這種循環(huán)外的單次拷貝如果跳出循環(huán)可能會(huì)將一些隨機(jī)值拷貝到數(shù)組中或者造成將一些元素給覆蓋掉。這個(gè)時(shí)候只能修正區(qū)間了，需要后面的while(begin1

這個(gè)時(shí)候需要修正區(qū)間，將begin2和end2修正成一個(gè)不存在的區(qū)間。但是如果拷寫在for循環(huán)中就不用修正，直接跳出循環(huán)就可以。因?yàn)楹罄m(xù)的拷貝還是這些元素，不影響后續(xù)的排序拷貝。

接著處理begin2越界的情況,begin2的越界的話，begin2和end2都是錯(cuò)誤區(qū)間，對于在for循環(huán)中的分組多次拷貝來說直接break即可。如果對于在循環(huán)外整體拷貝來說就需要修正區(qū)間將begin2和end2改成不存在的區(qū)間即可。因?yàn)楹罄m(xù)的begin1和end1區(qū)間內(nèi)的元素是需要放進(jìn)臨時(shí)空間的。

最后就是end2越界了，end2越界，劃分的區(qū)間中肯定有一部分是屬于正常的范圍內(nèi)，對于end2來說只能采用修正區(qū)間的方法，不能跳過，否則最后一段區(qū)間就不會(huì)排序進(jìn)入臨時(shí)空間，造成排序的不完整。不管memcpy拷貝寫在何處，end需要修正成n-1。這樣才能正確排好序。

歸并排序的時(shí)間復(fù)雜度是N*logN，每次對區(qū)間進(jìn)行二分可以劃分成logN次，同時(shí)每次對劃分出的小區(qū)間都會(huì)遍歷，相當(dāng)于遍歷完了整個(gè)元素?？臻g復(fù)雜度需要臨時(shí)空間就是O(N).

---

8.計(jì)數(shù)排序

計(jì)數(shù)排序又稱為鴿巢原理，是對哈希直接定址法的變形應(yīng)用。計(jì)算排序是將待排的數(shù)據(jù)映射到數(shù)組下標(biāo)中，利用數(shù)組下標(biāo)的順序性來達(dá)到排序的目的。之前講解力扣題時(shí)就用到了類似的做法，將數(shù)組元素轉(zhuǎn)成另一個(gè)數(shù)組的下標(biāo)。計(jì)數(shù)排序也是類似的方法。

計(jì)數(shù)排序通過將數(shù)組元素轉(zhuǎn)成另一個(gè)數(shù)組的下標(biāo)來排序，這里就需要臨時(shí)空間了，為了節(jié)省空間。我們直接將空間范圍確定為0到待排數(shù)組元素中大值max與最小值min差值加1，也就是max-min+1.

代碼示例

void CountSort(int* a, int n)
{int max = a[0];
	int min = a[0];
	int i = 0;
	for (i=1; i< n; i++)
	{if (a[i] >max)
		{	max = a[i];
		}
		if (a[i]< min)
		{	min = a[i];
		}
	}
	int* count=(int*)calloc(max-min+1,sizeof(int));
	if (count == NULL)
	{perror(" calloc fail!");
		return;
	}
	for (i=0; i< n; i++)
	{count[a[i] - min]++;
	}
	int k = 0;
	for (i = 0; i< max-min+1; i++)
	{while (count[i]--)
		{	a[k++] = min+i;
		}
	}
	free(count);
	count = NULL;
}

當(dāng)然也可以不用calloc，直接寫成int count[max-min+1]={0};在賦值回去的時(shí)候需要將min加上。從代碼中可以看出復(fù)雜度：O(MAX(N,范圍))，空間復(fù)雜度：O(范圍)，這個(gè)范圍就是max-min+1
計(jì)數(shù)排序在數(shù)據(jù)范圍集中時(shí)，效率很高，但是適用范圍及場景有限。只是適用于對整型(負(fù)整型也可以)排序。

---

9.額外知識關(guān)于各類排序算法的穩(wěn)定性

所謂穩(wěn)定性就是，如果數(shù)組中有重復(fù)的元素，排序之后不影響相對位置就是穩(wěn)定的排序。比如1 5 4 346排序之后應(yīng)該是1 3 445 6，紅色的4在后面要保持相對位置不變。接著我們來討論討論上述8種算法的穩(wěn)定性。

插入排序的穩(wěn)定性

插入排序是在一個(gè)已經(jīng)有序的小序列的基礎(chǔ)上，一次插入一個(gè)元素。剛開始這個(gè)有序的小序列只有1個(gè)元素，就是第一個(gè)元素，插入的元素從end后開始比較往前移動(dòng)。如果end位置的元素和要插入的元素相等，可以將相等或者大于a[end]放入end的后面。所以，相等元素的前后順序沒有改變，從原無序序列出去的順序就是排好序后的順序，所以插入排序是穩(wěn)定排序算法。

冒泡排序的穩(wěn)定性

冒泡排序就是把小的元素往前調(diào)或者把大的元素往后調(diào)。比較是相鄰的兩個(gè)元素比較，交換也發(fā)生在這兩個(gè)元素之間。所以，如果兩個(gè)元素相等，沒有動(dòng)作；兩個(gè)相同元素就算有間隔也不影響，隨著不斷挪動(dòng)相相同的元素會(huì)相鄰，又回到了相鄰元素相等沒有交換。冒泡也是穩(wěn)定的。

歸并排序

歸并排序是把序列遞歸地分成短序列，遞歸出口是短序列只有1個(gè)元素或者2個(gè)序列，然后把各個(gè)有序的段序列合并成一個(gè)有序的長序列，不斷合并直到原序列全部排好序?？梢园l(fā)現(xiàn)，在1個(gè)或2個(gè)元素時(shí)，1個(gè)元素不會(huì)交換，2個(gè)元素如果大小相等也沒有人故意交換，這不會(huì)破壞穩(wěn)定性。那么，在短的有序序列合并的過程中，穩(wěn)定是是否受到破壞？沒有，合并過程中我們可以保證如果兩個(gè)當(dāng)前元素相等時(shí)，我們把處在前面的序列的元素保存在結(jié)果序列的前面，這樣就保證了穩(wěn)定性。所以，歸并排序也是穩(wěn)定的排序算法。

選擇排序的穩(wěn)定性

選擇排序是一種不穩(wěn)定的排序方式，當(dāng)數(shù)組中出現(xiàn)重復(fù)元素了，在找max和min的位置后會(huì)和begin end位置元素進(jìn)行交換，當(dāng)交換的位置是某個(gè)重復(fù)元素的為止時(shí)，原有順序就會(huì)被破壞，從而影響相對順序.

---

希爾排序的穩(wěn)定性

希爾排序也是不穩(wěn)定的，希爾排序的先進(jìn)行預(yù)分組的方式排序，在進(jìn)行預(yù)分組的時(shí)候隨著區(qū)間的跳動(dòng)是沒法控制相同元素的相對位置的。相同的元素可能會(huì)因?yàn)轭A(yù)處理的時(shí)候被從前面移動(dòng)到后面將原有的順序打亂

快排的穩(wěn)定性

快排也是不穩(wěn)定的，我們知道快排每次都選key，如果有相同的元素且它們大于key話,它們會(huì)集中到key的右側(cè)，中間會(huì)涉及到交換，先出現(xiàn)的元素會(huì)被放到后面，后出現(xiàn)的元素會(huì)被放到前面，這樣相對位置就會(huì)被影響。同時(shí)，如果相同的元素做key，因?yàn)樽詈笠粨Qkey，前面做key的元素也會(huì)被移動(dòng)到后面。

堆排序的穩(wěn)定性

堆排序也是不穩(wěn)定的，以建大堆為例，假如建堆的時(shí)候就保證了順序的穩(wěn)定性，但是堆頂?shù)臄?shù)據(jù)會(huì)被移動(dòng)到數(shù)組后面的位置，等到另一個(gè)相同的元素作為堆頂?shù)臅r(shí)候就會(huì)被放入靠前面的位置，這樣穩(wěn)定性就被破壞了。

---

計(jì)數(shù)排序的穩(wěn)定性

計(jì)數(shù)排序毫無疑問是沒有穩(wěn)定性的，計(jì)數(shù)排序只關(guān)心元素出現(xiàn)的次數(shù)，無法控制相對順序。這點(diǎn)通過代碼或者它的排序思想就可以感受到。

---

10.總結(jié)

• 以上便是對經(jīng)典的八大排序講解，以上內(nèi)容如有問題，歡迎指正！

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)頁名稱：數(shù)據(jù)結(jié)構(gòu)之經(jīng)典八大排序的實(shí)現(xiàn)(萬字詳談）-創(chuàng)新互聯(lián)
標(biāo)題鏈接：http://jinyejixie.com/article14/ccsige.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供虛擬主機(jī)、外貿(mào)網(wǎng)站建設(shè)、網(wǎng)站策劃、全網(wǎng)營銷推廣、電子商務(wù)、網(wǎng)站排名

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)