移动网站建设查询,教做宝宝辅食的网站,大连网站推广公司,网站开发域名注册1.排序的概念及运用
1.1概念
排序#xff1a;所谓排序#xff0c;就是使⼀串记录#xff0c;按照其中的某个或某些关键字的大小#xff0c;递增或递减的排列起来的操作#xff0c;以便更容易查找、组织或分析数据。
1.2运用 购物筛选排序 院校排名 1.3常见排序算法 2.实…1.排序的概念及运用
1.1概念
排序所谓排序就是使⼀串记录按照其中的某个或某些关键字的大小递增或递减的排列起来的操作以便更容易查找、组织或分析数据。
1.2运用 购物筛选排序 院校排名 1.3常见排序算法 2.实现常见排序算法
int a[] {5, 3, 9, 6, 2, 4, 7, 1, 8};
2.1 插入排序 把待排序的记录按其关键码值的大小逐个插入到⼀个已经排好序的有序序列中直到所有的记录插入完为止得到⼀个新的有序序列 。 2.1.1 直接插入排序
直接插入排序Direct Insertion Sort是一种简单直观的排序算法它通过逐步构建有序序列将未排序部分的元素插入到已排序部分的适当位置直到整个数组排序完成。
基本思想
1.将数组分为 已排序部分 和 未排序部分。 初始时已排序部分只有第一个元素。 未排序部分为剩余的元素。
2.依次从未排序部分取出一个元素插入到已排序部分的正确位置。
3.重复以上操作直到未排序部分为空。
算法步骤
1.从数组的第二个元素索引为 1开始依次向后遍历。 对当前元素在已排序部分从后向前查找其插入位置 如果已排序部分的元素大于当前元素则将其向后移动。
2.找到插入位置后将当前元素放入。
3.重复此过程直到所有元素排序完成。 当插入第 i(i1) 个元素时前⾯的 array[0],array[1],…,array[i-1] 已经排好序此时用 array[i] 的排序码与 array[i-1],array[i-2],… 的排序码顺序进行比较找到插入位置即将 array[i] 插入原来位置上的元素顺序后移 代码实现
void InsertSort(int* a, int n) {for (int i 1; i n; i) {// 当前要插入的元素int tmp a[i];// 已排序部分的最后一个元素的索引int j i - 1;// 从后向前查找插入位置while (j 0 a[j] tmp) {a[j 1] a[j]; // 后移元素j--;}// 将当前元素插入到正确的位置a[j 1] tmp;}
}特性总结
算法复杂度
时间复杂度 最坏情况数组逆序O(n^2)最好情况数组已排序O(n)平均情况O(n^2)空间复杂度原地排序不需要额外的辅助空间空间复杂度为 O(1)。稳定性直接插入排序是稳定的因为在插入过程中不会改变相等元素的相对顺序。 优缺点
优点
简单直观实现容易适合小规模数据。性能良好当数组接近有序时插入排序的效率很高接近 O(n)。
缺点
效率低下对大规模、随机分布的数组排序效率较低时间复杂度较高。大量数据移动当数组逆序时几乎每次插入都需要移动大量元素。 适用场景
数据量较小如 n 100时插入排序是一种简单有效的选择。数据本身接近有序时如几乎按升序排列插入排序效率很高。
2.1.2 希尔排序
希尔排序又称缩小增量法是一种基于插入排序的改进算法得名于其发明者 Donald Shell。它通过分组和逐步缩小分组间距增量使得数据能够更快地接近有序从而提高排序效率。
基本思想 先选定⼀个整数通常是gap n/3 1把待排序文件所有记录分成各组所有的距离相等的记录分在同⼀组内并对每⼀组内的记录进⾏排序然后gap gap/3 1得到下⼀个整数再将数组分成各组进入插入排序当gap 1时就相当于直接插入排序。 它是在直接插入排序算法的基础上进行改进而来的综合来说它的效率肯定是要高于直接插入排序算法的。 算法步骤
初始化 gap n / 3 1其中 n 是数组的长度。按照当前的 gap 将数组分组对每组进行插入排序。缩小 gap继续分组排序直到 gap 1。当 gap 1 时进行最后一次插入排序数组有序。 代码实现
void ShellSort(int* a, int n) {int gap n;// 缩小增量直到 gap 1while (gap 1) {gap gap / 3 1;// 分组for (int group 0; group gap; group) { // 控制每组// 每组独立进行插入排序for (int i group gap; i n; i gap) {int tmp a[i];int j i - gap;while (j group a[j] tmp) {a[j gap] a[j];j - gap;}a[j gap] tmp;}}}
}显式地将数组分组每组独立排序后再继续调整增量 gap这种更好理解分组排序的原理但代码稍显冗长所以我一般用这种
void ShellSort1(int* a, int n) {int gap n;// 缩小增量直到 gap 1while (gap 1) {gap gap / 3 1;// 从 gap 开始模拟插入排序for (int i gap; i n; i) {int tmp a[i]; // 当前待插入的元素int j i - gap;// 插入排序逻辑按 gap 步长比较和移动while (j 0 a[j] tmp) { // 在同组中向前查找a[j gap] a[j]; // 将较大的元素后移j - gap; // 按 gap 步长继续比较}a[j gap] tmp; // 插入到合适位置}}
}这种方法也叫“简单希尔排序”Simple Shell Sort或者直接叫并着走它直接在外层控制增量 gap然后在整个数组中按步长进行插入排序逻辑比较直观效率高。这种实现方法更贴近希尔排序的本质适合直接应用于实际场景。
它的核心思想是 希尔排序的分组本质上是用 步长 gap 控制哪些元素属于一个组。 在并着走的实现中假设 gap 3 对于索引为 0, 3, 6, 9... 的元素它们属于第一组。对于索引为 1, 4, 7, 10... 的元素它们属于第二组。对于索引为 2, 5, 8, 11... 的元素它们属于第三组。并着走的逻辑是遍历整个数组隐式地让这些组在同一个循环中排序。 在 gap 的控制下 每个位置 i 的元素 a[i]都会和同组的前一个元素位置 i - gap进行比较。如果需要交换位置就不断向前检查直到找到合适位置。 特性总结
算法复杂度
1.时间复杂度 最坏情况O(n^2)不理想的增量序列。 平均情况O(n^(3/2)) 或更优根据增量序列。 最好情况接近 O(n)。
可以分成内外层来分析
外层循环控制增量 gap应该能直接看出来吧无疑问的O(log(n))就是增量序列的长度。
内层循环分组插入排序 假设⼀共有n个数据合计gap组则每组为n / gap个在每组中插入移动的次数最坏的情况下为 1 2 3 .... ( n / gap− 1))⼀共是gap组因此 1 2 3 .... ( n / gap− 1)) 总计最坏情况下移动总数为 gap ∗ 1 2 3 .... (n / gap − 1 ) gap取值有以除3为例n / 3 n / 9 n / 27 ...... 2 1 当gap为n / 3时移动总数为 n / 3 * (1 2) n 当gap为n / 9时移动总数为 n / 9 * (1 2 3 .... 8) (n / 9) * 8 (1 8) / 2 4n最后⼀趟gap1即直接插入排序内层循环排序消耗为n
可知比较次数是先增加再下降的或者画一张曲线图更好理解 因此希尔排序在最初和最后的排序的次数都为n即前⼀阶段排序次数是逐渐上升的状态当到达某⼀顶点时排序次数逐渐下降至n而该顶点的计算暂时无法给出具体的计算过程 所以目前其实没有明确的希尔排序的时间复杂度普遍认为的话是在 O(n^1.3) 这里我们引用充当教科书较多的 《数据结构(C语言版)》--- 严蔚敏书中给出的时间复杂度的解释 2.空间复杂度使用原地排序额外空间复杂度为 O(1)。
3.稳定性不稳定因为在分组时可能会打乱相同元素的相对顺序。 优缺点
优点
简单易实现。对中等规模的数组如 1 万以下性能较好。在基本有序的数组上效率较高。
缺点
不稳定不能保证相同元素的顺序。对非常大的数组效率不如快速排序。 增量序列的选择
希尔增量gap gap / 3 1。Hibbard增量gap 2^k - 1。Sedgewick增量gap 9 * 4^i - 9 * 2^i 1 等。增量序列的选择会显著影响希尔排序的性能。 适用场景
数据规模适中几百到几万。数据分布无规律但需要排序效率较高的场景。对性能要求高但稳定性不重要的场景。
2.2 选择排序 每⼀次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置直到全部待排序的数据元素排完 。 2.2.1 直接选择排序
直接选择排序Selection Sort是一种简单的排序算法其基本思想是每次从待排序的序列中选择最小或最大元素将其放到已排序序列的末尾。该算法属于交换排序类通过多次选择最小或最大元素并与当前序列中的元素交换来逐步完成排序。
基本思想
选择最小元素在每一轮中找到剩余未排序部分的最小元素。交换位置将找到的最小元素与当前已排序部分的末尾元素交换位置。重复每次排好一个元素后缩小待排序部分的范围继续执行选择和交换操作直到所有元素排序完成。
算法步骤
假设数组长度为 n开始时将整个数组看作未排序部分。从第一个元素开始扫描剩余部分找到最小的元素。将最小元素与当前待排序部分的第一个元素交换。重复此过程直到排序完成。 1. 在元素集合 array[i]--array[n-1] 中选择关键码最大(小)的数据元素 2. 若它不是这组元素中的最后一个(第一个)元素则将它与这组元素中的最后一个第一个元素 交换 3. 在剩余的 array[i]--array[n-2]array[i1]--array[n-1] 集合中重复上述步骤直到集合剩余 1 个元素 代码实现
void SelectionSort(int* a, int n) {// 外层循环控制已排序部分的末尾for (int i 0; i n - 1; i) {int minIndex i;// 内层循环在未排序部分中寻找最小值for (int j i 1; j n; j) {if (a[j] a[minIndex]) {minIndex j; // 记录最小元素的索引}}// 交换最小元素与当前已排序部分的下一个元素if (minIndex ! i) {int temp a[i];a[i] a[minIndex];a[minIndex] temp;}}
}特性总结
算法复杂度
1.时间复杂度 最坏情况数组逆序O(n^2) 最好情况数组已排序O(n^2)即数组已经排序选择排序仍需执行完整的循环 平均情况O(n^2)
2.空间复杂度原地排序不需要额外的辅助空间空间复杂度为 O(1)。
3.稳定性不稳定在排序过程中可能会改变相等元素的相对顺序因为会交换位置。 优缺点
优点
简单直观直接选择排序算法的实现简单易于理解适合小规模数据。空间效率高只使用常数级的额外空间内存开销小。
缺点
效率低下由于时间复杂度为 O(n^2)对于大规模数据性能较差。不稳定相同元素的顺序可能被改变导致排序不稳定。交换次数较多每次找到最小元素后都会交换可能导致不必要的交换操作。 适用场景
数据量较小如 n 100时选择排序是一种简单有效的排序方法适合小规模数据的排序。数据本身接近有序时直接选择排序的性能相对较好尽管时间复杂度为 O(n^2)但相较于其他 O(n^2) 算法选择排序的交换次数较少。
2.2.2 堆排序 堆排序(Heap Sort)是一种基于堆数据结构的排序算法堆是一种完全二叉树满足堆的性质 最大堆Max Heap父节点的值大于或等于其子节点的值根节点是最大元素。最小堆Min Heap父节点的值小于或等于其子节点的值根节点是最小元素。 堆排序利用堆的性质每次从堆中提取根节点最大或最小然后调整堆结构从而实现排序。 基本思想
构建堆将待排序数组转换成一个堆结构可以是最大堆或最小堆通常构建最大堆。交换根节点与最后一个节点将堆顶最大元素与堆的最后一个元素交换这样最大元素就被放置到了正确的位置。调整堆交换后堆的结构可能被破坏需要重新调整堆使其恢复堆的性质。重复将剩下的部分继续调整为堆再次进行交换直到所有元素都排序完成。
算法步骤
建堆将给定的数组转换成一个最大堆。交换根节点和最后一个节点把堆顶元素最大值交换到数组的末尾。调整堆将剩余部分重新调整为最大堆。重复交换和调整过程直到堆的大小减小为1。
代码实现
#include stdio.h// 调整堆结构
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]) {int temp a[parent];a[parent] a[child];a[child] temp;parent child;child parent * 2 1; // 继续向下调整} else {break; // 如果父节点大于等于最大子节点则结束}}
}// 堆排序主函数
void HeapSort(int* a, int n) {// 建堆从最后一个非叶子节点开始调整堆for (int i (n - 1) / 2; i 0; --i) {AdjustDown(a, n, i);}// 交换根节点最大元素和最后一个元素然后调整堆int end n - 1;while (end 0) {// 交换根节点与堆的最后一个元素int temp a[0];a[0] a[end];a[end] temp;// 重新调整堆AdjustDown(a, end, 0);--end;}
}// 打印数组
void PrintArray(int* a, int n) {for (int i 0; i n; i) {printf(%d , a[i]);}printf(\n);
}int main() {int arr[] {4, 10, 3, 5, 1};int n sizeof(arr) / sizeof(arr[0]);HeapSort(arr, n);PrintArray(arr, n);return 0;
}堆排序的步骤演示
假设我们有一个数组 [4, 10, 3, 5, 1]我们来逐步演示堆排序的过程。
1.建堆首先将数组转换为最大堆 AdjustDown 会从最后一个非叶子节点开始调整堆结构。 经过调整最大堆应该是 [10, 5, 3, 4, 1]。
2.交换根节点和最后一个元素交换根节点 10 和数组末尾的元素 1得到 [1, 5, 3, 4, 10]。 通过 AdjustDown 调整堆使其重新恢复堆的性质得到 [5, 4, 3, 1, 10]。
3.再次交换根节点和最后一个元素交换根节点 5 和倒数第二个元素 1得到 [1, 4, 3, 5, 10]。 通过 AdjustDown 调整堆得到 [4, 1, 3, 5, 10]。
4.重复继续交换并调整堆直到整个数组排好序 交换后得到 [3, 1, 4, 5, 10]。 调整后得到 [3, 1, 4, 5, 10]。 最终得到排序结果 [1, 3, 4, 5, 10]。
特性总结
算法复杂度
1.时间复杂度 最坏情况数组逆序O(n log n) 最好情况数组已排序O(n log n) 平均情况O(n log n)
2.空间复杂度原地排序堆排序不需要额外的辅助空间空间复杂度为 O(1)。
3.稳定性不稳定堆排序在排序过程中可能改变相等元素的相对顺序因此是一个不稳定的排序算法。 优缺点
优点
时间复杂度稳定无论在最坏、最好还是平均情况下堆排序的时间复杂度始终为 O(n log n)表现稳定。原地排序堆排序只使用常数级额外空间空间复杂度为 O(1)内存开销小。适用于大规模数据由于堆排序的时间复杂度较为稳定因此适合用于处理大规模数据的排序任务。
缺点
不稳定堆排序不保持相等元素的相对顺序因此不适用于需要稳定排序的场景。常数因子较大虽然时间复杂度为 O(n log n)但堆排序的常数因子较大通常会比其他如快速排序的实际性能稍差。 适用场景
大规模数据的排序堆排序在处理大数据时较为稳定尤其是在对时间复杂度有较高要求时。内存有限的情况堆排序是原地排序不需要额外的内存适用于内存受限的情况。需要稳定时间复杂度的场景当不关心排序的稳定性时堆排序是一个不错的选择尤其是在无法预测输入数据分布的情况下。
下一章应该是介绍冒泡和快速排序
那几种快速排序够写很多了
