解析四种排序算法
解析四种排序算法
冒泡排序
- 原理
依次遍历数组，比较相邻两个元素的大小。若前面数据大于后边数据，则交换。否则不变。
这样一来，每次就都只能确定一个数据的位置。
- 时间复杂度
因为是比较一遍花 O ( n ) O(n) O(n)，需要确定 n n n 个，需要跑 n n n 次，时间复杂度为 O ( n 2 ) O(n^2) O(n2)。
- 稳定性
对于相邻的两个元素，不满足交换条件，所以不会交换，是稳定的排序算法。
插入排序
- 原理
每次将原数组划分为有效部分，划分 n n n 次，每次将剩下的无效部分按照大小插入到有效部分内。
最后的包含 n n n 个元素的有效部分即为排好序的数组。
- 时间复杂度
划分 n n n 次，每次需要处理 n n n 次比较，时间复杂度为 O ( n 2 ) O(n^2) O(n2)。
- 稳定性
这里的稳定性重点在将其余数字插入到有效范围内。很显然，对于每个位置，在插入的时候，会保持原顺序，即不会出现某个元素 x x x 要插入到 x ′ x' x′ ( x = x ′ ) (x=x') (x=x′) 前面的情况。
快速排序
- 原理
选择一个基准数，将所有数据划分为两个区间：小于基准数的和大于基准数的。
然后对每个区间继续重复操作。
- 时间复杂度
选取基准数为 O ( l o g 2 n ) O(log^n_2) O(log2n)，排序时间为 O ( n ) O(n) O(n)，共 O ( n log 2 n ) O(n\log _2^n) O(nlog2n)。
- 稳定性
快速排序主要看的是区间内的排序，并不能保证稳定性。
归并排序
- 原理
与快排类似，每次都将所有数据分为两个区间，在将每个区间分成两个区间……直到区间长度为 2 2 2，这时再将已经排好序的区间合并。
- 时间复杂度
分成区间时间复杂度 O ( log 2 n ) O(\log^n_2) O(log2n)，比较 O ( n ) O(n) O(n)，总时间复杂度为 O ( n log 2 n ) O(n\log^n_2) O(nlog2n)。
- 稳定性
归并排序可以保证在相邻两个元素相等时，处在前面的序列一定会在处理时在后面的序列的前面。
所以归并排序为稳定的排序算法