🌻個(gè)人主頁：路飛雪吖~

? ? ? ?🌠專欄：數(shù)據(jù)結(jié)構(gòu)

---

目錄

🌻個(gè)人主頁：路飛雪吖~

一、插入排序

🌟直接插入排序??

🌟希爾排序??

二、選擇排序

🌟選擇排序??

🌟堆排序??

三、交換排序

🌟冒泡排序??

🌟快速排序??

?遞歸

?hoare

?前后指針版本

?非遞歸 --- 使用棧

四、歸并排序

🌟遞歸??

🌟非遞歸??

---

如若對你有幫助，記得關(guān)注、收藏、點(diǎn)贊哦~ 您的支持是我最大的動力🌹🌹🌹🌹！！！

若有誤，望各位，在評論區(qū)留言或者私信我 指點(diǎn)迷津！！！謝謝 ヾ(≧▽≦*)o? \( ?? ω ?? )/

一、插入排序

🌟直接插入排序??

void InsertSort(int* a, int n)
{for (int i = 0; i < n - 1; i++) // n - 1 防止最后一個(gè)進(jìn)隨機(jī)值{int end = i;int temp = a[end + 1];// 單趟while (end >= 0){if (temp < a[end]) // 把大的放后面{a[end + 1] = a[end];--end;}else {a[end + 1] = temp;break;}}// 要插入的數(shù)據(jù)的下標(biāo)小于0 （所有數(shù)據(jù)中最小的）a[end + 1] = temp;}
}

🌟希爾排序??

void ShellSort(int* a, int n)
{int gap = n;while (gap > 1) // 逐漸有序{gap /= 2;for (int i = 0; i < n - gap; i++) {int end = i;int temp = a[end + gap];while (end >= 0){if (temp < a[end]){a[end + gap] = a[end];end -= gap;}else{a[end + gap] = temp;break;}}a[end + gap] = temp;}}
}

二、選擇排序

🌟選擇排序??

