数据结构(初阶7)---七大排序法(堆排序，快速排序，归并排序，希尔排序，冒泡排序，选择排序，插入排序)(详解)
排序
- 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;
else
return (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;
else
return (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，有留言必回 (*´∀`)~♥
