【常见的六大排序算法】插入排序、希尔排序、选择排序、冒泡排序、堆排序、快速排序

2024-06-01 19:44
文章标签 算法 常见 选择 快速 排序 希尔 堆排序 冒泡排序 插入排序 六大

本文主要是介绍【常见的六大排序算法】插入排序、希尔排序、选择排序、冒泡排序、堆排序、快速排序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述

个人主页
创作不易，感谢大家的关注！

在这里插入图片描述
在这里插入图片描述

文章目录

    • 前言
  • 🎡一、插入排序
  • 🌲二、希尔排序
  • 🎉三、选择排序
  • 🎀四、冒泡排序
  • 🚘五、堆排序
  • 🛵六、快速排序
    • 1. Hoare版本
    • 2. 挖坑法
    • 3. 前后指针法
    • 4. 非递归实现

前言

在实现排序前，我们要先知道什么是排序。排序：简单的来说就是把一串数据按照一定的方式依次排序。例如：可以按照数字的大小升序或降序排列，或者按照英文字母的先后顺序排列等。使用这一系列的方式，就可以将一串无序状态下的数据排列成有序的数据。

🎡一、插入排序

  1. 基本思路：

    1. 默认第一个元素为有序的，从第二个元素开始排序。
    2. 取出下一个元素tmp，往前进行比较。
    3. 如果该元素比tmp大，则将该元素往后移动一位，直到找到比tmp小于或者等于的元素。
    4. 找到比tmp小于或者等于的元素，将tmp插入到该元素的下一位。
    5. 不断重复上述步骤。

  2. 动图演示：
    在这里插入图片描述

  3. 时间复杂度： 最坏情况下为 O(N ^ 2)，此时待排序的序列状况为逆序或者接近逆序。最好情况下为 O(N)，此时待排序列为升序，或者说接近升序。

  4. 空间复杂度： O(1)。

代码实现：

// 插入排序
void InsertSort(int* a, int n)
{//遍历数组for (int i = 0; i < n - 1; i++){//记录有序序列最后一个元素的下标int end = i;int tmp = a[end + 1];while (end >= 0){	//比插入的数大就往后移动if (a[end] > tmp){a[end + 1] = a[end];--end;}else{//比插入的数小就退出循环break;}}//将tmp放到比插入的数小的后面a[end + 1] = tmp;}
}

🌲二、希尔排序

  1. 基本思路：

    希尔排序是插入排序的一个优化方案，其本质上还是插入排序。但它们的时间复杂度却并不相同。

    1. 先将待排序列进行预排序，使得待排序列接近有序，然后再进行插入排序。
    2. 将待排序的数据分为多个组，使每组间隔gap为2或3…。
    3. 如果第一个元素大于最后一个元素，则将它们两个元素进行交换。
    4. 不断重复上述操作，直到每组间隔只有1时，说明所有的数据已经完成排序。

  2. 动图演示：在这里插入图片描述

  3. 时间复杂度： O(N ^ 1.3)。

  4. 空间复杂度： O（1）。

代码实现：

// 希尔排序
void ShellSort(int* a, int n)
{int gap = n;while (gap > 1){// +1保证当n的值小于3时，gap最低为1，依次进行插入排序gap = gap / 3 + 1;for (size_t i = 0; i < n - gap; i += gap){int end = i;int tmp = a[end + gap];while (end >= 0){if (a[end] > tmp){a[end + gap] = a[end];end = end - gap;}else{break;}}a[end + gap] = tmp;}}
}

🎉三、选择排序

  1. 基本思路：
    1. 从待排序序列中选出最小值mini，放在序列的起始位置。
    2. 每次遇到比mini小的值就更新mini，直到遍历完整个序列。
    3. 然后将该值放到序列的排列好的有序序列的下一个位置。
    4. 重复上述步骤，直到待排序只剩下一个元素，说明排序完成。
  2. 动图演示：
    在这里插入图片描述
  3. 时间复杂度： O（N^2）。有n个数，每趟选一个最大或最小值，需要选n趟。
  4. 空间复杂度： O（1）。

代码实现

// 选择排序
void SelectSort(int* a, int n)
{//定义一个begin和end分别指向数组的头下标和尾下标int begin = 0;int end = n - 1;while (begin < end){//定义mini和begin分别表示最小值和最大值的下标int mini = begin, maxi = begin;for (int i = begin + 1; i <= end; i++){if (a[i] > a[maxi])maxi = i;if (a[i] < a[mini])mini = i;}Swap(&a[begin], &a[mini]);//需要注意的是，当最大值在最小值位置的时候，a[maxi]的值会与a[mini]的值进行交换，因此需要提前将maxi置为miniif (begin == maxi){maxi = mini;}Swap(&a[end], &a[maxi]);begin++;end--;}
}

总结： 效率相对较低，实际中很少使用。

🎀四、冒泡排序

  1. 基本思路：
    根据序列中两个记录键值的比较结果来交换这两个记录在序列中的位置，一前一后两个下标的值进行比较，如果前一个值比后一个值大就进行交换。
  2. 动图演示：在这里插入图片描述
  3. 时间复杂度： O（N ^2）。该排序每次都要和相邻的两个数进行比较，最坏情况下比较n次，跑n躺。
  4. 空间复杂度： O（1）。

代码实现：

// 冒泡排序
void BubbleSort(int arr[], int n)
{for (int i = 0; i < n - 1; i++){//假设没有发生判断，如果发生判断，就将flag置为，否则就退出int flag = 0;for (int j = 0; j < n - 1 - i; j++){int tmp = 0;tmp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = tmp;flag = 1;}if (flag == 0){break;}}
}

结论： 该排序效率低下，实际中几乎不使用。

🚘五、堆排序

  1. 基本思路：
    将一组无序的数据，按照升序或降序的方式对其进行排序。
    注意： 在堆排序中，升序建大堆，降序建小堆。 因为堆排序的逻辑是将根节点与最后一个节点依次发生交换。不断交换，大堆排序完，堆尾的数据就是最大的值，并且不断向堆顶的数据依次缩小；相反，小堆排序完后，堆尾的数据就是最小的值，并不断向堆顶的数据依次增大。
  2. 图片演示：**在这里插入图片描述
  3. 时间复杂度： O（N * log(N)）堆排序建堆的时间复杂度为O（N），但是选数时都需要将堆顶和堆尾的数据进行交换，而堆的高度是log（N），而建堆的时间复杂的可以忽略不计，因此为O（N * log(N)）。
  4. 空间复杂度： O（1）。

代码实现：

void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}// 向下调整排序
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)
{int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);--end;}
}

