幾種排序的實現

直接插入排序

直接插入排序是一種簡單的插入排序法，其基本思想是：

把待排序的記錄按其關鍵碼值的大小逐個插入到一個已經排好序的有序序列中，直到所有的記錄插入完為止，得到一個新的有序序列。

實際中我們玩撲克牌時，就用了插入排序的思想：
就是，第一次摸牌我們把它放在第一張，第二次就和第一張比較，比它大就放在他的后面，否則就放在他的前面，摸第三張的時候先和后面大的一張牌開始比較，依次向前。
在這里插入圖片描述
總結來說就是：
當插入第i(i>=1)個元素時，前面的array[0],array[1],…,array[i-1]已經排好序，此時用array[i]的排序碼與array[i-1],array[i-2],…的排序碼順序進行比較，找到插入位置即將array[i]插入，原來位置上的元素順序后移

直接插入排序的特性總結：

元素集合越接近有序，直接插入排序算法的時間效率越高
時間復雜度：O(N^2)
空間復雜度：O(1)，它是一種穩定的排序算法
穩定性：穩定

下面我們對直接插入排序進行代碼的實現
插入排序很簡單
我們將第二個元素開始向后遍歷，i=1，令end=i-1，并且保存a[i]的值
當a[end]大于此前i下標的元素的值時，將其調整，將end位置的值移動到end后面一個位置，同時end–，如果是小于的，那就直接跳出循環，就代表了前面的所有值都是升序的

void insertsort(int* a, int n)
{for (int i = 1; i < n; i++){int end = i - 1;int temp = a[i];while (end >= 0){if (a[end] > temp){a[end + 1] = a[end];end--;}else{break;}}a[end + 1] = temp;}
}

希爾排序

希爾排序法又稱縮小增量法。希爾排序法的基本思想是：先選定一個整數，把待排序文件中所有記錄分成個組，所有距離為的記錄分在同一組內，并對每一組內的記錄進行排序。
在這里插入圖片描述
下面為代碼實現：
我們開始令gap為n的三分之一+1，加一是因為gap不能等于0，一般情況下gap是數組長度的三分之一是比較合適的
后面的邏輯就和插入排序差不多了
后面的for循環時各個分組的數字同時進行排序

void shellsort(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 temp = a[end + gap];while (end >= 0){if (a[end] > a[temp]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = temp;}}
}

希爾排序的特性總結：

希爾排序是對直接插入排序的優化。
當gap > 1時都是預排序，目的是讓數組更接近于有序。當gap == 1時，數組已經接近有序的了，這樣就
會很快。這樣整體而言，可以達到優化的效果。我們實現后可以進行性能測試的對比。
希爾排序的時間復雜度不好計算，因為gap的取值方法很多，導致很難去計算，因此在好些樹中給出的希爾排序的時間復雜度都不固定

選擇排序

選擇排序的思想就是每一次從待排序的數據元素中選出最小（或最大）的一個元素，存放在序列的起始位置，直到全部待排序的數據元素排完。
代碼實現：
第一次找出最大值最小值的下標，然后放在首尾
交換值，然后begin和end分別被前進和后退

