当前位置：首页 > news >正文

数据结构(初阶7)---七大排序法(堆排序，快速排序，归并排序，希尔排序，冒泡排序，选择排序，插入排序)(详解)

news 来源：原创 2025/7/18 3:04:42

排序

1.插入排序
2.希尔排序
3.冒泡排序
4.选择排序(双头排序优化版)
5.堆排序
6.快速排序
- 1). 双指针法
- 2).前后指针法
- 3).非递归法
7.归并排序
- 1).递归版本(递归的回退就是归并)
- 2).非递归版本(迭代版本)

计算机执行的最多的操作之一就有排序，排序是一项极其重要的技能
接下来我们来详细介绍一下，我们遇到最多的排序方法

1.插入排序

首先我们介绍的是最基本的排序方式，插入排序

给定一个数组
[2,3,5,7,6,4,1]
请添加图片描述

代码实现：如何在数组中实现插入呢，
1.先将p+1的值记住。
2.从后向前遍历，找到比它小的前一个数
3.在遍历的时候，只需要将后面的值赋值给前面的值

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

这是最基本的排序方式
遍历了n+(n-1)+(n-2)+…+1
共计时间复杂度为O(n^2);

2.希尔排序

希尔排序是插入排序的升级版，是一种强大的排序方式。
我们发现如果我们正常使用选择排序，如果我的极值在数组的两头，我们就需要花费更多的时间将两头的元素一步一步的移到另一端，所以希尔大佬就发明了一种跳跃式移动的方法——希尔排序

给定一个数组：[5,3,2,4,1,2,2,3,4]需要排为升序
请添加图片描述
所以我们可以去迭代gap，让gap从sz/3开始逐渐向1迭代，
这样数列逐渐有序->最终变为有序

void ShellSort(int*a,int n)
{int gap=n;while (gap > 1){gap = gap / 3 + 1;for (int count = 0; count < n - gap; count++){int end = count;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}
}

在实际应用中，希尔排序的平均时间复杂度通常被认为是
O(n log n)到O(n^(1.2)) 之间

3.冒泡排序

冒泡排序应该是所有初学者第一次学习的排序算法，也是效率最低的一种算法

这里就不过多赘述
通过一次次的冒泡排序，每一次都将一个数字移到正确的位置

void swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}
void bubblesort(int *p,int sz)
{for (int count = 0; count < sz; count++){for (int cur = 0; cur < sz - count-1; cur++){if (p[cur] > p[cur+1]){swap(p + cur, p + cur + 1);}}}
}

4.选择排序(双头排序优化版)

选择排序应该也是一种十分常见的排序方式

这里我们就在原有基础上优化升级一下，双头选择排序优化版
从两头分别取数，左边取一个交换为较小，右边取一个交换为较大
给定一个数组：[5,3,2,4,1,2,2,3,4]需要排为升序请添加图片描述
时间复杂度还是O(n^2)但是效率要略高一些。

5.堆排序

堆排序我已经在这篇文章中仔细地阐述了：
可以点击以下链接去访问:

数据结构(初阶5)—堆与堆排序(详解)

6.快速排序

运用最最广泛的一种排序方式，以其独特的解决思想而闻名。
他的变种和相关推论有许多，这边着重将双指针法，前后指针法
优化方式为三数取中法

快速排序的本质就是分治的思想，递归的思想
给定一个数组：[5,3,2,4,1,2,2,3,4]需要排为升序
请添加图片描述

1). 双指针法

请添加图片描述
为什么我们必须让p1先走呢，因为p1先走，最后相遇的时候，

相遇的值一定大于key，可以直接将key与相遇值交换
我们也许会想到，如果key的左边全部都大于key，这种极端的情况下，我们的快排就会变得十分的不稳定
所以我们有一个三数取中的优化方法
先将key与中间值与排头比较，最后将第二大的值与key的位置交换

void swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}
int mid_inthree(int* arr, int begin, int end)
{if (arr[begin] > arr[end] && arr[begin] < arr[(begin + end) / 2])return begin;else if (arr[end] > arr[begin] && arr[end] < arr[(begin + end) / 2])return end;elsereturn (end + begin) / 2;
}
void my_qsort(int* arr, int begin, int end)//双指针快排
{if (end <= begin){return;}swap(arr+end, arr+mid_inthree(arr, begin, end));int left = begin, right = end - 1;while (left <= right){while (arr[left] <= arr[end]&&left<=right){left++;}while (arr[right] >= arr[end]&&right>=left){right--;}if (left < right){swap(arr + left, arr + right);}}swap(arr + end, arr + left);my_qsort(arr, begin, left - 1);my_qsort(arr, left + 1, end);
}

2).前后指针法

请添加图片描述

void swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}
int mid_inthree(int* arr, int begin, int end)
{if (arr[begin] > arr[end] && arr[begin] < arr[(begin + end) / 2])return begin;else if (arr[end] > arr[begin] && arr[end] < arr[(begin + end) / 2])return end;elsereturn (end + begin) / 2;
}
void my_qsort2(int* arr, int begin, int end)
{if (end <= begin){return;}swap(arr + end, arr + mid_inthree(arr, begin, end));int cur = begin, prev = begin-1;while (cur<end){while (cur < end && arr[cur] >= arr[end]){cur++;}prev++;swap(arr + cur, arr + prev);}swap(arr + prev+1, arr + end);my_qsort(arr, begin, prev - 1);my_qsort(arr, prev + 1, end);
}

3).非递归法

递归的短板不言而喻，稍微大一点的数组就会导致栈溢出
所以我们这里可以在堆上面建立一个模拟栈，总所周知栈上空间只有M量级，堆上空间却有G量级

大致思路与上面类似，只是多了一个模拟栈，所以选择上面任意一种排序法就行，这里选择双指针快排作为核心
我们的模拟栈的作用是什么：用来存放和调用下标
比如说给定一个数组：[5,3,2,4,1,2,2,3,4]需要排为升序
哪么我的模拟栈中存入 (0,8)这两个区间的脚标
每进行一次快排，去掉内部的两个脚标，再放入四个脚标；
如果区间只有一个数字，就不放入模拟栈
最后栈变为空。
所以代码实现如下：

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
// 定义栈节点
typedef int STDataType;typedef struct Stack {STDataType _data;struct Stack* _next;
} Stack;// 初始化栈
Stack* StackIni() {return NULL; // 空栈直接用 NULL 表示
}// 销毁栈
void Stackdestory(Stack* pst) {while (pst) {Stack* tmp = pst;pst = pst->_next;free(tmp);}
}// 入栈
void StackPush(Stack** ppst, STDataType x) {Stack* newNode = (Stack*)malloc(sizeof(Stack));newNode->_data = x;newNode->_next = *ppst; // 新节点指向当前栈顶*ppst = newNode;        // 更新栈顶为新节点
}// 出栈
void StackPop(Stack** ppst) {assert(*ppst); // 确保栈非空Stack* tmp = *ppst;*ppst = (*ppst)->_next;free(tmp);
}// 判断栈是否为空
int Stackempty(Stack* pst) {return pst == NULL; // 空栈返回 1，非空返回 0
}// 获取栈顶元素
STDataType Stacktop(Stack* pst) {assert(!Stackempty(pst)); // 确保栈非空return pst->_data;
}

前面是栈的源码操作，和建立
下面实现非递归快排

void swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}
int partsort(int* arr, int begin, int end)//双指针核心
{swap(arr + end, arr + mid_inthree(arr, begin, end));int left = begin, right = end - 1;while (left <= right){while (left <= right&&arr[left] <= arr[end]){left++;}while (right >= left &&arr[right] >= arr[end] ){right--;}if (left < right){swap(arr + left, arr + right);}}swap(arr + end, arr + left);return left;
}
void my_qsort3(int* arr, int begin, int end)//非递归快排
{Stack* tmp=StackIni();StackPush(&tmp, end);StackPush(&tmp, begin);while (!Stackempty(tmp)){int begin = Stacktop(tmp);StackPop(&tmp);int end = Stacktop(tmp);StackPop(&tmp);int div = partsort(arr, begin, end);if (div + 1 < end){StackPush(&tmp, end);StackPush(&tmp, div+1);}if (div - 1 > begin){StackPush(&tmp, div - 1);StackPush(&tmp, begin);}}Stackdestory(tmp);
}

