*** 以下排序皆以升序為例***

插入排序

1.1 直接插入排序

1.1.1 單趟排序思想（三種情況）

對于第一張圖片中的數據，我們設置一個tmp保存最后一個數據，設置end表示5的下標。在這串數據中可以看到，數據已經是升序了，我們要對6這個數據進行排序，就是拿tmp和end下標位置的數據比較，在這里tmp不小于end，那么就不需要做出任何改動

在這種圖片中我們可以觀察到，3最終是要放到2下標處的，我們現在開始對3進行排序。??if(tmp < arr[end])??我們就讓??arr[end+1]=arr[end]??也就是把前面的數據往后挪，給日后tmp找到了屬于自己的位置時留一個位置，此時第一次走，3是比6小的，那么下標為5的位置上就賦值成6，因為tmp=3，所以不必擔心會被覆蓋數據。然后再對end--。讓tmp與前面的數據接著比對，重復上面的操作，直到tmp與下標為2比較時，tmp比2大，停止遍歷，直接讓??arr[end+1]=tmp??，至此讓3找到了自己應該在的升序位置。

在這張圖片中我們可以看到，最終1是要放到0下標處的 。我們仍然重復上一張圖片里的步驟，兩者唯一的不同就是，當end==0時，比對完成，end變成-1，此時仍然是執行??arr[end+1]=tmp??,這可以解決end下標為-1的問題。

(資料圖片僅供參考)

1.1.2 單趟排序的代碼

int end;int tmp=arr[end+1];//當end<0或者tmp大于arr[end]的時候說明tmp找到了自己的位置while(end >= 0){  //如果當前排序的數據小于其它數據，就挪動數組內的元素順序，使其下標向后移  if(tmp < arr[end])  {    //挪動數據    arr[end+1]=arr[end];    end--;  }  else  {    break;  }}//把tmp放在自己該在的位置arr[end+1]=tmp;

1.1.3 完整直接插入排序思想

完整的插入排序的思想就是，每一次單趟插入排序把前面的數據排好順序，后面在排序的時候，只要tmp>arr[end]，就代表前面每一個數都比tmp要小，tmp也可以依此找到自己的位置了。比如：

在這張圖片中，第一次進行排序，我們把1和9排好升序

進行第二次排序時，數據就變成了下圖所示，再重復單趟排序

進行第三次排序時，數據變成了這樣，也就是說，在執行單趟循環的時候，5和9比完，把9賦值給下標為3的位置，然后和2比，5比2大，因為前面的數都比2小，之前已經排過序了，所以結束循環，此時end下標為1，arr[end+1]=tmp。這樣就讓tmp找到了位置。

1.1.4 代碼實現

void InsertSort(int* arr,int n)//n代表數組元素個數{  for(int i=0;i= 0)    {      //如果當前排序的數據小于其它數據，就挪動數組內的元素順序，使其下標向后移      if(tmp < arr[end])      {        //挪動數據        arr[end+1]=arr[end];        end--;      }      else      {        break;        //由于之前已經把前面的數據都排過序，        //所以如果大于，那么說明前面的數都小于tmp      }    }    //把tmp放在自己該在的位置    arr[end+1]=tmp;  }}

1.2 希爾排序

1.2.1 思想

希爾排序實際就是直接插入排序的優化。在希爾排序中，我們選取一個間距對整個數組進行分組，對每一組內的元素分別進行排序，然后不斷縮小間距，直到間距為1，就變成了直接插入排序，我們稱這個過程為預排序，而由于多次的預排序，數組元素已經接近有序，此時直接插入的效率大大提升。

比如：設置gap變量為間距，設置gap=5

1.2.2 代碼實現

