目錄

引言

一：InsertSort(直接插入排序)

?二：ShellSort(希爾排序)

?三：BubbleSort(冒泡排序)

四： HeapSort(堆排序)

五：SelectSort(直接選擇排序)

六：QuickSort(快速排序)

?1.Hoare版本

2.前后指針版本?

3.非遞歸版本?

4.快排之三路劃分

5.SGI-IntrospectiveSort(自省排序)

七：MergeSort(歸并排序)?

1.遞歸版本

2.非遞歸版本?

?八：CountSort(計數(shù)排序)

?

接下來的日子會順順利利，萬事勝意，生活明朗-----------林辭憂?

引言

在日常生活當中任何地方都有著排序的思想，對于網(wǎng)購時價格排序，銷量排序，好評排序等各種排名，因此對于學習排序算法是很重要，對于排序算法有常見的八種，它們分別是? InsertSort(直接插入排序)? ? ShellSort(希爾排序)? ? BubbleSort(冒泡排序)? ? ?HeapSort(堆排序)? ? ?SelectSort(直接選擇排序)? ? ?QuickSort(快速排序)? ? ?MergeSort(歸并排序)? ? ?CountSort(計數(shù)排序)? ?對于其他的如桶排序，奇數(shù)排序等實際用處不大，很少使用。接下來就介紹這八種排序算法

一：InsertSort(直接插入排序)

1.動圖

2.思想：把待排序的記錄按其關(guān)鍵碼值的大小逐個插入到一個已經(jīng)排好序的有序序列中，直到所有的記錄插入完為止，得到一個新的有序序列

void InsertSort(int* a, int n)
{//[0,end]有序，插入a[end+1]for (int i = 0; i < n - 1; ++i){int end=i;int tmp = a[end + 1];while (end>=0){if (a[end] > tmp){a[end + 1] = a[end];--end;}else{break;}}a[end + 1] = tmp;}
}

3.時間復雜度：O(N^2)? ? 最壞情況是逆序，最好情況是有序或者接近有序O(N)

?二：ShellSort(希爾排序)

1.圖片演示

2.思想：

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

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

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

void ShellSort(int* a, int n)
{//當gap>1時為預排序，目的是為了接近有序//當gap==1時為直接插入排序//間隔為gap的分為一組，總共gap組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 (a[end] > tmp){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}
}

?三：BubbleSort(冒泡排序)

1.動圖展示

2. 代碼實現(xiàn)

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

3.時間復雜度O(N^2)?

詳細介紹可參考https://blog.csdn.net/Miwll/article/details/135315155?spm=1001.2014.3001.5501

四： HeapSort(堆排序)

1.圖片展示

2.思想及代碼實現(xiàn)

void AdjustDown(int* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){if (child + 1 < n && a[child] < a[child + 1]){++child;}if (a[parent] < a[child]){Swap(&a[parent],&a[child]);parent = child;child = parent * 2 + 1;}else{break;}}
}
void HeapSort(int* a, int n)
{//排升序建大根堆--向下調(diào)整建堆for (int i = (n - 1 - 1) / 2; i >= 0; --i){AdjustDown(a, n, i);}//排數(shù)據(jù)--首尾交換再向下調(diào)整int end = n - 1;while (end){Swap(&a[end], &a[0]);AdjustDown(a, end, 0);--end;}
}

時間復雜度為O(N*logN)?

詳細可以參考https://blog.csdn.net/Miwll/article/details/136636869?spm=1001.2014.3001.5501

五：SelectSort(直接選擇排序)

1.動圖顯示

2.思想及實現(xiàn)

void SelectSort(int* a, int n)
{//遍歷一遍選出最大和最小值下標，再收尾交換int begin = 0, end = n - 1;int maxi = 0, mini = 0;while (begin < end){for (int i = begin; i <= end; ++i){if (a[i] > a[maxi]) maxi = i;if (a[i] < a[mini]) mini = i;}Swap(&a[begin], &a[mini]);if (begin == maxi){maxi = mini;}Swap(&a[end], &a[maxi]);begin++;end--;}
}

這里需要注意當begin和maxi重疊的情況

時間復雜度：O(N^2)

六：QuickSort(快速排序)

?1.Hoare版本

1.動圖展示

2.思想及實現(xiàn)

對于Hoare版本的快排是選取一個key值，然后先讓右邊先走找小，再左邊找大，再交換繼續(xù)往后直至相遇，再交換key位置處的值，再以相遇位置為劃分子區(qū)間繼續(xù)執(zhí)行

畫一部分遞歸展開圖理解最小子問題的條件

?

3.為啥相遇位置一定比key值小？---右邊先走保證的

?

4.快排的時間復雜度為O(N*logN),但在有序或者接近有序的情況下最壞為O(N^2),為了防止出現(xiàn)最壞的情況，可以使用三數(shù)取中或者隨機選key來解決問題