总结： 排序效率高，实际中也可以使用。

🛵六、快速排序

一般我们使用快速排序方法的顺序：挖坑法 -> Hoare -> 前后指针法。

1. Hoare版本

  1. 基本思路：
    1. 选出一个key，一般在最左边或在最右边。
    2. 定义一个begin为序列的头和end为序列的尾，begin从左向右开始走，end从右向左进行走。（注意： 如果选择最左边的数据为key，则需让end先走；若选择右边的数据为key，则让begin先走）
    3. 假设最左边为key，end开始先走。在走的过程中，如果end遇到比key小的数据，就停下，然后让begin开始走，直到begin遇到比key大的数据就停下，然后将begin里的值和end里的值进行交换，然后又继续从end开始先走，不断循环往复，直到begin和end相遇，则将相遇点的内容和key进行交换即可。
    4. 此时，key左边的数据都是小于key的，key右边的数据都是大于key的，说明key已在序列中排好序了。
    5. 因此，序列中划分出了三个区间，分别为 [left, key - 1],key,[key + 1, right] 这三个区间，然后不断对[left, key - 1]和[key + 1, right]这两个区间重复上述步骤，直到所有的key都排好序。
  2. 单趟的动图演示如下：
    在这里插入图片描述
    代码实现：
// 快速排序
void QuickSort(int* a, int left,int right)
{//只有一个数或区间不存在if (left >= right){return;}int begin = left, end = right;while (begin < end){//右边找小，begin < end是为了防止越界while (begin < end && a[end] >= a[keyi]){end--;}//左边找大while (begin < end && a[begin] <= a[keyi]){++begin;}//小的换到右边，大的换到左边Swap(&a[begin], &a[end]);}Swap(&a[keyi], &a[begin]);// [left,keyi-1] keyi [keyi+1,right]，使用递归的方法QuickSort(a, left, keyi - 1);QuickSort(a, keyi + 1, right);
}

代码优化：
在实际中，我们发现：快速排序在有序或接近有序数组中完成排序的效率低下。因此我们可以采用每次都取大小中等的值来作为数组中最左边的key，这样可以有效提升代码的运行效率，减少循环的次数。

// 三数取中
int GetMidi(int* a, int left, int right)
{int midi = (left + right) / 2;if (a[left] < a[midi]){if (a[midi] < a[right])return midi;else if (a[left] < a[right])return right;else{return left;}}// a[left] > a[midi]else{if (a[midi] > a[right])return midi;// a[midi] < a[right]else if (a[left] < a[right])return left;elsereturn right;}
}

2. 挖坑法

  1. 基本思路：
    1. 选出最左边的元素存入key中，在此位置中形成一个坑位。
    2. 定义left从左到右开始遍历，定义right从右向左开始遍历。
    3. 当right遍历找到比key小的数据，就放入left当中的位置。
    4. 当left遍历找到比key大的数据，就放入right当中的位置
    5. 如果left和right下标相遇，则把key中的数据放入相交处。
  2. 单趟动图演示：
    在这里插入图片描述
    代码实现：