void ShellSort(int*arr, int k){  int gap = k;  //循環中所有的+-gap的操作，都對應著直接插入排序中的end+1和end--操作。  //觸類旁通就好  while (gap > 1)  {    //下面這層循環就是單趟排序，在某一個gap值下進行的單趟排序，    //實現了讓數據更加有序的目的    //每一次進入這個循環都會使數據更加有序    gap /= 2;    //除以2能夠保證最后gap==1，    //也就保證了最后一次可以實現接近有序的直接插入排序    for (int i = 0; i < k - gap; i++)    {      int end = i;//讓end=i，依次對每一組進行預排      int tmp = arr[end + gap];      while (end >= 0)      {        if (tmp < arr[end])        {          arr[end + gap] = arr[end];          end -= gap;        }        else        {          break;        }      }      arr[end + gap] = tmp;    }  }}

選擇排序

2.1 直接選擇排序

2.1.1思想

在數據中遍歷，選出最小的數據和最大的數據，然后把它們分別放在元素集合中的最前面和最后面，每一遍遍歷過后，集合的寬度減2，重復以上步驟。思想很簡單，實現起來也很簡單。

2.1.2 代碼實現

void Swap(int* a, int* b){  int tmp = *a;  *a = *b;  *b = tmp;}void SelectSort(int* arr, int k){  //一次選擇排序兩個數據，分別放在最前面和最后面  int begin = 0; int end = k-1;    //找下標  while (begin < end)  {    int min = begin; int max = begin;    for (int i = begin + 1; i <= end; i++)    {      if (arr[min] > arr[i])      {        min = i;      }      if (arr[max] < arr[i])      {        max = i;      }    }    //最后找到最大和最小的數的下標，交換        if (max == begin)    {      ////判斷max原來的值是否會被第一個Swap覆蓋，如果==begin說明會被覆蓋，      //那么把min位置給max就可以得到交換位置后的數據      max = min;    }    Swap(&arr[begin], &arr[min]);    Swap(&arr[end], &arr[max]);    //一次循環排完了兩個數    begin++;    end--;  }}

2.2 堆排序

2.2.1 建立什么樣的堆

??要學習堆排序，先學習了解什么是堆??堆排序需要了解建堆這個數據結構，了解建堆算法。如果堆學好了，才能看得懂博主寫的堆排序是個什么東西。沒有學好堆，不要看這里的堆排序。

先說結論：升序建大堆，降序建小堆

為什么升序建小堆不好：排升序建小堆的話，堆頂數據為最小的數據，但因為堆的性質是，如果是小堆，只能保證孩子一定大于父親，不能保證孩子和兄弟之間是按從小到大排列的。所以接下來我們需要不斷地選出次小的數據來達到排序的目的。那么選出次小的數據的思路有兩種：

把堆頂數據刪除，存到一個數組里，然后再對剩下的數據進行調整。對于這種思路，我們需要明白有兩個弊端：刪除堆頂數據之后，我們需要對整個數組進行調整，要把整個數組的內容往前移動，這是對性能的浪費。挪動數組數據后，我們對應的邏輯關系也就亂了，如下圖，如果我們選出最小數據15，然后把15刪除掉，就得出右圖，我們可以看到，右圖中的父子關系已經混亂，不再是一個小堆。這時就需要重新建堆,浪費空間，需要重新開數組。這也意味著，每一次要選出次大的數據都要重新建堆，這又是一次性能的浪費。這個思路需要開新空間存刪掉的堆頂數據。

所以這個思路并不好。

把堆頂數據刪掉，把堆底數據換到堆頂，然后向下調整，原來的堆頂數據開新空間存入數組，解決了關系會亂的問題，不需要重新建堆，但同樣的，這個思路的缺點是開了新空間，空間復雜度為O(N)。要做，我們就要做最優的！！！

為什么排升序建大堆好：建大堆，意味著最大的數在堆頂，此時我們把堆頂與堆底對調，然后排除堆底數據，如下第1,2張圖，在選出次大的數據時，我們把堆底的65排除在外，15處才算做堆底。然后向下調整，選出次大的數據。重復以上步驟，每一次的向下調整之后我們都把次大的數交換在了當時的堆底。最后就可以實現堆頂是最小的數，整個堆都是有序的。

2.2.2 代碼實現

//排升序void Swap(int* a, int* b){    int tmp = *a;    *a = *b;    *b = tmp;}void Heapsort(){    int arr[] = {15,18,19,37,25,28,34,65,27,49};    int n = sizeof(arr) / sizeof(arr[0]);    Heap php;    //建堆O(N)    HeapCreat(&php, arr, n);        //O(N*log N)    for (int end = n-1; end > 0; end--)    {        Swap(&php.a[0], &php.a[end]);//交換堆頂堆底數據        AdjustDown(0, php.a, end);//調整選出次大的數    }}

交換排序

3.1 快速排序

快速排序這里介紹三種實現思路，分別是hoare版，挖坑法以及快慢指針法

3.1.1 hoare版

3.1.1.1 思想

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

單趟排序

如下方動圖，選取最左邊的數據或者最右邊的數據為key，此處以最左處為key，右邊先走找比key位置處的6小的值，找到了或遇到了左邊的小人就停下來，然后左邊再走，找比6大的值，找到了或遇到了右邊的小人就停下來。當左右兩個小人都找到了自己要找的數時，交換兩數，再重復以上步驟，直到兩小人相遇，把key位置的值與相遇位置的值相交換，至此完成單趟排序。

最后我們可以看到，在經歷上方動圖所示的排序后，我們達到了兩個效果:

分割出了左右兩個區間，6 的左邊都是比它小的值，右邊都是比它大的值。key位置的 6 到了它該在的位置.這就完成了快速排序的第一趟排序。之后分別對 6 左邊的數據序列和右邊的數據序列重復此步驟就可以完成全部數據的排序。這就是子問題，用一樣的方式不斷遞歸知道該區間只剩一個數。

多趟

由下方的圖我們可以看到，在每一個數都找到了自己的位置后，排序實際就已經完成了。

這其實就是一顆完全二叉樹，我們按照完全二叉樹的遞歸方式就可以把數據排好了

3.1.1.2 小問題

為什么能夠保證最后和key交換的的位置就是key應該在的位置

這里給出思路，既然已經看到這個地方了，如果前面的都看懂了說明是有能力獨立解決這個問題的，如果沒有解決，請看下方的思路，這個問題并不難，畫畫圖就可以解決，祝好運！

3.1.1.3 對以上思想的優化

3.1.1.3.1 三數取中

首先我們求算一下快速排序的時間復雜度

在單趟排序中，我們只需遍歷完整個循環就可以排好一個數，所以單趟的排序時間復雜度是O(N)。所以接下來，時間復雜度最好與最壞就取決于我們到底要走多少次單趟循環才能把所有數排完。

最好的情況：什么是最好的情況？我們前面講思想的時候提到，通過不斷的對剩下的區間進行排序達到整個數據集合排序的目的，這也就是不斷縮小問題規模形成子問題的方法，也就是遞歸。那么，遞歸的深度也就很大程度上決定了我們這個程序性能的高下。在進行單趟排序中，我們是左右兩邊互相靠近的，都在移動。那也就是說，理想狀態就是二者在中間位置相遇是最好的，邏輯圖可以想象為一個滿二叉樹，這種情況下的每一次單趟排序具體的時間復雜度是N/2。而如果相遇位置靠右或者靠左，就意味著程序的遞歸深度要增加，性能自然也就不是最優。如下圖，每一次選key，key最后的位置都在數據集合的中間，這樣就把數據集合分成了一顆完全二叉樹的形式進行遞歸。完全二叉樹遞歸深度為logN，每一層都有接近N個值，因為每一趟排序都會減少一個數據。又因為每一層要遍歷接近N次，所以最后的時間復雜度就是O(N * logN)。- 最壞的情況：數據集合是有序的。如下圖，這就意味著每一次選key，都只能選出一個key所在的位置，無法分割區間。也就是說，我們需要進行N次單趟循環。所以最壞的時間復雜度是O(N2)通過上方的時間復雜度的求算我們知道，影響快速排序性能的實際問題其實是key的選取，key選的差，時間復雜度就靠近O(N2），所以我們需要使起到分割區間作用的key盡量靠近中間位置。由此，誕生出了三數取中。

三數取中的思想

從選key下手，我們選三個數，一個為最左邊，一個最右邊，一個數據集合的中間位置，我們從這里面選取一個中間大的數據當做key，以此來盡量避免key分割出的區間很不均衡的問題。

下面是三數取中的代碼實現

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

3.1.1.3.2 小區間優化

通過下方這張圖，結合二叉樹的相關知識我們可以知道，遞歸往下，二叉樹的最后一層就占了一半的遞歸調用，倒數3層差不多就占了80%多的遞歸。而在最后的幾層遞歸中，我們實際待排的數據量是比較少的，這個時候用快排的優勢就體現不出來了，因為每一次遞歸開辟棧幀銷毀棧幀是會消耗性能的，同時遞歸層數過多可能導致棧溢出。這也就是小區間優化存在的意義。在數據量小的時候，我們采取直接插入排序的方法，減少了80%的遞歸，極大地優化了程序。

代碼放在下方的多趟hoare代碼實現里

3.1.1.3.3 三路并排

三數取中只能幫助我們盡量選出一個好的key，但當大量數據重復時，三數取中也會無能為力。因為在數據大量重復時，分割出的區間會很不均衡，比如??{2,2,3,2,2,3,2,2}???邏輯圖也不會是我們上面的完全二叉樹了,性能極大地下滑。為了解決這個問題，三路并排就出現了。

其主要的思路就是把與key相同的數據往中間靠，比key小的數據往左，比key大的數據往右。目的就是不讓與key相同的數據再次參與排序，極大地優化了性能。

單趟三路并排：

最后

void QuickThreeSort(int* arr, int begin, int end)//末尾數據下標{  //如果右邊<=左邊說明只剩1個數據了  if (begin >= end)  {    return;  }  int left = begin;  int right = end;  int cur = begin + 1;  //把得到的key的位置放到最左邊  Swap(&arr[GetMidIndex(arr, begin, end)], &arr[begin]);  int key = arr[begin];  int keyi = begin;  //小區間優化  if (end - begin > 10)  {    //單趟，排序主體    while (cur <= right)    {      if (arr[cur] < key)      {        Swap(&arr[left++], &arr[cur++]);      }      else if (arr[cur] > key)      {        Swap(&arr[cur], &arr[right--]);      }      else        cur++;    }    QuickPoint(arr, begin, left-1);    QuickPoint(arr, right+1, end);  }  else//直接插入排序  {    InsertSort(arr + begin, end - begin + 1);  }}

3.1.1.4 代碼實現

在看懂前面的思想后，試著自己實現一下代碼再來看博主的代碼有什么不一樣。用這個思想實現代碼會有一些坑。寫完代碼去代碼尾部看坑。

單趟

void Swap(int* a, int* b){  int tmp = *a;  *a = *b;  *b = tmp;}void QuickSort(int *arr,int n){  int left =0; int right = n-1;  int key = left;     while (left < right)  {    //右邊先走，找小    while (left < right && arr[right] >= arr[key])    {      --right;    }    //左邊后走，找大    while (left < right && arr[left] <= arr[key])    {      ++left;    }    //交換比key位置大的和比key位置小的數    Swap(&arr[left], &arr[right]);  }  //交換key位置的數和相遇位置的數，完成單趟  Swap(&arr[left], &arr[key]);}

坑1：如果數據集合是這樣的：{3,5,7,8,4,3,10}。設左邊是key，我們就需要考慮到數據集合中有數字是和key位置相同的，對于這串數據，我們要考慮到的是當某個位置的數字是和key位置相同，那么這意味著如果按照上面的思想我們右邊找小，比key要大，我們就right - 1，當碰到 3 了，我們就停下來了，此時就會陷入死循環。所以我們在代碼中要找小找大，就要找純粹的大和小，與key處元素相等就跳過。坑2：如果數據集合是這樣的：{1,2,3,4,5,6,7,8}。設左邊是key，右邊的數全比 1 要大，因為右邊先走，此時如果不限定條件讓left

多趟

void Swap(int* a, int* b){  int tmp = *a;  *a = *b;  *b = tmp;}void QuickHoare(int* arr, int begin, int end)//end是最后一個數據的下標{  //如果右邊<=左邊說明只剩1個數據了  if (begin >= end)  {    return;  }  int left = begin; int right = end ;  //三數取中后把得到的key的位置放到最左邊  Swap(&arr[GetMidIndex(arr, begin, right)], &arr[begin]);  int key = begin;  //小區間優化  if (end - begin > 10)  {    //單趟，排序主體    while (left < right)    {      //右邊先走，找小      while (left < right && arr[right] >= arr[key])      {        --right;      }      //左邊后走，找大      while (left < right && arr[left] <= arr[key])      {        ++left;      }      Swap(&arr[left], &arr[right]);    }    Swap(&arr[left], &arr[key]);    QuickHoare(arr, begin, left-1);    QuickHoare(arr, left + 1, end);  }  else//直接插入排序  {    InsertSort(arr + left, end - begin +1);  }}

3.2.1 挖坑法

3.2.1.1 思想

挖坑法的思想其實和hoare大佬的思想很像，就是把key位置的數據保存起來，把key位置當做坑，然后key在左就右邊先走，key在右就左邊先走。

如下圖：這里以左邊為key，右邊先走找小，每停一次把停住的位置的數據放到坑位上，然后另外一邊再走。重復以上步驟，兩者相遇的位置就是key應該在的位置。

3.2.1.2 代碼實現

void Swap(int* a, int* b){  int tmp = *a;  *a = *b;  *b = tmp;}//挖坑void QuickHole(int* arr, int begin, int end)//end是最后一個數據的下標{  //如果右邊<=左邊說明只剩1個數據了  if (begin >= end )  {    return;  }  int left = begin; int right = end;  //三數取中后把得到的key的位置放到最左邊  Swap(&arr[GetMidIndex(arr, begin, right)], &arr[begin]);  int key = arr[begin];  //小區間優化  if (end - begin > 10)  {    //單趟，排序主體    while (left < right)    {      //右邊先走，找小      while (left < right && arr[right] >= key)      {        --right;      }      arr[left] = arr[right];      //左邊后走，找大      while (left < right && arr[left] <= key)      {        ++left;      }      arr[right] = arr[left];    }    arr[left] = key;    //遞歸小區間    QuickHoare(arr, begin, left-1);    QuickHoare(arr, left + 1, end);  }  else//直接插入排序  {    InsertSort(arr + left, end - begin + 1);  }}

3.3.1 快慢指針法

3.3.1.1 思想

同樣是選key，一樣的操作，實現交換的細節不一樣而已。我們要做的就是用cur指針找比key小的數據，找到后停下來，然后++prev，交換prev和cur位置的值。最后cur遍歷完整個數據集合時，prev所在的位置就是key應該在的位置。下面動態展示單趟排序的操作細節

開始：

最后：

3.3.1.2 代碼實現

void Swap(int* a, int* b){  int tmp = *a;  *a = *b;  *b = tmp;}void QuickPoint(int* arr, int begin, int end)//end為末尾數據的下標{  //如果右邊<=左邊說明只剩1個數據了  if (begin >= end)  {    return;  }  //快慢下標  int prev = begin;  int cur  = begin + 1;  //三數取中后把得到的key的位置放到最左邊  Swap(&arr[GetMidIndex(arr, begin, end)], &arr[begin]);  int key = begin;  //小區間優化  if (end - begin > 10)  {    //單趟，排序主體    while (cur <= end)    {      if (arr[cur] < arr[key] && ++prev != cur)      {        Swap(&arr[prev], &arr[cur]);      }      cur++;    }    Swap(&arr[prev], &arr[key]);        //遞歸小區間    QuickPoint(arr, begin, prev-1);    QuickPoint(arr, prev + 1, end);  }  else//直接插入排序  {    InsertSort(arr + begin, end - begin + 1);  }}

3.4 快排的非遞歸實現

3.4.1 思想

我們知道，遞歸調用的過程是，開始調用創建一塊棧空間，調用結束銷毀這片棧空間。所以可以使用棧這個數據結構入棧與出棧的操作來模擬遞歸的調用,入棧對應著遞歸調用，把區間傳給遞歸的函數，出棧對應著銷毀棧幀，在出棧的時候我們拿到區間下標，對這段區間進行排序。

創建好棧后，我們把待排序的區間的下標入棧，再把區間對應的下標出棧進行排序，這就是單趟的排序。單趟排完后我們可以拿到起到分割區間作用的key位置的下標，這里稱keyi，進行區間的劃分：

???[begin,keyi-1] keyi [keyi+1,end]???,然后再對兩區間入棧。重復以上步驟，我們就可以實現利用棧模擬遞歸調用。

因為博主的實現思路是先把左區間排完再拍右區間，根據棧的后入先出特點，我們先入右區間再入左區間，然后再對要排序的區間進行出棧操作。不斷循環以上操作，實現快排的非遞歸！！！

3.4.2 代碼實現

void Swap(int* a, int* b){  int tmp = *a;  *a = *b;  *b = tmp;}int SinglePassSort(int* arr, int begin, int end){  //快慢下標  int prev = begin;  int cur = begin;  //三數取中，把得到的key的位置放到最左邊  Swap(&arr[GetMidIndex(arr, begin, end)], &arr[begin]);  int key = begin;  while (cur <= end)  {    if (arr[cur] < arr[key] && ++prev != cur)    {      Swap(&arr[prev], &arr[cur]);    }    cur++;  }  Swap(&arr[prev], &arr[key]);  return prev;}void QuickSortNonR(int* arr, int begin, int end)//end是末尾數據的下標{  ST* st = (ST*)malloc(sizeof(ST));  StackInit(st);  Stackpush(st, begin);//把最前面的數據的下標入棧  Stackpush(st, end);//把最后一個數據的下標入棧  while (!IsEmpty(st))//棧不為空說明排序沒有完成，里面的判斷是判斷棧是否為空  {    int end = StackTop(st);  //end就是最后的數據的下標，根據入棧的順序來    Stackpop(st); //出棧    int begin = StackTop(st);//begin就是頭部的數據的下標    Stackpop(st);//出棧    //提取出之前寫的單趟排序的代碼進行排序    int keyi = SinglePassSort(arr, begin, end);        if ( keyi + 1 < end)    {      //入右區間      Stackpush(st, keyi + 1);      Stackpush(st, end);    }    if ( begin < keyi-1)    {      //入左區間      Stackpush(st, begin);      Stackpush(st, keyi - 1);    }  }  StackDestory(st);  free(st);  st = NULL;}

歸并排序

4.1 遞歸實現

4.1.1 思想

如果兩個左右兩個區間有序，那么把左區間和右區間合并在一起，使其變得有序，這就是歸并的意思。那么問題就在于左右區間是無序的怎么辦？我們仍然采用分治的思想，將左右區間不斷分割，直到只剩一個數據，一個數據我們就認為它是有序的，這就對應下圖的分解。分解完成后，我們開始合并，把左右區間的數據排序合并在一起。最終完成整個數據集合的排序。

4.1.2 實現

要注意一個點，我們不能在原數組進行排序合并，如果在原數組進行合并，合并過程會導致原數組中的數據被覆蓋，創建一個數組來解決這個問題會很妙。

void _MergeSort(int* arr, int begin, int end, int* tmp)//end是最后元素的下標{  //遞歸結束條件,一個數據不再需要分解  if (begin >= end)  {    return;  }  //分割左右區間  int mid = begin + (end - begin) / 2;  int begin1 = begin; int end1 = mid;  int begin2 = mid + 1; int end2 = end;  _MergeSort(arr, begin1, end1, tmp);  _MergeSort(arr, begin2, end2, tmp);    //合并區間并交換  int i = begin;  //兩區間合并，數據先放到tmp數組中，比對完后面拷貝回原數組  while (begin1 <= end1 && begin2 <= end2)//左右任意一個區間走完了就停下  {    if(arr[begin1] < arr[begin2])    {      tmp[i++] = arr[begin1++];    }    else    {      tmp[i++] = arr[begin2++];    }  }  //把剩下沒有拷貝的數據拷貝進tmp  while (begin1 <= end1)  {    tmp[i++] = arr[begin1++];  }  while (begin2 <= end2)  {    tmp[i++] = arr[begin2++];  }  //拷貝到原數組中  memcpy(arr+begin, tmp+begin, sizeof(int)*(end-begin+1));}void MergeSort(int* arr, int n)//n是數組元素個數{  int* tmp = (int*)malloc(sizeof(int) * n);//創建用來交換的數組  if (tmp == NULL)  {    perror("MergeSort malloc");    exit(-1);  }  //創建一個子函數，避免在這里面遞歸每次都要動態開辟一個tmp數組  _MergeSort(arr, 0, n-1, tmp);  free(tmp);  tmp = NULL;}

4.2 非遞歸實現

4.2.1 思路

我們知道，歸并的思路就是把左右區間各取一半，兩區間如果有序就把兩區間合并使其有序。那么我們的非遞歸就是從最小的問題出發，先一個一個數進行歸并，再兩個兩個數歸并，依次增大歸并的數據量，直到把最后的最大的兩個區間歸并完，數據就變得整體有序了。這和遞歸是相反的思路，遞歸是一步一步縮小區間，非遞歸是一步一步擴大區間。

如下圖：

4.2.2 代碼實現

需要注意幾個點

每一個rangeN間距下，循環遍歷數組 i 的取值以及范圍每一個rangeN間距下，待歸并的左右區間是否存在如：

void MergeSortNonR(int* arr, int begin, int end)//end是元素個數{  int* tmp = (int*)malloc(sizeof(int)* (end+1));//創建用來交換的數組  if (tmp == NULL)  {    perror("MergeSort malloc");    exit(-1);  }  int rangeN = 1;  //rangeN 為元素個數一半之前都進行歸并,  while (rangeN=end)      {        break;//無論是end1還是begin2越界，我們都無法進行歸并，直接退出      }      if (begin2 >= end)      {        break;      }      if (end2 >= end)      {        end2 = end - 1; //如果是end2越界，我們把end2改成end-1就行，                  //把剩下的數據歸并排序      }              int j = i;      //兩區間合并，數據先放到tmp數組中，比對完后面拷貝回原數組      while (begin1 <= end1 && begin2 <= end2)//左右任意一個區間走完就停下      {        if (arr[begin1] < arr[begin2])        {          tmp[j++] = arr[begin1++];        }        else        {          tmp[j++] = arr[begin2++];        }      }      //把剩下沒有拷貝的數據拷貝進tmp      while (begin1 <= end1)      {        tmp[j++] = arr[begin1++];      }      while (begin2 <= end2)      {        tmp[j++] = arr[begin2++];      }      //拷貝到原數組中      memcpy(arr + i, tmp + i, sizeof(int)*(end2-i+1));    }    rangeN *= 2;  }}

總結

5.1 時間復雜度

直接插入排序

最壞的情況下：逆序的情況就是最壞的情況，這意味著每一次進行單趟排序，tmp都要循環至最前面進行交換，時間復雜度時O(N2)。最好的情況：有序或者接近有序。這意味著單趟排序時每一個tmp代表的值要進行的循環只有1次或者接近1次，時間復雜度為O(N)。我們一般默認最壞的情況是時間復雜度，所以是O（N2）。

希爾排序

希爾排序的時間復雜度以我的能力實在沒法兒求，需要高深的數學知識很強的數理能力。

因為gap的取值有很多種方法，也沒有一個公認的時間復雜度。

直接選擇排序

典型的O（N2），每次排序要遍歷一遍數組選出數據，要遍歷N次。

堆排序

堆排序的時間復雜度需要了解建堆的過程，了解建堆算法。如果堆這個數據結構學好了，才能看得懂博主寫的是什么。沒有學好堆，不要看這里的堆排序。O(N* logN)，向下調整是O（logN），要調整N次，所以是O(N* logN)。

快速排序

O(N* logn)，在3.1.1.3.1中我求算了快排在沒有優化前的時間復雜度，而在三數取中優化后，我們快排最后取出的數會是一個比較均衡的數，也就是說，可以默認快排的時間復雜度接近最好的情況。

歸并排序

歸并排序實際上就是快速排序的最優情況，每一次都二等分數據集合，想象邏輯圖是一顆完全二叉樹，我們可以得出深度是logN，每層遍歷N次，所以時間復雜度是O(N* logN)

5.2 空間復雜度

不重要，不解釋，也不難。遞歸就算遞歸的深度，深度就是空間復雜度。求時間和空間這個在博主的??時間復雜度空間復雜度求算博客??中講的很清楚。

5.3 穩定性

5.3.1 什么是穩定性

假設一場考試中有三人先后交卷，第一個交卷的為92分，第二個交卷的91分，第三個交卷的也是91分，這時我們要對他們進行的成績排先后順序，把92排在最前，這沒問題。第二個和第三個同分，但第二個比第三個先交卷，如果我們把第三個交卷的人排在第二就不合理了，這時我們把可以保證相同數據的相對順序的排序稱穩定性好。比如??? 1 5 4 7 4 9??，排升序，可以讓第1個 4 排在第 2 個4前面的排序就是穩定性好。如果后面那個4排到前面去了說明穩定性不好。

5.3.2 各排序的穩定性分析

這里只分析選擇排序，因為一些書和資料對它的穩定性分析有爭議

選擇排序穩定性分析

這里采用一次找一個數的排序來分析穩定性，一次找一個數都保證不了，一次找兩個數就更不能保證穩定性了。如圖：