void SelectSort(int* a, int n)
{assert(a);int begin = 0, end = n - 1;while (begin < end){int min = begin, max = begin;for (int i = begin; i <= end; i++){if (a[i] >= a[max])max = i;if (a[i] < a[min])min = i;}Swap(&a[begin], &a[min]);//如果最大的位置在begin位置//說明min是和最大的交換位置//這個時候max的位置就發生了變換//max變到了min的位置//所以要更新max的位置if (begin == max)max = min;Swap(&a[end], &a[max]);++begin;--end;}

快速排序

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

總結下來就是：
我們將小于中間位置的值的放在左邊，大于的放在右邊，然后再對左邊進行一樣的劃分，右邊也是，用遞歸實現即可

在實現快排前我們先定義一個找中間下標的函數：
也就是常說的三數取中，有利于更好更快得完成快排

int getmidindex(int* a, int left, int right)
{int midi = (left + right) / 2;if (a[left] < a[midi]){if (a[midi] < a[right]){return midi;}else if (a[left] < a[right]){return right;}elsereturn left;}else//a[left] >=a[midi]{if (a[midi] > a[right]){return midi;}else if (a[left] > a[right]){return right;}elsereturn left;}
}

快速排序一共有三種方法：

hoare版本
這種方法我們統稱為霍爾法：
就是我們將數組的第一個元素的值賦值給key，然后分別從左右開始遍歷，右邊先走，一旦找到比key小的就停下來，然后左邊開始走，左邊找到大的就停下來，然后兩個位置的值互換，知道二者相遇，將key位置的值和他們相遇位置的值交換，最后返回這個位置的下標

代碼實現：

int partsort1(int* a, int left, int right)
{int midi = getmidindex(a, left, right);swap(&a[left], &a[midi]);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 begin, int end)
{if (begin >= end)return;int midi = partsort1(a, begin, end);quicksort(a, begin, midi - 1);quicksort(a, midi + 1, end);
}

挖坑法版本
挖坑法就是把第一個元素存放到臨時變量key中，形成一個坑位，然后右邊先走，右邊遇到比key小的，就把它給此位置的值放入坑位中，此位置就是新的坑位，然后左邊開始找大的，如果出現大的就把值填入坑位中，然后此位置就是新的坑位，一直到left和right相遇時，就把挖出來的key值填入坑位中，并且返回這個坑位的下標

過程如下圖：
最后省略了一部分，依次類推即可

代碼實現如下：

int partsort2(int* a, int left, int right)
{int midi = getmidindex(a, left, right);swap(&a[left], &a[midi]);int hole = left;int key = a[left];while (left < right){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;return hole;
}
void quicksort(int* a, int begin, int end)
{if (begin >= end)return;int midi = partsort1(a, begin, end);quicksort(a, begin, midi - 1);quicksort(a, midi + 1, end);
}

前后指針版本
我們首先令第一個位置的下標為prev，他的下一個位置為cur，并且記錄第一個位置的值為key
然后cur先后遍歷，當cur遇到小于key的值時，將prev和cur位置的值交換，并且再prev+1不等于cur的情況下prev進行+1操作（如果是等于的話就是自己和自己交換，沒有什么意義），同時cur++，當遍歷完成時，最后交換prev位置的值和key的值，返回prev位置的下標

遍歷過程如下：

代碼實現：

int partsort3(int* a, int left, int right)
{int midi = getmidindex(a, left, right);swap(&a[left], &a[midi]);int prev = left;int cur = left + 1;int keyi = left;while (cur <= right){if (a[keyi] > a[cur] && ++prev != cur){swap(&a[prev] ,&a[cur]);}cur++;}swap(&a[prev] ,&a[keyi]);keyi = prev;return keyi;
}
void quicksort(int* a, int begin, int end)
{if (begin >= end)return;int midi = partsort1(a, begin, end);quicksort(a, begin, midi - 1);quicksort(a, midi + 1, end);
}

歸并排序

歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide andConquer）的一個非常典型的應用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。
他的大概步驟如下：
在這里插入圖片描述
歸并排序的遞歸很簡單：
就是將區間逐一劃分
并且得開辟一塊新的空間，最后將temp直接全部memcpy到目標空間a中

void _mergesort(int* a, int begin, int end, int* temp)
{if (begin >= end)return;int midi = (begin + end) / 2;_mergesort(a,begin, midi,temp);_mergesort(a,midi + 1, end,temp);int begin1 = begin;int begin2 = midi + 1;int end1 = midi;int end2 = end;int i = begin;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){temp[i++] = a[begin1++];}else{temp[i++] = a[begin2++];}}while (begin1 <= end1){temp[i++] = a[begin1++];}while (begin2 <= end2){temp[i++] = a[begin2++];}memcpy(a + begin, temp + begin, sizeof(int) * (end - begin + 1));
}
void mergesort(int* a, int n)
{int* temp = (int*)malloc(sizeof(int)*n);_mergesort(a, 0, n-1, temp);free(temp);
}

非遞歸就有點難了：

void mergesortnonr(int* a, int n)
{int* temp =(int*)malloc(sizeof(int) * n);if (temp == NULL){perror("malloc");}int gap = 1;while (gap < n){int j = 0;for (int i = 0; i < n; i += 2*gap){int begin1 = i;int begin2 = i + gap;int end1 = i + gap-1;int end2 = i + 2 * gap - 1;if (end1 >= n || begin2 >= n){break;}if (end2 >= n){end2 = n - 1;//修正}while (begin1 <= end1 && begin2 <= end2){if (a[begin1] <= a[begin2]){temp[j++] = a[begin1++];}else{temp[j++] = a[begin2++];}}while (begin1 <= end1){temp[j++] = a[begin1++];}while (begin2 <= end2){temp[j++] = a[begin2++];}//每歸并完一組就拷貝一組memcpy(a + i, temp + i, sizeof(int) * (end2 - i + 1));}gap *= 2;}free(temp);
}

歸并排序的特性總結：

歸并的缺點在于需要O(N)的空間復雜度，歸并排序的思考更多的是解決在磁盤中的外排序問題。
時間復雜度：O(N*logN)
空間復雜度：O(N)
穩定性：穩定

計數排序

思想：計數排序又稱為鴿巢原理，是對哈希直接定址法的變形應用。操作步驟：

統計相同元素出現次數
根據統計的結果將序列回收到原來的序列中
其實計數排序就是用到了數組的映射，當數組元素過多時就不適用了，但是效率很高：

void countsort(int* a, int n)
{int i = 0;int j = 0;int max = a[0];int min = a[0];for (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*)malloc(sizeof(int) * n);memset(count, 0, sizeof(int) * range);for (i = 0; i < n; i++){count[a[i] - min]++;}int k = 0;for (j = 0; j < range; j++){while (count[j]--){a[k++] = j + min;}}
}

計數排序的特性總結：