这种操作可以有效规避栈溢出，但是不会提高性能。
用了三数取中的方法，我们的快排可以近似为O(nlogn)

在这里插入图片描述

7.归并排序

归并排序也是一个十分重要的排序，在许多场景下都有运用，其主要思想是分治

给定一个数组：[5,3,2,4,1,2,2,3]需要排为升序
主要思想如下：
递归到底，再向上归并
请添加图片描述

1).递归版本(递归的回退就是归并)

代码实现如下，在经历了二叉树便利的学习后，归并排序的代码其实并不难理解

void _MergeSort(int* a, int left, int right, int* tmp)//递归回退就是归并
{if (left >=right){return;}int mid = (left+right) / 2;_MergeSort(a, left, mid,tmp);_MergeSort(a, mid + 1, left, tmp);int begin_1 = left, end_1 = mid;int begin_2 = mid + 1, end_2 = right;int begin_tmp = begin_1;while (begin_1 <= end_1 && begin_2 <= end_2){if (a[begin_1] >= a[begin_2]){tmp[begin_tmp++] = a[begin_2++];}else {tmp[begin_tmp++] = a[begin_1++];}}while (begin_1 <= end_1)//因为是不等长的，所以我们需要考虑不等长的情况{tmp[begin_tmp++] = a[begin_1++];}while (begin_2 <= end_2){tmp[begin_tmp++] = a[begin_2++];}while (left <= end_2)//复制过去{a[left] = tmp[left];left++;}
}
void MergeSort(int* arr, int n)
{assert(arr);int* tmp = (int*)malloc(sizeof(int) * n);_MergeSort(arr,0,n-1,tmp);
}

2).非递归版本(迭代版本)

这个版本有点抽象,这种递归改非递归的题都很让人摸不着头脑qwq

创建数组int arr[ ] = {1,3,5,7,9,2,4,6,8,0};
我们创造一个gap，gap从1开始，为 2^(n-1)+1,这样代表1，3，7，15…刚好表示
请添加图片描述
代码实现：(切记要控制边界，且要处理特殊情况！！！)

void MergeSortpart(int* a, int left,int mid,int right, int* tmp)
{int begin_1 = left, end_1 = mid;int begin_2 = mid + 1, end_2 = right;int begin_tmp = begin_1;while (begin_1 <= end_1 && begin_2 <= end_2){if (a[begin_1] >= a[begin_2]){tmp[begin_tmp++] = a[begin_2++];}else{tmp[begin_tmp++] = a[begin_1++];}}while (begin_1 <= end_1)//因为是不等长的，所以我们需要考虑不等长的情况{tmp[begin_tmp++] = a[begin_1++];}while (begin_2 <= end_2){tmp[begin_tmp++] = a[begin_2++];}while (left <= right)//复制过去{a[left] = tmp[left];left++;//printf("%d ", a[left]);}
}
void MergeSort(int* arr, int n)
{assert(arr);int* tmp = (int*)malloc(sizeof(int) * n);//_MergeSort(arr,0,n,tmp);int gap = 1;for (gap = 1; gap <= n-1; gap=gap*2+1){for (int x = 0; x+gap<=n; x += gap+1){int begin_1 = x, end_1 = x + gap;int mid = (begin_1 + end_1) / 2;MergeSortpart(arr, begin_1,mid,end_1,tmp);}for (int i = 0; i < n + 1; i++){printf(" %d", arr[i]);}printf("\n");}if (gap/2 != n-1)//处理后面多出来的一小块{MergeSortpart(arr, 0, gap/2, n,tmp);}//_MergeSort(arr,0,n-1,tmp);
}

(*´∀`)~♥

创作不易，恳请留一个赞吧qwq，有留言必回 (*´∀`)~♥
在这里插入图片描述

排序