排序算法

概览与术语 在计算机科学与数学中，一个排序算法（Sorting algorithm）是一种能将一串资料依照特定排序方式进行排列的一种算法，最常用到的排序方式之一就是数值顺序。 排序算法依照稳定性可分为稳定算法和不稳定算法。稳定排序算法会让原本有相等键值的纪录维持相对次序。也就是如果一个排序算法是稳定的，当有两个相等键值的纪录 R 和 S，且在原本的列表中 R 出现在 S 之前，则在排序过的列表中 R 也将会是在 S 之前。 排序算法依照排序过程中占用空间的方式分为 In-place 算法 与 Out-place 算法。In-place 是原地算法，基本上不需要额外的辅助空间，可允许固定数量的辅助变量。非原地算法就是 Out-place，其开辟的辅助空间与问题规模相关。例如，冒泡排序只需要数据在原序列中交换位置，不需要额外的辅助空间，是 In-place 算法。 不同的排序算法会有不同的时间复杂度（最差、平均、和最好性能），下表列出了十种经典排序算法的概览： 冒泡排序（Bubble Sort） 一种简单的排序算法。该算法重复地走访过要排序的数列，每次比较相邻的两个元素，如果它们的顺序错误就进行交换，直到序列有序。这个算法的名字由来是因为：越小/越大的元素会经由交换慢慢“浮”到数列的顶端。 冒泡排序对 n 个项目最多需要 O(n2) 的比较次数，且可以原地排序。尽管这个算法是最易了解和实现的排序算法之一，它对于大量数据的排序效率还是比较低。 算法描述 比较相邻的元素。如果第一个比第二个大，就交换他们两个； 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数； 针对所有的元素重复以上的步骤，除了最后一个； 重复步骤 1~3，直到没有任何一对数字需要比较； 可选的优化步骤：某次步骤 1~3 执行过程中没有元素发生交换，则证明该序列已经有序，不需要再进行下一次序列遍历。 动图演示 代码实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 // TypeScript实现 export function bubbleSort(arr: number[]) { const len = arr....