排序下---(冒泡排序，快速排序，快速排序優化，快速排序非遞歸，歸并排序，計數排序)

排序上

交換類排序

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

冒泡排序

在這里插入圖片描述

冒泡排序的特性總結：

冒泡排序是一種非常容易理解的排序
時間復雜度：O(N^2)
空間復雜度：O(1)
穩定性：穩定

代碼實現

void BublleSort(int*array, int size)
{for (int i = 0; i < size - 1; ++i)       //總共冒泡的趟數{//冒泡的方式----->用相鄰元素進行比較for (int j = 0; j < size - i - 1; ++j)		//一次冒泡{if (array[j]>array[j + 1])Swap(&array[j], &array[j + 1]);}}
}

冒泡排序優化

void BublleSort(int*array, int size)
{	for (int i = 0; i < size - 1; ++i)       //總共冒泡的趟數{int IsChange = 0;			//查看這一趟有沒有交換//冒泡的方式----->用相鄰元素進行比較for (int j = 0; j < size - i - 1; ++j)		//一次冒泡{if (array[j]>array[j + 1]){Swap(&array[j], &array[j + 1]);IsChange = 1;}	}if (!IsChange)  //如果沒有交換return;}
}

快速排序

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

快速排序的特性總結：

快速排序整體的綜合性能和使用場景都是比較好的，所以才敢叫快速排序
時間復雜度：O(N*logN)，最差場景，單支樹O(N2)
空間復雜度：O(logN)
穩定性：不穩定
快排參考鏈接

代碼實現

int Partion(int*array, int left, int right)
{//劃分基準值
}
void QuickSort(int *array, int left, int right)
{if (right - left > 1){int div = Partion(array, left, right);QuickSort(array, left, div);QuickSort(array, div + 1, right);}
}

劃分基準值的方式

hoare版本

