数据结构：七大经典、比较类的排序算法思路

您所在的位置：网站首页 › 数据结构排序有哪些类型 › 数据结构：七大经典、比较类的排序算法思路

数据结构：七大经典、比较类的排序算法思路

2024-07-16 03:18| 来源: 网络整理| 查看: 265

排序算法根据数据是否存在内存中进行排序，划分为内部排序和外部排序。而常见的内部排序算法有十种，又可根据是否需要进行元素的比较，划分为比较类排序和非比较类排序。在这里插入图片描述

文章目录插入排序简单插入排序希尔排序选择排序简单选择排序堆排序交换排序冒泡排序快速排序Hoare版本挖坑版本前后指针版本归并排序

插入排序简单插入排序

玩扑克牌时最常用的就是简单插入排序在这里插入图片描述摸一张牌插入已经有序的队列中，将这张牌依次与队列中的牌比较，左边比它小右边比它大则插入该位置。

插入排序：插入排序基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序。插入排序的基本思想是：每次将一个待排序的数据，按其关键码值的大小插入前面已经排序的数据中的适当位置上，直到全部插入完为止。

单趟插入排序（升序）示例：在这里插入图片描述但是大多数情况我们面临的环境，都是给你一段无序的数据要求你进行排序。基于上面单趟排序的思想，可以将数组的第一个数据当作是一个有序的数组，其后面的一个元素当作要插入这个有序的数组的元素，插入之后又是一个有序的数组，按照这个思路依次进行插入，直到最后一个元素插入完成为止。这里可能有一点绕，但是原理是很简单的。

插入排序（升序）动图演示如下：在这里插入图片描述【参考代码】

//直接插入排序（升序为例） void InsertSort(int* arr, int n) { assert(arr); //防止传一个空的数组 int i = 0; for (i = 0; i = 0) { if (arr[end] > x) { arr[end + 1] = arr[end];//将end的数据往后移，以便之后的插入，不用担心数据被覆盖，因为之前已经存放在x里了 --end; } else { break; //找到合适的位置，跳出 } } arr[end + 1] = x; //插入 } }

复杂度

时间复杂度

最坏时间复杂度：O(n^2)，逆序为最坏情况。最好时间复杂度：O(n) ，接近有序为最好情况。

空间复杂度

O(1), 并没有借助额外的空间。希尔排序

希尔排序又可称为“缩小增量排序”，它优化了简单插入排序。

根据上面对简单插入排序的探讨，当序列接近有序时，时间复杂度可达到O(n).

希尔排序的思想：首先使得整个序列接近有序后，最后在使用简单插入排序。为了使得整个序列接近有序采用了分组预排序的方法，取某个固定距离的数据为一组进行分组。

在这里插入图片描述此时该序列已经相较与之前更接近有序了，再减少距离来分组排序则更接近有序。其实在分组的时候取多少为间距并没有给出明确的规定,一般是先采用序列的一半为距离，后面依次缩小一半的距离进行多次分组预排序，所以希尔排序又可称为“缩小增量排序”。当距离为1时其实就是一次直接插入排序。我们先来实现以gap为距离分一次组的预排序。

//希尔排序,一次分组预排序 void ShellSort_One(int* arr, int n) { assert(arr); int i = 0; int j = 0; int gap = 3; for (j = 0; j x) { arr[end + gap] = arr[end]; end -= gap; } else { break; } } arr[end + gap] = x; } } }

以上面的例子进行测试，答案一致。在这里插入图片描述而多次分组预排序即可达到目的。

//希尔排序,版本一 void ShellSort_One(int* arr, int n) { assert(arr); int i = 0; int j = 0; int gap = n; while (gap > 0) { gap /= 2; //上面已经解释过这里为什么是除以2 for (j = 0; j x) { arr[end + gap] = arr[end]; end -= gap; } else { break; } } arr[end + gap] = x; } } } }

【优化】上面的思路，我们采用的一次分组预排序是：每组各自进行排序，一组排好序之后再排下一组”。其实我们还可以采用：每组交替进行一次插入排序，直到达到目的，可以理解为“一锅炖”。

//希尔排序，版本二 void ShellSort_Two(int* arr, int n) { int i = 0; int gap = n; while (gap > 1) { gap /= 2; for (i = 0; i = 0) { if (arr[end] > x) { arr[end + gap] = arr[end]; end -= gap; } else { break; } } arr[end + gap] = x; } } } 选择排序简单选择排序

【简述】

选择排序的思想：先以第一个数为参照数，在后面剩下的序列中选出比它小并且是剩下的序列中最小的数，将这个数与参照数的位置交换。此时属于第一个位置的数已经排好，剩下的数依次按照这个方法进行直到达到排序的目标。

【动图如下】在这里插入图片描述那么我们来实现一下。

//简单选择排序 //版本一 void SelectSort(int* arr, int n) { assert(arr); int begin = 0; while (begin

【本文地址】

数据结构：七大经典、比较类的排序算法思路

数据结构：七大经典、比较类的排序算法思路

今日新闻

推荐新闻