//2.三數(shù)取中
int mid = GetMidi(a,begin, end);
Swap(&a[begin], &a[mid]);int GetMidi(int*a,int left, int right)
{int mid = (left + right) / 2;if (a[left] < a[mid]){if (a[right] > a[mid])//mid>left right>mid{return mid;}else if (a[left] > a[right])//mid>left right<mid{return left;}else{return right;}}else //left>mid{if (a[right] < a[mid])//right<mid{return mid;}else if (a[left] > a[right])//right>mid {return right;}else{return left;}}
}

5.小區(qū)間優(yōu)化? 由于到最后的幾步時，遞歸的深度和廣度是非常巨大的，因此可以采用小區(qū)間優(yōu)化的方式減少遞歸，這里可以采用插入排序

void QuickSort1(int* a, int begin, int end)
{//最小子問題--區(qū)間不存在或者只有一個數(shù)據(jù)if (begin >= end) return;//1.隨機選key---選[left, right]區(qū)間中的隨機數(shù)做key//int randi = rand() % (end - begin + 1);//randi += begin;//在遞歸時begin不一定是0開始的//Swap(&a[begin],&a[randi]);if (end - begin + 1 < 10){InsertSort(a+begin, end - begin + 1);}else{//2.三數(shù)取中int mid = GetMidi(a, begin, end);Swap(&a[begin], &a[mid]);int keyi = begin;int left = begin, right = end;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]);keyi = left;//[begin,keyi-1] keyi [keyi+1,end]QuickSort1(a, begin, keyi - 1);QuickSort1(a, keyi + 1, end);}
}

2.前后指針版本?

?1.動圖展示

2.思想及實現(xiàn)

當cur處的值>=key時，++cur

當cur處的值<key時，++prev,再交換prev和cur的值，再++cur

void QuickSort2(int* a, int begin, int end)
{if (begin >= end) return;int prev = begin;int cur = begin + 1;int keyi = begin;while (cur <= end){if (a[cur] < a[keyi] && ++prev != cur){Swap(&a[prev],&a[cur]);}++cur;}Swap(&a[prev],&a[keyi]);keyi = prev;//[begin,keyi-1]keyi[keyi+1,end]QuickSort2(a, begin, keyi - 1);QuickSort2(a, keyi + 1, end);
}

3.非遞歸版本?

對于遞歸如果深度太深的話，就會導致棧溢出，因此用棧實現(xiàn)非遞歸版本很重要

思想：走一趟單趟，再右左區(qū)間入棧

void QuickSortNonR(int* a, int begin, int end)
{ST st;STInit(&st);//先入右再入左STPush(&st, end);STPush(&st, begin);while (!STEmpty(&st)){int left = STTop(&st);STPop(&st);int right = STTop(&st);STPop(&st);//單趟int keyi = left;int cur = left + 1;int prev = left;while (cur <= right){if (a[cur] < a[keyi] && ++prev != cur)Swap(&a[cur],&a[prev]);++cur;}Swap(&a[prev], &a[keyi]);keyi = prev;//[left,keyi-1]keyi[keyi+1,right]//保證入的區(qū)間有效if (keyi + 1 < right){STPush(&st, right);STPush(&st, keyi + 1);}if (left < keyi -1){STPush(&st, keyi - 1);STPush(&st, left);}//Print(a, left, right);}STDestroy(&st);
}

4.快排之三路劃分

1.快排性能的關(guān)鍵點分析

決定快排性能的關(guān)鍵點是每次單趟排序后，key對數(shù)組的分割，如果每次選key基本?分居中，那么快 排的遞歸樹就是顆均勻的滿?叉樹，性能最佳。但是實踐中雖然不可能每次都是?分居中，但是性能 也還是可控的。但是如果出現(xiàn)每次選到最?值/最?值，劃分為0個和N-1的?問題時，時間復雜度為 O(N^2)，數(shù)組序列有序時就會出現(xiàn)這樣的問題，我們前?已經(jīng)?三數(shù)取中或者隨機選key解決了這個問 題，也就是說我們解決了絕?多數(shù)的問題，但是現(xiàn)在還是有?些場景沒解決(數(shù)組中有?量重復數(shù)據(jù)時)，即以下情況

?此時就提出了采用三路劃分的思想來解決

這樣再對比key大的數(shù)據(jù)區(qū)間和比key小的數(shù)據(jù)區(qū)間進行遞歸

//三路劃分
void QuickSort3(int* a, int begin, int end)
{//最小子問題if (begin >= end) return;int left = begin, right = end;int key = a[left];int cur = left + 1;while (cur <= right){if (a[cur] < key){Swap(&a[left], &a[cur]);++cur;++left;}else if(a[cur]>key){Swap(&a[cur],&a[right]);--right;}else{++cur;}}//[begin,left-1][left,right][right+1,end]QuickSort3(a, begin, left - 1);QuickSort3(a, right+1, end);
}

5.SGI-IntrospectiveSort(自省排序)

?introsort是introspectivesort采?了縮寫，他的名字其實表達了他的實現(xiàn)思路，他的思路就是進?? 我偵測和反省，快排遞歸深度太深（sgistl中使?的是深度為2倍排序元素數(shù)量的對數(shù)值）那就說明在 這種數(shù)據(jù)序列下，選key出現(xiàn)了問題，性能在快速退化，那么就不要再進?快排分割遞歸了，改換為堆 排序進?排序

void IntroSort(int* a, int left, int right, int depth, int defaultDepth)
{if (left >= right)return;// 數(shù)組長度?于16的?數(shù)組，換為插入排序，簡單遞歸次數(shù)---小區(qū)間優(yōu)化    if (right - left + 1 < 16){InsertSort(a + left, right - left + 1);return;}// 當深度超過2 * logN時改用堆排序    if (depth > defaultDepth){HeapSort(a + left, right - left + 1);return;}depth++;int begin = left;int end = right;// 隨機選keyint randi = left + (rand() % (right - left));Swap(&a[left], &a[randi]);int prev = left;int cur = prev + 1;int keyi = left;while (cur <= right){if (a[cur] < a[keyi] && ++prev != cur){Swap(&a[prev], &a[cur]);}++cur;}Swap(&a[prev], &a[keyi]);keyi = prev;// [begin, keyi-1] keyi [keyi+1, end]IntroSort(a, begin, keyi - 1, depth, defaultDepth);IntroSort(a, keyi + 1, end, depth, defaultDepth);
}void QuickSort4(int* a, int begin, int end)
{int depth = 0;int logn = 0;int N= end - begin + 1;for (int i = 1; i < N; i *= 2){logn++;}// introspective sort -- 自省排序IntroSort(a, begin, end, depth, logn * 2);
}

七：MergeSort(歸并排序)?

1.遞歸版本

1.動圖演示

?2.思想及實現(xiàn)

void _MergeSort(int* a, int left,int right,int*tmp)
{//最小子問題if (left == right) return;int mid = (left + right) / 2;//[begin,mid][mid+1,end]_MergeSort(a, left, mid, tmp);_MergeSort(a, mid + 1, right, tmp);//開始歸并int begin1 = left, end1=mid;int begin2=mid+1, end2=right;int i = left;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] <= a[begin2]){tmp[i++] = a[begin1++];}else{tmp[i++] = a[begin2++];}}while (begin1 <= end1){tmp[i++] = a[begin1++];}while (begin2 <= end2){tmp[i++] = a[begin2++];}memcpy(a + left, tmp + left, sizeof(int) * (right-left+1));
}
void MergeSort(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail\n");return;}_MergeSort(a, 0, n - 1, tmp);free(tmp);tmp = NULL;
}

?部分遞歸展開

2.非遞歸版本?

這里的非遞歸版本采用循環(huán)的方式來解決

void MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail\n");return;}int gap = 1;while (gap < n){for (int i = 0; i < n; i += 2 * gap){int begin1 = i, end1 = begin1 + gap - 1;int begin2 = end1 + 1, end2 = begin2 + gap - 1;//調(diào)整越界問題if (end1 >= n || begin2 >= n){break;}if (end2 >= n)//修正{end2 = n - 1;}int j = i;while (begin1 <= end1 && begin2 <= end2){//取小的尾插if (a[begin1] <= a[begin2]){tmp[j++] = a[begin1++];}else{tmp[j++] = a[begin2++];}}while (begin1 <= end1){tmp[j++] = a[begin1++];}while (begin2 <= end2){tmp[j++] = a[begin2++];}memcpy(a + i, tmp + i, sizeof(int) * (end2-i+1));}gap *= 2;}
}

?八：CountSort(計數(shù)排序)

1.思想及實現(xiàn)

開辟一個數(shù)組用來統(tǒng)計每個數(shù)據(jù)出現(xiàn)的次數(shù)，在相對映射位置的次數(shù)++，然后再往原數(shù)組寫入數(shù)據(jù)，適合于整形且數(shù)據(jù)集中的

void CountSort(int* a, int n)
{int min = a[0];int max = a[0];for (int i = 1; i < n; ++i){if (min > a[i]) min = a[i];if (max < a[i]) max = a[i];}int range = max - min + 1;int* count = (int*)malloc(sizeof(int) * range);if (count == NULL){perror("malloc fail\n");return;}memset(count, 0, sizeof(int) * range);//統(tǒng)計次數(shù)for (int i = 0; i < n; ++i){count[a[i] - min]++;}//寫回原數(shù)組int j = 0;for (int i = 0; i < range; ++i){while (count[i]--){a[j++] = i + min;}}
}

?總結(jié)