int Partion(int*array, int left, int right)
{int key = array[right - 1];int begin = left;int end = right - 1;while (begin<end){//從前往后找比基準值大的元素，找到就停下來,等于也往前走，因為找的是大的while (begin < end&&array[begin] <= key)begin++;//end從后往前找比基準值小的元素，找到就停下來，等于也往前走，找的是小的，不是等于while (begin < end&&array[end] >= key)end--;if (begin < end)Swap(&array[begin], &array[end]);}if (begin != right - 1)Swap(&array[begin], &array[right-1]);return begin;
}

挖坑法

int Partion2(int*array, int left, int right)
{int key = array[right - 1];int begin = left;int end = right - 1;while (begin<end){while (begin<end&&array[begin] <= key)begin++;if (begin<end){//上一個坑是end，begin是比基準值大的數array[end] = array[begin];end--;}while (begin<end&&array[end] >= key)end--;if (begin<end){//上次坑是end，填坑的是begin，填完坑后，begin成坑，由新end比基準值小的數來填array[begin] = array[end];begin++;}}array[begin] = key;return begin;
}

前后指針版本

int Partion3(int*array, int left, int right)
{int key = array[right - 1];int cur = left;int pre = cur - 1;while (cur<right){if (array[cur] < key && ++pre != cur)Swap(&array[cur], &array[pre]);cur++;}if (++pre != right - 1)Swap(&array[pre], &array[right - 1]);return pre;
}

快排的優化

三數取中法選key
遞歸到小的子區間時，可以考慮使用插入排序

三數取中法

//三數取中法
int GetMiddleIdx(int*array, int left, int right)
{int mid = left + ((right - left) >> 1);//left mid right-1if (array[left] < array[right - 1]){if (array[mid] < array[left])return left;else if (array[mid]>array[right - 1])return right - 1;elsereturn mid;}else{if (array[mid] > array[left])return left;else if (array[mid] < array[right - 1])return right - 1;elsereturn mid;}
}
int Partion(int*array, int left, int right)
{int middle = GetMiddleIdx(array, left, right);if (middle != right - 1)Swap(&array[middle], &array[right - 1]);int key = array[right - 1];int begin = left;int end = right - 1;while (begin<end){//從前往后找比基準值大的元素，找到就停下來,等于也往前走，因為找的是大的while (begin < end&&array[begin] <= key)begin++;//end從后往前找比基準值小的元素，找到就停下來，等于也往前走，找的是小的，不是等于while (begin < end&&array[end] >= key)end--;if (begin < end)Swap(&array[begin], &array[end]);}if (begin != right - 1)Swap(&array[begin], &array[right - 1]);return begin;
}

元素個數小用直接插入排序

void QuickSort(int *array, int left, int right)
{if (right - left < 16)//如果快排的元素個數沒有達到16及其以上，就用插入排序InsertSort(array, right - left);else{int div = Partion(array, left, right);QuickSort(array, left, div);QuickSort(array, div + 1, right);}
}

快速排序非遞歸寫法

#include"stack.h"
//快排非遞歸
void QuickSortNor(int*array, int size)
{int left = 0;int right = size;Stack s;StackInit(&s);StackPush(&s,right);StackPush(&s,left); //后進去的先出來，先出來的是左while (!StackEmpty(&s)){left = StackTop(&s);StackPop(&s);right = StackTop(&s);StackPop(&s);if (left < right){int div = Partion3(array, left, right);//先保存右半部分,先進后出來StackPush(&s,right);//右半部分右邊界StackPush(&s, div + 1);//右半部分左邊界//再保存左邊部分，后進先出來StackPush(&s, div);//左半部分右邊界StackPush(&s, left);//左半部分左邊界}}StackDestroy(&s);
}

歸并排序

基本思想：

歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide andConquer）的一個非常典型的應用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。
在這里插入圖片描述

歸并排序的特性總結：

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

代碼實現

//歸并到temp臨時空間里
//兩個有序序列合并成一個
void MergeData(int*array, int left, int mid, int right, int *temp)
{int begin1 = left, end1 = mid;int begin2 = mid, end2 = right;int index = left;while (begin1 < end1 && begin2 < end2)//第一個和第二個區間里的元素沒有處理完{if (array[begin1] < array[begin2])temp[index++] = array[begin1++];elsetemp[index++] = array[begin2++];}//如果第一個空間里的數沒有搬移完while (begin1 < end1)temp[index++] = array[begin1++];//第一個空間搬移完了，第二個空間里的元素沒有搬移完while (begin2 < end2)temp[index++] = array[begin2++];
}
void _MergeSort(int*array, int left, int right,int*temp)
{//int*temp=(int*)malloc(sizeof(array[left])*(right-left));if (right - left>1) //區間里的元素超過一個，再排序{//找中間位置int mid = left + ((right - left) >> 1);_MergeSort(array, left, mid,temp);_MergeSort(array, mid, right,temp);MergeData(array, left, mid, right, temp);memcpy(array + left, temp + left, sizeof(array[left])*(right - left));}
}
void MergeSort(int *array, int size)
{int *temp = (int*)malloc(size*sizeof(array[0]));if (NULL == temp){assert(0);return;}_MergeSort(array, 0, size, temp);free(temp);
}

歸并排序非遞歸

void MergeSortNor(int *array, int size)
{int *temp = (int*)malloc(size*sizeof(array[0]));if (NULL == temp){assert(0);return;}int gap = 1;while (gap < size){for (int i = 0; i < size; i += 2 * gap){int left = i;//左int mid = left + gap;//中int right = mid + gap;//右if (mid >= size)mid = size;if (right >= size)right = size;MergeData(array, left, mid, right, temp);}memcpy(array, temp, (sizeof(array[0])*size));gap *= 2;}free(temp);
}

非比較排序

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

在這里插入圖片描述
操作步驟：

統計相同元素出現次數
根據統計的結果將序列回收到原來的序列中

在這里插入圖片描述

計數排序的特性總結：

計數排序在數據范圍集中時，效率很高，但是適用范圍及場景有限。
時間復雜度：O(MAX(N,范圍))
空間復雜度：O(范圍)
穩定性：穩定

代碼實現

//場景:數據密集集中在某個范圍中
void CountSort(int*array, int size)
{int minVal = array[0];//范圍的左邊界值int maxVal = array[0];//范圍的右邊界值//1--找數據的范圍for (int i = 1; i < size; ++i){if (array[i] < minVal)minVal = array[i];if (array[i]>maxVal)maxVal = array[i];}//2--計算保存計數的空間int range = maxVal - minVal + 1;int *temp = (int*)malloc(sizeof(int)*range);if (NULL == temp){assert(0);return;}//3---空間位置里全部置為0memset(temp, 0, sizeof(int)*range);//memeset 按一個一個字節賦值，賦值0可以，賦值其他值不行，例如100，給一個字節賦值100//4--統計每個數據出現的次數for (int i = 0; i < size; ++i){temp[array[i] - minVal]++;}//5--回收數據int index = 0;for (int i = 0; i < range; ++i){while (temp[i]--)  //當前元素值不為0，說明該下標還有個數	{array[index++] = i + minVal;}}free(temp);
}