宝子,你不点个赞吗?不评个论吗?不收个藏吗?
最后的最后,关注我,关注我,关注我,你会看到更多有趣的博客哦!!!
喵喵喵,你对我真的很重要。文章来源:https://www.toymoban.com/news/detail-718054.html
前言
小喵喵课堂开课来,今天我们学习七个常见的排序,哦哦耶!!!
喵喵今天也要加油哦!
来吧,不乱叫,上导图:
目录
前言
八大经典排序的概述
直接插入排序
希尔排序
选择排序
堆排序
冒泡排序
快速排序(快排)
归并排序
总结
┗|`O′|┛ 嗷~~,怎么能忘了基数排序呢?补上补上:
八大经典排序的概述
八大排序算法是指常见的八种经典排序算法,它们分别是冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序和基数排序。
- 冒泡排序:比较相邻的元素,如果顺序错误就交换它们,重复这个过程直到整个数组有序。
- 选择排序:每次从待排序的数组中选择最小(或最大)的元素放在已排序数组的末尾,直到整个数组有序。
- 插入排序:遍历数组,将当前元素插入已排好序的子数组中的适当位置,直到整个数组有序。
- 希尔排序:通过设置间隔将数组分组,对每个分组进行插入排序,逐渐减小间隔,直到间隔为1时进行最后一次插入排序。
- 归并排序:采用分治的思想,将待排序数组划分为较小的子数组,然后递归地对子数组进行排序,并将排好序的子数组合并成更大的有序数组。
- 快速排序:选取一个基准元素,将数组划分为左右两部分,左边部分都比基准元素小,右边部分都比基准元素大,在递归地对左右两部分进行快速排序。
- 堆排序:将待排序数组构建成一个大顶堆,然后将堆顶元素与最后一个元素交换并重新调整堆,重复这个过程直到整个数组有序。
- 基数排序:根据元素的每个位上的值进行排序,先按低位排序,再按高位排序,直到所有位都排序完成。
直接插入排序
直接插入的排序规则,如图所示:
将end和tmp代入进去思考,一来的3,就算起始点,排好了位置,作为end,然后tmp是44,44>3,tmp>end,所以不交换位置,算排好了,end+1,tmp+1。那么第二次比较,end是44,tmp是38,end>tmp,交换位置,38排在44前面。那么第三次比较,5比44小,比38小,排在38前面。以此类推,循环排好数组。
void InSert(int* a, int n)
{
for (int i = 1; i < n; i++)
{
int end = i - 1;
int tmp = a[i];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + 1] = a[end];
end--;
}
else
{
break;
}
}
a[end + 1] = tmp;
}
}
希尔排序
希尔排序是直接插入排序的升级版,先对数组进行有规律的分组,分成多个组,然后每个小组进行直接插入排序。每个小组排完后,再进行一次直接插入排序,就要轻松地多,能够快速排好,大大提高了排序的效率。
分成绿,蓝,红三组,分别进行直接插入排序。
void InsertSort(int* a, int n)
{
int gap = 3;
for (j=0;j<gap;j++)
{
for (int i = j; i < n-gap; i+=gap)
{
int end = i;
int tmp = a[i+gap];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + gap] = a[end];
end-=gap;
}
else
{
break;
}
}
a[end + gap] = tmp;
}
}
}
void InsertSort(int* a, int n)
{
int gap = n;
int j = 0;
while (gap > 1)
{
gap = gap / 2;
for (j = 0; j < gap; j++)
{
for (int i = j; i < n - gap; i += gap)
{
int end = i;
int tmp = a[i + gap];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = tmp;
}
}
}
}
选择排序
选择排序,很直观就是要选择,我们先选择3作为有序数组,然后从3后面的数组中选出最小的数,并于3进行比较,谁小谁站在前面。2比3小,2与3交换位置。依次往后推,拍成有序数组。
喵,很难评,这是简单版的一个点移动,而我们一般上的是困难版的两个点,喵,不好理解,喵喵,也是搞了好久,才明白滴,喵。那么让我们开始吧!猫猫队,冲冲冲!
两个点的移动(建议结合代码,自己也跟着走一走,感觉不就来了嘛!):
//这是两个点的移动
void SelectSort(int* a, int n)
{
int left = 0, right = n - 1;
while (left < right)
{
int mini = left, maxi = left;
for (int i = left + 1; i <= right; i++)
{
if (a[i] < a[mini])
{
mini = i;
}
if (a[i] > a[maxi])
{
maxi = i;
}
}
Swap(&a[left], &a[mini]);
// 如果left和maxi重叠,交换后修正一下
if (left == maxi)
{
maxi = mini;
}
Swap(&a[right], &a[maxi]);
++left;
--right;
}
}
堆排序
就是以层序的方式从下往上,从大到小的排。升序建大堆,降序建小堆。
// 左右子树都是大堆/小堆
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)
{
// 建堆 -- 向下调整建堆 -- O(N)
for (int i = (n - 1 - 1) / 2; i >= 0; --i)
{
AdjustDown(a, n, i);
}
// 自己先实现 -- O(N*logN)
int end = n - 1;
while (end > 0)
{
Swap(&a[end], &a[0]);
AdjustDown(a, end, 0);
--end;
}
}
冒泡排序
冒泡排序,好理解,教学意义重大。简单的来说就是从一端开始,两两交换,把小的换在前面去就OK了!
void BubbleSort(int* a, int n) { for (int j = 0; j < n; j++) { bool exchange = false; for (int i = 1; i < n - j; i++) { if (a[i - 1] > a[i]) { Swap(&a[i - 1], &a[i]); exchange = true; } } if (exchange == false) { break; } } }
快速排序(快排)
快排有很多种方法,比如hoare法,挖坑法,前后指针法:
1.hoare法:
无言,如图所示
int GetMidNumi(int* a, int left, int right) { int mid = (left + right) / 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[mid] > a[right]) { return mid; } else if (a[left] < a[right]) { return left; } else { return right; } } } int PartSort1(int* a, int left, int right) { // 三数取中 int midi = GetMidNumi(a, left, right); if (midi != left) Swap(&a[midi], &a[left]); int keyi = left; while (left < 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; return keyi; }
挖坑法:
int GetMidNumi(int* a, int left, int right) { int mid = (left + right) / 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[mid] > a[right]) { return mid; } else if (a[left] < a[right]) { return left; } else { return right; } } } int PartSort2(int* a, int left, int right) { // 三数取中 int midi = GetMidNumi(a, left, right); if (midi != left) Swap(&a[midi], &a[left]); // 21:10继续 int key = a[left]; int hole = left; while (left < right) { // 右边找小 while (left < right && a[right] >= key) --right; a[hole] = a[right]; hole = right; // 左边找大 while (left < right && a[left] <= key) ++left; a[hole] = a[left]; hole = left; } a[hole] = key; return hole; }
前后指针法:
int GetMidNumi(int* a, int left, int right) { int mid = (left + right) / 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[mid] > a[right]) { return mid; } else if (a[left] < a[right]) { return left; } else { return right; } } } int PartSort3(int* a, int left, int right) { // 三数取中 int midi = GetMidNumi(a, left, right); if (midi != left) Swap(&a[midi], &a[left]); int keyi = left; int prev = left; int cur = left + 1; while (cur <= right) { if (a[cur] < a[keyi] && ++prev != cur) Swap(&a[cur], &a[prev]); ++cur; } Swap(&a[prev], &a[keyi]); keyi = prev; return keyi; }
归并排序(递归):
int GetMidNumi(int* a, int left, int right) { int mid = (left + right) / 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[mid] > a[right]) { return mid; } else if (a[left] < a[right]) { return left; } else { return right; } } } int PartSort3(int* a, int left, int right) { // 三数取中 int midi = GetMidNumi(a, left, right); if (midi != left) Swap(&a[midi], &a[left]); int keyi = left; int prev = left; int cur = left + 1; while (cur <= right) { if (a[cur] < a[keyi] && ++prev != cur) Swap(&a[cur], &a[prev]); ++cur; } Swap(&a[prev], &a[keyi]); keyi = prev; return keyi; } void QuickSort(int* a, int left, int right) { if (left >= right) return; int keyi = PartSort3(a, left, right); QuickSort(a, left, keyi - 1); QuickSort(a, keyi + 1, right); }
总结
疯了,疯了,怎么才能讲清楚啊,白话文一大堆,还是图来说清楚,没看清楚的啾咪,留言喵喵鸭,你的明白,就是我的成长,酸Q喵。
宝子,你不点个赞吗?不评个论吗?不收个藏吗?
最后的最后,关注我,关注我,关注我,你会看到更多有趣的博客哦!!!
喵喵喵,你对我真的很重要。
文章来源地址https://www.toymoban.com/news/detail-718054.html
到了这里,关于[C语言]排序的大乱炖——喵喵的成长记的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!