所以直接插入排序的整個過程的代碼實現如下：

void InsertSort(int* a, int n){	int i = 0;	for (i = 0; i < n - 1; i++)	{		int end = i;		// 先定義一個變量將要插入的數保存起來		int x = a[end + 1];		// 直到后面的數比前一個數大時就不往前移動，就直接把這個數放在end的后面		while (end >= 0)		{			if (a[end] > x)			{				a[end + 1] = a[end];				end--;			}			else			{				break;			}		}		a[end + 1] = x;	}}

?時間復雜度和空間復雜度的分析
時間復雜度： 第一趟end最多往前移動1次，第二趟是2次……第n-1趟是n-1次，所以總次數是1+2+3+……+n-1=n*(n-1)/2，所以說時間復雜度是O(n^2)
最好的情況： 順序
最壞的情況： 逆序
:給大家看一下直接插入排序排100w個數據要跑多久

空間復雜度：由于沒有額外開辟空間，所以空間復雜度為O(1)
?直接插入排序穩定性的分析
直接插入排序在遇到相同的數時，可以就放在這個數的后面，就可以保持穩定性了，所以說這個排序是穩定的。

?希爾排序

?基本思想：希爾排序是建立在直接插入排序之上的一種排序，希爾排序的思想上是把較大的數盡快的移動到后面，把較小的數盡快的移動到后面。先選定一個整數，把待排序文件中所有記錄分成個組，所有距離為的記錄分在同一組內，并對每一組內的記錄進行排序。（直接插入排序的步長為1），這里的步長不為1，而是大于1，我們把步長這個量稱為gap，當gap>1時，都是在進行預排序，當gap==1時，進行的是直接插入排序。
?可以先給大家看一個圖解：

看一下下面動圖演示的過程：

我們可以先寫一個單趟的排序：

int end = 0;int x = a[end + gap];while (end >= 0){	if (a[end] > x)	{		a[end + gap] = a[end];		end -= gap;	}	else	{		break;	}}a[end + gap] = x;

這里的單趟排序的實現和直接插入排序差不多，只不過是原來是gap = 1，現在是gap了。
由于我們要對每一組都進行排序，所以我們可以一組一組地排，像這樣：

// gap組for (int j = 0; j < gap; j++){	int i = 0;	for (i = 0; i < n-gap; i+=gap)	{		int end = i;		int x = a[end + gap];		while (end >= 0)		{			if (a[end] > x)			{				a[end + gap] = a[end];				end -= gap;			}			else			{				break;			}		}		a[end + gap] = x;	}}

也可以對代碼進行一些優化，直接一起排序，不要一組一組地，代碼如下：

int i = 0;for (i = 0; i < n - gap; i++)// 一起預排序{	int end = i;	int x = a[end + gap];	while (end >= 0)	{		if (a[end] > x)		{			a[end + gap] = a[end];			end -= gap;		}		else		{			break;		}	}	a[end + gap] = x;}

?當gap>1時，都是在進行預排序，當gap==1時，進行的是直接插入排序。
?gap越大預排越快，預排后越不接近有序
?gap越小預排越慢，預排后越接近有序
?gap==1時，進行的是直接插入排序。
?所以接下來我們要控制gap，我們可以讓最初gap為n，然后一直除以2直到gap變成1，也可以這樣：gap = gap/3+1。只要最后一次gap為1就可以了。
所以最后的代碼實現如下：

void ShellSort(int* a, int n){	int gap = n;	while (gap > 1)// 不要寫等于，會導致死循環	{		// gap > 1 預排序		// gap == 1 插入排序		gap /= 2;		int i = 0;		for (i = 0; i < n - gap; i++)// 一起預排序		{			int end = i;			int x = a[end + gap];			while (end >= 0)			{				if (a[end] > x)				{					a[end + gap] = a[end];					end -= gap;				}				else				{					break;				}			}			a[end + gap] = x;		}	}}

?時間復雜度和空間復雜度的分析
時間復雜度： 外層循環的次數前幾篇博客我們算過很多次類似的，也就是O(logN),
里面是這樣算的

:給大家看一下直接插入排序排100w個數據要跑多久

看這時間，比起直接插入排序真的是快了太多。
空間復雜度：由于沒有額外開辟空間，所以空間復雜度為O(1)
?希爾排序穩定性的分析
我們可以這樣想，相同的數被分到了不同的組，就不能保證原有的順序了，所以說這個排序是不穩定的。

?選擇排序

?直接選擇排序

?基本思想每一次從待排序的數據元素中選出最小（或最大）的一個元素，存放在序列的起始位置，直到全部待排序的數據元素排完 。
?我們先看一下直接選擇排序的動圖演示：

像上面一樣，我們先來實現單趟排序：

int begin = 0;int mini = begin;int maxi = begin;int i = 0;for (i = begin; i <= end; i++){	if (a[i] > a[maxi])	{		maxi = i;	}	if (a[i] < a[mini])	{		mini = i;	}}// 如果maxi和begin相等的話，要對maxi進行修正if (maxi == begin)	maxi = mini;Swap(&a[begin], &a[mini]);Swap(&a[end], &a[maxi]);

這里我要說明一下，其中加了一段修正maxi的代碼，就是為了防止begin和maxi相等時，mini與begin交換會導致maxi的位置發生變化，最后排序邏輯就會亂了，所以加上一段修正maxi的值得代碼。

if (maxi == begin)	maxi = mini;

整體排序就是begin往前走，end往后走，相遇就停下，所以整體代碼實現如下：

void SelectSort(int* a, int n){	int begin = 0;	int end = n - 1;		while (begin < end)	{		int mini = begin;		int maxi = begin;		int i = 0;		for (i = begin; i <= end; i++)		{			if (a[i] > a[maxi])			{				maxi = i;			}			if (a[i] < a[mini])			{				mini = i;			}		}		// 如果maxi和begin相等的話，要對maxi進行修正		if (maxi == begin)			maxi = mini;		Swap(&a[begin], &a[mini]);		Swap(&a[end], &a[maxi]);		begin++;		end--;	}} 

?時間復雜度和空間復雜度的分析
時間復雜度： 第一趟遍歷n-1個數，選出兩個數，第二趟遍歷n-3個數，選出兩個數……最后一次遍歷1個數（n為偶數）或2個數（n為奇數），所以總次數是n-1+n-3+……+2，所以說時間復雜度是O(n^2)
最好的情況： O(n^2)（順序）
最壞的情況： O(n^2)（逆序）
直接選擇排序任何情況下的時間復雜度都是 O(n^2)，因為不管有序還是無序都要去選數。
?給大家看一下直接選擇排序排100w個數據要跑多久

空間復雜度：由于沒有額外開辟空間，所以空間復雜度為O(1)
?直接選擇排序穩定性的分析
我們可以這樣想

所以說直接選擇排序是不穩定的。

?堆排序

?堆排序我在上上一篇博客已經詳細介紹了，大家可以點擊這里去看堆排序

?交換排序

?基本思想：所謂交換，就是根據序列中兩個記錄鍵值的比較結果來對換這兩個記錄在序列中的位置，交換排序的特點是：將鍵值較大的記錄向序列的尾部移動，鍵值較小的記錄向序列的前部移動。

?冒泡排序

?基本思想：它重復地走訪過要排序的元素列，依次比較兩個相鄰的元素，如果順序（如從大到小、首字母從Z到A）錯誤就把他們交換過來。走訪元素的工作是重復地進行直到沒有相鄰元素需要交換，也就是說該元素列已經排序完成。
?圖解如下：

?再看一個冒泡排序的動圖：

先實現單趟冒泡排序：

int j = 0;for (j = 0; j < n - 1; j++){	// 比后面的數大就交換	if (a[j] > a[j + 1])	{		exchange = 1;		Swap(&a[j], &a[j + 1]);	}}

再實現整體的排序：

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

?我們再考慮這樣一個問題，假如當前的序列已經有序了，我們有什么辦法讓這個排序盡快結束嗎？
這當然是有的，我們可以定義一個exchange的變量，如果這趟排序發生交換就把這個變量置為1，否則就不變，不發生交換的意思就是該序列已經有序了，利用這樣一個變量我們就可以直接結束循環了。

優化后的代碼如下：

void BubbleSort(int* a, int n){	int i = 0;	for (i = 0; i < n - 1; i++)	{		int exchange = 0;		int j = 0;		for (j = 0; j < n - i - 1; j++)		{			if (a[j] > a[j + 1])			{				exchange = 1;				Swap(&a[j], &a[j + 1]);			}		}		// 不發生交換		if (exchange == 0)			break;	}}

?時間復雜度和空間復雜度的分析
時間復雜度： 第一趟最多比較n-1次，第二趟最多比較n-2次……最后一次最多比較1次，所以總次數是n-1+n-2+……+1，所以說時間復雜度是O(n^2)
最好的情況： O(n)（順序）
最壞的情況： O(n^2)（逆序）
所以說冒泡排序在最好的情況下比直接選擇排序更優。
?給大家看一下冒泡排序排10w個數據要跑多久,因為太慢了，所以這里只排10w

可以看出的是，10w個數冒泡排序都排的很久。
空間復雜度：由于沒有額外開辟空間，所以空間復雜度為O(1)
?直接選擇排序穩定性的分析
冒泡排序在比較遇到相同的數時，可以不進行交換，這樣就保證了穩定性，所以說冒泡排序數穩定的。

?快速排序（遞歸版本）

?快速排序是Hoare于1962年提出的一種二叉樹結構的交換排序方法。

?hoare版本

?基本思想：任取待排序元素序列中的某元素作為基準值，按照該排序碼將待排序集合分割成兩子序列，左子序列中所有元素均小于基準值，右子序列中所有元素均大于基準值，然后最左右子序列重復該過程，直到所有元素都排列在相應位置上為止。
?我們先看一個分割一次的動圖：
?我們要遵循一個原則：關鍵詞取左，右邊先找小再左邊找大；關鍵詞取右，左邊找先大再右邊找小。
?一次過后，2也就來到了排序后的位置，接下來我們就是利用遞歸來把key左邊區間和右邊的區間遞歸排好就可以了，如下：

遞歸左區間:[left, key-1] key 遞歸右區間:[key+1, right]

hoare版本找key值代碼實現如下：

int PartSort1(int* a, int left, int right){	int keyi = left;	while (left < right)	{		// 右邊找小		while (left < right && a[right] >= a[keyi])		{			right--;		}		// 左邊找大		while (left < right && a[left] <= a[keyi])		{			left++;		}		Swap(&a[left], &a[right]);	}	Swap(&a[keyi], &a[left]);	return left;}

快排代碼實現如下：

void QuickSort(int* a, int left, int right){	if (left > right)		return;	int div = PartSort1(a, left, right);	// 兩個區間 [left, div-1] div [div+1, right]	QuickSort(a, left, div - 1);	QuickSort(a, div + 1, right);}

?我們考慮這樣一種情況，當第一個數是最小的時候，順序的時候會很糟糕，因為每次遞歸right都要走到頭，看下圖：

此時會建立很多函數棧幀，遞歸的深度會很深，會導致棧溢出（stackover），看下圖：

為了優化這里寫了一個三數取中的代碼，三數取中就是在序列的首、中和尾三個位置選擇第二大的數，然后放在第一個位置，這樣就防止了首位不是最小的，這樣也就避免了有序情況下，情況也不會太糟糕。
下面是三數取中代碼：

int GetMidIndex(int* a, int left, int right){	int mid = left + (right - left) / 2;	if (a[mid] > a[left])	{		if (a[right] > a[mid])		{			return mid;		}		// a[right] <= a[mid]		else if (a[left] > a[right])		{			return left;		}		else		{			return right;		}	}	// a[mid] <= a[left]	else	{		if (a[mid] > a[right])		{			return mid;		}		// a[mid] <= a[right]		else if (a[left] > a[right])		{			return right;		}		else		{			return left;		}	}}

所以加上三數取中優化后的代碼如下：

int PartSort1(int* a, int left, int right){	int index = GetMidIndex(a, left, right);	Swap(&a[index], &a[left]);	int keyi = left;	while (left < right)	{		// 右邊找小		while (left < right && a[right] >= a[keyi])		{			right
            
                     

                 

                                                                                                                    
                         云服務器
                                             
                         GPU云服務器
                                                                                                                                                 
                                      
                     
                    
                                                                                               排序算法圖解
                                                                                                           排序算法總結
                                                                                                           最快比較排序算法
                                                                                                           最快的基于比較的排序算法
                                                         
                 
               
              
             
               

                   
 文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
                 
                   
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/125071.html
               
                      
               

                 
                                  
上一篇：stl——容器適配器
  
                                                
                                       
下一篇：C語言中數據的存儲