1.排序的概念及常見的排序算法

? ? ? ? 排序在咱們日常生活中十分的常見，就好比是網上購物的時候通常能夠選擇按照什么排序，比如價格、評論數量、銷量等。那么接下來咱們就來了解一些關于排序的概念。

????????排序：所謂排序，就是使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減的排列起來的操作。

????????穩定性：假定在待排序的記錄序列中，存在多個具有相同的關鍵字的記錄，若經過排序，這些記錄的相對次 序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，則稱這種排 序算法是穩定的；否則稱為不穩定的。

????????內部排序：數據元素全部放在內存中的排序。

????????外部排序：數據元素太多不能同時放在內存中，根據排序過程的要求不斷地在內外存之間移動數據的排序。

? ? ? ? 排序也是有很多算法的，一下是常見的排序算法:

? ? ? ? 接下來咱們分別來說一說這些個常見的排序。

2.插入排序

? ? ? ? 2.1直接插入排序

? ? ? ? 插入排序就像是打撲克牌摸牌時的整理牌的動作，取出一張牌，插在兩張牌之間形成升序，以此往復，直至牌被整理好。咱們再來觀察一下直接插入排序排升序的動圖模擬。

? ? ? ? 首先，咱們來討論開始情況，初始時，認為第一個元素已排好，①與②比較，如果②大，認為①②已經排好，接下來以②開始和③比較；如果②小，則取出②，①挪到②的位置，②向后沒有數可以比較，②停在0的位置，認為①②排好，接下來以②開始和③比較。

? ? ? ? 接下來，咱們假設一共有n個元素，設end為已排好的序列的最后一項的位置,提前存好end+1的內容賦值到tmp。end與end+1進行比較:

①如果end+1比end要大，那么視為排好，end+1成為新的end繼續與新的end+1進行比較；

②如果end+1比end要小，end的內容賦值到end+1中，這時候的end缺少數據,咱們假象tmp停在上面等待加入,接著end--，將end和tmp進行比較:

????????①如果tmp大于end，就說明前面的數據全都比tmp小，無需再比較，tmp停下比較，停在end+1的位置（end是--后的end）；

????????②如果tmp小于end，那么end的值賦值在end+1的位置(tmp預備賦值的地方），想象tmp懸在end上方，end--，以此往復，直到end減到了-1，或者tmp碰到了比他小的數為止，最終tmp賦值在了end+1處。

? ? ? ? 以上就是對于單趟排序的分析，以下是插入排序的具體內容，可見插入排序的時間復雜度是O(N^2).

void InsertSort(int* a, int n)
{for(int i=0;i<n-1;i++){//初始時，認為第一個數據已經排好int end = i;//提前存下end+1的內容int tmp = a[end + 1];//end為-1的時候結束while (end >= 0){//tmp小，還沒有找到自己的位置if (tmp < a[end]){//end來到end+1的位置a[end + 1] = a[end];end--;}else//tmp大，說明已經找到位置了，不用繼續遍歷，退出循環{break;}}//將tmp賦值在end+1的位置a[end + 1] = tmp;}
}

? ? ? ? 2.2希爾排序

? ? ? ? 希爾排序是以插入排序為基礎的一種排序，效率比直接排序更高，時間復雜度大概為O(N^1.3)，其思想是:①通過預排序使數據趨于有序;②用插入排序排好。

? ? ? ? 假設一個整型gap,那么預排序就是從0開始，每隔一個gap取一個數(不越界取),取完后進行一次插入排序,然后在從1開始，每隔一個gap取一個數，繼續插入排序,直到取完,也就是把插入排序改成如下，gap的值可以為任意值(但是要小于元素個數)。

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

? ? ? ? 通過預排序，可以快速將前面較大的數據轉移到后面。但僅有一個gap的，對數據的有序化有限，此時，就可以遍歷gap的值來增強有序化,那么gap的初值選什么合適呢？gap值選大了就容易漏掉很多數據，取小了效率就低，于是有大佬研究，gap取元素個數的三分之一效率會較高。所以當元素個數為n時，gap=n，gap=n/3.

? ? ? ? 都到這里了，肯定就有人發現了，當gap=1的時候不就是插入排序嗎！那能不能把預排序和插入排序結合起來呢？可以是可以，但是咱們要確保gap的最后取值是1呀，于是對gap有了一點改進:gap=gap/3+1。一眼看上去可能看不出什么苗頭，但是只要代值進去就會發現，gap最后都是1.

? ? ? ? 那么最終的代碼如下,

void TestShellSort(int* a, int n)
{int gap = n;while(gap>1){gap = gap / 3 + 1;for (int i = 0; i < n - gap; i++){int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}
}

3.選擇排序

? ? ? ? 3.1選擇排序

? ? ? ? 選擇排序的思想:每一次從待排序的數據元素中選出最小（或最大）的一個元素，存放在序列的起始位置，直到全部待排序的數據元素排完。

? ? ? ? 以排升序，找小數為例，可以使用假設法找到小數下標，先設0為最小數，和1進行比較，如果0小，那么不變，如果1小，那么下標改為1，遍歷一趟之后咱們就能將最小的值放在開頭，單層循環結束后只需要重新設最小數就能完成排序，于是可以有以下代碼，時間復雜度為O(N).

void SeSort(int* a, int n)
{int left = 0;while (left < n){int min = left;for (int i = left+1; i < n; i++){if (a[min] > a[i])min = i;}Swap(&a[min], &a[left]);left++;}
}

? ? ? ? 此時提出一個問題，能不能同時找到最大值和最小值放到左右兩邊呢？這當然是可以的，但如果最大值位于最小值將要換到的地方或者是最小值位于最大值將要換到的地方呢？咱們需要注意這點，并在交換的時候注意更新數據。

void SelectSort(int* a, int n)
{int right = n-1;int left = 0;while(right>left){int max = left;int min = left;for (int i = left+1; i < n-left; i++){if (a[i] > a[max]){max = i;}if (a[i] < a[min]){min = i;}}Swap(&a[min], &a[left]);//如果重疊，那么更新數據if (max == left)max = min;Swap(&a[max], &a[right]);right--;left++;}
}

????????3.2堆排序

????????堆排序是指利用堆積樹（堆）這種數據結構所設計的一種排序算法,它是選擇排序的一種。它是通過堆來進行選擇數據需要注意的是排升序要建大堆排降序建小堆。其時間復雜度為O(nlogn)。

? ? ? ? 在二叉樹部分也有提過，其核心就是向下調整算法建堆，再將根與最后一個元素交換，調整堆的大小，在向下調整成新的堆，循環操作得到排好的數據。

? ? ? ? 至于向下調整算法建堆可以參見往篇，而排序的過程也只是簡單的控制定義域。

void AdjustDwon(int* a, int n, int root)
{//向下調整,大堆//root*2+1為孩子節點，如果孩子節點存在則循環繼續while(root * 2 + 1<n){//找到兩個孩子中大的那個int child = root * 2 + 1;if (child+1<n && a[child] < a[child + 1]){child = child + 1;}if (child<n && a[child] > a[root]){Swap(&a[child], &a[root]);}root = child;}
}void HeapSort(int* a, int n)
{//最后一個節點的父節點int parent = (n - 1 - 1) / 2;//向下調整建堆for (int i = parent; i >= 0; i--){AdjustDwon(a, n, i);}//選擇，挑出大的數據for (int i = n - 1; i > 0; i--){Swap(&a[0], &a[i]);AdjustDwon(a, i - 1, 0);}
}

? ? ? ? 今天的排序就到這里啦！至于剩下的排序就留到下篇吧！