数据结构 常见的排序算法
🌻个人主页：路飞雪吖~
🌠专栏：数据结构
目录
🌻个人主页：路飞雪吖~
一、插入排序
🌟直接插入排序
🌟希尔排序
二、选择排序
🌟选择排序
🌟堆排序
三、交换排序
🌟冒泡排序
🌟快速排序
⭐递归
✨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;
}