常见的排序算法

Posted on Wed, 25 Dec 2024 10:13:01 +0800 by LiangMingJian

冒泡排序 #

选择第 1 个和第 2 个数字，如果第 1 个大于第 2 个，则二者交换位置（假设是升序排列）。之后选择第 2个和第 3 个数字，类似交换处理。一轮下来后，最大的数字会冒泡到最后一位。接下来，忽略已经排好的数字，对于剩下的数字再来一轮，直到所有的数字都排列完成。

• 若文件的初始状态是正序的，一趟扫描即可完成排序。所需的关键字比较次数 C 和记录移动次数 M 均达到最小值：Cmin = n-1，Mmin = 0，所以，冒泡排序最优的时间复杂度为 O(n)。
• 若初始文件是反序的，需要进行 n-1 趟排序。每趟排序要进行 n-1 次关键字的比较 ( 1 ≤ i ≤ n-1 )，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：Cmax=n(n-1)/2，Mmax=3n(n-1)/2，冒泡排序的最坏时间复杂度为 O(n^2)。
• 最优的空间复杂度，不需要借用第三方内存空间，则复杂度为 0，最差的空间复杂度，每次都要借用一次内存，按照实际的循环次数，为 O(n)。
• 平均的空间负杂度为 O(1)，平均的时间复杂度 O(n^2)。

插入排序 #

从第一个元素开始，该元素可以认为已经被排序。然后取出下一个元素，在已经排序的元素序列中从后向前扫描，并把取出的元素放到已排序的元素中间的合适位置。重复上述步骤，就像排队一样，依次每次挑一个同学，把该同学插入到已经排好的部分队伍里。

• 当待排序数组是有序时，只需当前数跟前一个数比较一下就可以了，这时一共需要比较 N-1 次，因此最优的时间复杂度为 O(n)。
• 当待排序数组是逆序的，此时需要比较次数最多，总次数记为：1+2+3+…+N-1，所以，插入排序最坏情况下的时间复杂度为 O(n^2)。
• 平均来说，A[1 ... j-1] 中的一半元素小于A[j]，一半元素大于A[j]。插入排序在平均情况运行时间与最坏情况运行时间一样是 O(n^2)。
• 插入排序的空间复杂度为常数阶 O(1)。

快速排序 #

从数列中挑出一个元素，称为基准。然后重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。接着递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。当递归到最底部时，数列的大小是零或一，此时数列已经排序完毕。

• 快速排序的一次划分是从两头开始交替搜索，直到 low 和 hight 重合的，因此一次排序时间复杂度是 O(n)，即快速排序的时间复杂度与划分的趟数有关。
• 理想的情况是，每次划分所选择的中间数恰好将当前序列几乎等分，经过 log2n 趟划分，便可得到长度为 1 的子表。这样，整个算法的时间复杂度为 O(nlog2n)。
• 最坏的情况是，每次所选的中间数是当前序列中的最大或最小元素，这使得每次划分所得的子表中一个为空表，另一子表的长度为原表的长度 -1。这样，长度为n的数据表的快速排序需要经过 n 趟划分，使得整个排序算法的时间复杂度为 O(n^2)。
• 为改善最坏情况下的时间性能，可采用其他方法选取中间数。通常采用三者值取中方法，即比较 H->r[low].key、H->r[high].key 以及 H->r[(low+high)/2].key，取三者中为中值的元素为中间数。
• 从空间性能上看，尽管快速排序只需要一个元素的辅助空间，但快速排序需要一个栈空间来实现递归。最好的情况下，即快速排序的每一趟排序都将元素序列均匀地分割成长度相近的两个子表，所需栈的最大深度为 log2(n+1)；但最坏的情况下，栈的最大深度为n。这样，快速排序的空间复杂度为 O(log2n)。