数据结构 常见的排序算法

🌻个人主页：路飞雪吖~

       🌠专栏：数据结构

---

目录

🌻个人主页：路飞雪吖~

一、插入排序

🌟直接插入排序  

🌟希尔排序  

二、选择排序

🌟选择排序  

🌟堆排序  

三、交换排序

🌟冒泡排序  

🌟快速排序  

⭐递归

✨hoare

✨前后指针版本

⭐非递归 --- 使用栈

四、归并排序

🌟递归  

🌟非递归  

---

如若对你有帮助，记得关注、收藏、点赞哦~ 您的支持是我最大的动力🌹🌹🌹🌹！！！

若有误，望各位，在评论区留言或者私信我 指点迷津！！！谢谢 ヾ(≧▽≦*)o  \( •̀ ω •́ )/

一、插入排序

🌟直接插入排序  

void InsertSort(int* a, int n)
{for (int i = 0; i < n - 1; i++) // n - 1 防止最后一个进随机值{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;}}// 要插入的数据的下标小于0 （所有数据中最小的）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++)// 控制下标，{									  //数据最小的下标放到前面if (a[min] > a[i])				 // 数据最大的下标放到最后{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、用给的数据向下调整，直接建堆；

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

void AdjustDown(int* a, int n, int parent)
{int child = parent * 2 + 1;// 算出父节点的孩节点的下标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)
{// 向下调整 直接建堆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;}
}

三、交换排序

🌟冒泡排序  

注意控制最后一个数据的细节！！！

void BubbleSort(int* a, int n)
{for (int j = 0; j < n - 1; 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、选择最左节点

2、选择随机数

3、三数取中（大小居中的值，也就是不是最大也不是最小的）

<2> 左右指针

Right 先走，找比 keyi 小的值；

Left 后走，找比 keyi 大的值；

R、L 各自找到后进行交换

<3> 小区间选择走插入， 可以减少90%左右的递归。

​​​​​​​

// keyi 三数取中
//大小居中的值，也就是不是最大也不是最小的
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;// 小区间选择走插入， 可以减少90%左右的递归if (right - left + 1 < 10){InsertSort(a + left, right - left + 1);}else{int begin = left;int end = right;随机数做keyi//int randi = rand() % (right - left + 1);//randi += left;//Swap(&a[left], &a[randi]);三数取中//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;}// 各自找到就进行交换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数组中if (a[begin1] <= a[begin2]){temp[i++] = a[begin1++];}else{temp[i++] = a[begin2++];}}// 剩余的直接插入到temp数组中while (begin1 <= end1){temp[i++] = a[begin1++];}while (begin2 <= end2){temp[i++] = a[begin2++];}// 把数据拷贝到原数组里// 每次递归的时候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;
}

🌟非递归  

注意细节控制：

// 归并 --- 非递归
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倍进行排序{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;
}