void SelectSort(int* a, int n)
{int begin = 0;int end = n - 1;while(begin < end){int min = begin, max = begin;for (int i = begin + 1; i <= end; i++)// 控制下標(biāo)，{									  //數(shù)據(jù)最小的下標(biāo)放到前面if (a[min] > a[i])				 // 數(shù)據(jù)最大的下標(biāo)放到最后{min = i;}if (a[max] < a[i]){max = i;}}Swap(&a[begin], &a[min]);if (max == begin) // 小坑，注意畫圖{max = min;}Swap(&a[end], &a[max]);++begin;--end;}}

🌟堆排序??

1、用給的數(shù)據(jù)向下調(diào)整，直接建堆；

2、首尾交換，升序建大堆。

void AdjustDown(int* a, int n, int parent)
{int child = parent * 2 + 1;// 算出父節(jié)點(diǎn)的孩節(jié)點(diǎn)的下標(biāo)while (child < n){if (child + 1 < n && a[child + 1] > a[child]){++child;}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);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);}// 升序建大堆int end = n - 1;while (end >= 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);--end;}
}

三、交換排序

🌟冒泡排序??

注意控制最后一個(gè)數(shù)據(jù)的細(xì)節(jié)！！！

void BubbleSort(int* a, int n)
{for (int j = 0; j < n - 1; j++){// 一趟數(shù)據(jù)for (int i = 0; i < n - 1 - j; i++){if (a[i] > a[i + 1]){Swap(&a[i], &a[i + 1]);}}}
}

🌟快速排序??

?遞歸

?hoare

<1> keyi 的選擇：

1、選擇最左節(jié)點(diǎn)

2、選擇隨機(jī)數(shù)

3、三數(shù)取中（大小居中的值，也就是不是最大也不是最小的）

<2> 左右指針

Right 先走，找比 keyi 小的值；

Left 后走，找比 keyi 大的值；

R、L 各自找到后進(jìn)行交換

<3> 小區(qū)間選擇走插入， 可以減少90%左右的遞歸。

???????

// keyi 三數(shù)取中
//大小居中的值，也就是不是最大也不是最小的
int GetMid(int* a, int left, int right)
{int mid = (right - left) / 2;if (a[left] < a[mid]){if (a[mid] < a[right]){return mid;}else if (a[left] > a[right]){return left;}else{return right;}}else // a[left] > a[mid]{if (a[right] > a[left]){return left;}else if (a[right] < a[mid]){return mid;}else{return right;}}
}// 遞歸 -- hoare
void QuickSort(int* a, int left, int right)
{if (left >= right)return;// 小區(qū)間選擇走插入， 可以減少90%左右的遞歸if (right - left + 1 < 10){InsertSort(a + left, right - left + 1);}else{int begin = left;int end = right;隨機(jī)數(shù)做keyi//int randi = rand() % (right - left + 1);//randi += left;//Swap(&a[left], &a[randi]);三數(shù)取中//int mid = GetMid(a, left, right);//Swap(&a[left], &a[mid]);int keyi = left;while (left < right){// 找小// left < right 防止right越界while (left < right && a[right] >= a[keyi]){--right;}// 找大while (left < right && a[left] <= a[keyi]){++left;}// 各自找到就進(jìn)行交換Swap(&a[left], &a[right]);}// 相遇Swap(&a[keyi], &a[left]);keyi = left;// [begin, keyi - 1] keyi [ keyi + 1, end]QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);}
}

?前后指針版本

?

// 遞歸 -- 指針法
void QuickSort1(int* a, int left, int right)
{if (left >= right)return;int keyi = left;int prev = left;int cur = left + 1;while (cur <= right){if (a[cur] < a[keyi]){++prev;Swap(&a[prev], &a[cur]);++cur;}else{++cur;}}Swap(&a[keyi], &a[prev]);keyi = prev;// [left, keyi - 1] keyi [ keyi + 1, right]QuickSort1(a, left, keyi - 1);QuickSort1(a, keyi + 1, right);
}

?非遞歸 --- 使用棧

先放Right，再放Left：

#include"Stack.h"
// 非遞歸 -- 棧
void QuickSortNonR(int* a, int left, int right)
{ST st;STInit(&st);STPush(&st, right);STPush(&st, left);while (!STEmpty(&st)){int begin = STTop(&st);STPop(&st);int end = STTop(&st);STPop(&st);// 走單趟int keyi = begin;int prev = begin;int cur = begin + 1;while (cur <= end){if (a[cur] < a[keyi] && ++prev != cur)Swap(&a[prev], &a[cur]);++cur;}Swap(&a[keyi], &a[prev]);keyi = prev;// [begin, keyi - 1] keyi [ keyi + 1, end]if (keyi + 1 < end){STPush(&st, end);STPush(&st, keyi + 1);}if (begin < keyi - 1){STPush(&st, keyi - 1);STPush(&st, begin);}}STDestroy(&st);
}

四、歸并排序

🌟遞歸??

分治思想：

void _MergeSort(int* a, int begin, int end, int* temp)
{if (begin == end)return;int mid = (begin + end) / 2;// [begin, mid] [mid+1, end]_MergeSort(a, begin, mid, temp);_MergeSort(a, mid + 1, end, temp);// 歸并int begin1 = begin, end1 = mid;int begin2 = mid + 1, end2 = end;int i = begin;while (begin1 <= end1 && begin2 <= end2){// 把小的先尾插到temp數(shù)組中if (a[begin1] <= a[begin2]){temp[i++] = a[begin1++];}else{temp[i++] = a[begin2++];}}// 剩余的直接插入到temp數(shù)組中while (begin1 <= end1){temp[i++] = a[begin1++];}while (begin2 <= end2){temp[i++] = a[begin2++];}// 把數(shù)據(jù)拷貝到原數(shù)組里// 每次遞歸的時(shí)候a, temp 的位置可能不同，所以要加上begin memcpy(a + begin, temp + begin, sizeof(int) * (end - begin + 1));
}// 歸并 -- 遞歸
void MergeSort1(int* a, int n)
{int* temp = (int*)malloc(sizeof(int) * n);if (temp == NULL){perror("malloc fail");return;}_MergeSort(a, 0, n - 1, temp);free(temp);temp = NULL;
}

🌟非遞歸??

注意細(xì)節(jié)控制：

// 歸并 --- 非遞歸
void MergeSort(int* a, int n)
{int* temp = (int*)malloc(sizeof(int) * n);if (temp == NULL){perror("malloc fail");return;}int gap = 1;while (gap < n){for (int i = 0; i < n; i += 2 * gap) // 成gap倍進(jìn)行排序{int begin1 = i, end1 = begin1 + gap - 1;int begin2 = begin1 + gap, end2 = begin2 + gap - 1;// 越界的問題處理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]){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);temp = NULL;
}