排序算法

排序是将数组元素按升序或降序排列的过程。例如，考虑一个数组 A = {A1, A2, A3, A4, ... An}，如果 A 的元素按 A1 > A2 > A3 > A4 > A5 > ... > An 的顺序排列，则称该数组按升序排列。

考虑一个数组；

int A[10] = { 5, 4, 10, 2, 30, 45, 34, 14, 18, 9 }

按升序排列的数组将给出如下；

A[] = { 2, 4, 5, 9, 10, 14, 18, 30, 34, 45 }

有很多技术可以执行排序。在本教程的这一部分，我们将详细讨论每种方法。

排序算法的类型

各种类型的排序算法有：

• 基于比较的算法：这类排序算法仅根据最佳情况进行决策。基于比较的算法的最佳情况是 O(nlogn)，最坏情况是 O(n²)。
• 基于交换的算法：此算法通过交换次数（也称为干预次数）进行分类。
• 基于稳定性的算法：如果排序算法遵循具有相似键的元素的相对顺序，从而使原始顺序在输出中保持不变，则它是稳定的。例如：索引 i 和 j，使得 A[i] 等于键 A[j]，如果记录 R[i] 在原始文件中位于记录 R[j] 之前，则记录 R[i] 在排序列表中位于记录 R[j] 之前。
• 基于不稳定性的算法：此类算法不遵循顺序。
• 基于适应性的算法：某些排序算法的复杂性根据前置条件 [快速排序] 而变化。这类算法称为自适应算法。
• 内部排序算法：在排序过程中完全使用主内存的算法称为内部排序算法。内部排序要求数据集合完全适合计算机的主内存。
• 外部排序算法：当数据集合不能一次性完全容纳在计算机的主内存中，而必须驻留在磁带、磁盘等辅助存储设备中时，我们可以使用外部排序。

排序算法

下表描述了排序算法及其说明。