//挖坑法
int QuickSort1(int* a, int left, int right)
{int midi = GetMidi(a, left, right);Swap(&a[left], &a[midi]);midi = left;int key = a[midi];while (left < right){// 左右开始遍历while (left < right && a[right] >= key){--right;}a[midi] = a[right];midi = right;while (left < right && a[left] <= key){++left;}a[midi] = a[left];midi = left;}a[midi] = key;return midi;
}

3. 前后指针法

  1. 基本思路：
    1. 定义key来存储数组中最左边的数据，perv指向数组开始的位置，cur指向prev的下一个位置。
    2. 当cur下标中的元素小于key时，则让prev开始往后走。如果此时prev下标中的元素不等于cur下标中的元素，则两者进行交换。
    3. 否则cur一直往下走，当cur走完时，将prev下表中的元素和key中的数据进行交换
    4. 不断重复上述操作。
  2. 单趟动图演示：
    在这里插入图片描述
    代码实现：
//前后指针法
int QuickSort2(int* a, int left, int right)
{assert(a);int keyi = GetMidi(a, left, right);Swap(a[keyi], a[left]);keyi = left;int prev = left;int cur = prev + 1;while (cur <= right && a[cur] < a[keyi]){++prev;++cur;}while (cur <= right){while (cur <= right && a[cur] >= a[keyi]){++cur;}if (cur <= right){++prev;Swap(a[prev], a[cur]);}++cur;}Swap(&a[prev], &a[keyi]);return prev;
}

4. 非递归实现

基本思路：
1. 使用栈的形式，模拟递归实现
2. 因为每次都要对序列的左右边界进行传入，根据栈的性质：先进后出，后进先出。因此，我们要先传入左边界，再传入右边界，获取数据时要先取右边界，在获取左边界。
3. 注意：获取数据后要及时删除，避免影响栈头结点的数据。

代码实现：

// 非递归方法
void QuickSort3(int* a, int begin, int end)
{assert(a);Stack ST;StackInit(&ST);StackPush(&ST, begin);StackPush(&ST, end);while (!StackEmpty(&ST)){int right = StackTop(&ST);StackPop(&ST);int left = StackTop(&ST);StackPop(&ST);if (left >= right){continue;}int keyi = QuickSort2(a, left, right);StackPush(&ST, keyi + 1);StackPush(&ST, right);StackPush(&ST, left);StackPush(&ST, keyi - 1);}
}

今天的分享就到这里啦，后续我还会新增一个排序算法-------归并排序，希望这篇文章可以帮助大家解决排序算法中的问题。我们下次再见，拜拜啦！在这里插入图片描述

这篇关于【常见的六大排序算法】插入排序、希尔排序、选择排序、冒泡排序、堆排序、快速排序的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1021945。

相关文章

不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
如何选择适合孤独症兄妹的学校？

如何选择适合孤独症兄妹的学校？

在探索适合孤独症儿童教育的道路上，每一位家长都面临着前所未有的挑战与抉择。当这份责任落在拥有孤独症兄妹的家庭肩上时，选择一所能够同时满足两个孩子特殊需求的学校，更显得尤为关键。本文将探讨如何为这样的家庭做出明智的选择，并介绍星贝育园自闭症儿童寄宿制学校作为一个值得考虑的选项。 理解孤独症儿童的独特性 孤独症，这一复杂的神经发育障碍，影响着儿童的社交互动、沟通能力以及行为模式。对于拥有孤独症兄
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
电脑桌面文件删除了怎么找回来？别急，快速恢复攻略在此

电脑桌面文件删除了怎么找回来？别急，快速恢复攻略在此

在日常使用电脑的过程中，我们经常会遇到这样的情况：一不小心，桌面上的某个重要文件被删除了。这时，大多数人可能会感到惊慌失措，不知所措。 其实，不必过于担心，因为有很多方法可以帮助我们找回被删除的桌面文件。下面，就让我们一起来了解一下这些恢复桌面文件的方法吧。 一、使用撤销操作 如果我们刚刚删除了桌面上的文件，并且还没有进行其他操作，那么可以尝试使用撤销操作来恢复文件。在键盘上同时按下“C
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心： 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数，若返回值为正，qsort 函数判定a>b ；为负，a<b；为0，a==b； int milkcmp(const void *va,c
阅读更多...
C#实战|大乐透选号器[6]：实现实时显示已选择的红蓝球数量

C#实战|大乐透选号器[6]：实现实时显示已选择的红蓝球数量

哈喽，你好啊，我是雷工。 关于大乐透选号器在前面已经记录了5篇笔记，这是第6篇； 接下来实现实时显示当前选中红球数量，蓝球数量； 以下为练习笔记。 01 效果演示 当选择和取消选择红球或蓝球时，在对应的位置显示实时已选择的红球、蓝球的数量； 02 标签名称 分别设置Label标签名称为：lblRedCount、lblBlueCount
阅读更多...
poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大，用原来的O（n^2）会爆。 小白上的O(n^2)解法代码：TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2