|
一.稳定性 一个排序算法是稳定的，就是当有两个有相等关键的纪录R和S，且在原本的列表中R出现在S之前，在排序过的列表中R也将会是在S之前。 二.排序算法列表 1.稳定的 冒泡排序（bubble sort） — O(n^2） 插入排序（insertion sort）— O(n^2) 合并排序（merge sort）— O(nlog n); 需要 O(n) 额外空间 2.不稳定的 选择排序（selection sort）— O(n^2) 堆排序（heapsort）— O(nlog n) 快速排序（quicksort）— O(nlog n) 期望时间，O(n^2) 最坏情况； 对于大的、乱数列表一般相信是最快的已知排序三.冒泡排序 1.排序过程 设想被排序的数组R[1..N]垂直竖立，将每个数据元素看作有重量的气泡，根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R，凡扫描到违反本原则的轻气泡，就使其向上"漂浮"，如此反复进行，直至最后任何两个气泡都是轻者在上，重者在下为止。 2.性能 若记录序列的初始状态为"正序"，则冒泡排序过程只需进行一趟排序，在排序过程中只需进行n-1次比较，且不移动记录；反之，若记录序列的初始状态为"逆序"，则需进行n(n-1）/2次比较和记录移动。因此冒泡排序总的时间复杂度为O(n*n)。 尽管冒泡排序的性能不尽如人意，不过它有两个优点：(1)“编程复杂度”很低，很容易写出代码；(2)具有稳定性。 四.插入排序 1.排序过程 (1) 从第一个元素开始，该元素可以认为已经被排序 (2)取出下一个元素，在已经排序的元素序列中从后向前扫描 (3) 如果该元素（已排序）大于新元素，将该元素移到下一位置 (4) 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置 (5) 将新元素插入到下一位置中 (6) 重复步骤2 如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种，称为二分查找排序。 2.性能 如果目标是把n个元素的序列升序排列，那么采用插入排序存在最好情况和最坏情况。最好情况就是，序列已经是升序排列了，在这种情况下，需要进行的比较操作需（n-1）次即可。最坏情况就是，序列是降序排列，那么此时需要进行的比较共有n(n-1)/2次。插入排序的赋值操作是比较操作的次数加上 (n-1）次。平均来说插入排序算法的时间复杂度为O(n^2）。 插入排序的平均时间复杂度为平方级的，效率不高，但是容易实现。因而，插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小，例如，量级小于千，那么插入排序还是一个不错的选择。 五.合并排序 1.排序过程 合并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。 合并排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。 将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。 例： 设有数列{6，202，100，301，38，8，1} 初始状态： [6] [202] [100] [301] [38] [8] [1] 比较次数 i=1 [6 202 ] [ 100 301] [ 8 38] [ 1 ] 3 i=2 [ 6 100 202 301 ] [ 1 8 38 ] 4 i=3 [ 1 6 8 38 100 202 301 ] 4 总计： 11次 2.性能 时间O(nlogn) 空间O(n) 合并排序是典型的以空间换时间的例子。它的思想可以用来排序，以及寻找数组中的逆序对。 六.选择排序 1.排序过程 设数组内存放了n个待排数字，数组下标从1开始，到n结束。 i=1 从数组的第i个元素开始到第n个元素，寻找最小的元素。 将上一步找到的最小元素和第i位元素交换。 如果i=n－1算法结束，否则回到第3步 举例： 564 第一步：从第一位开始找最小的元素，564中4最小，与第一位交换。结果为465 第二步：从第二位开始找最小的元素，465中5最小，与第二位交换。结果为456 第三步：i=2，n=3，此时i=n-1，算法结束 完成 2.性能 选择排序的平均时间复杂度也是 O(n^2)，且是不稳定的。 七.快速排序 1.简述 现在开始，我们要接触高效排序算法了。实践证明，快速排序是所有排序算法中最高效的一种。它采用了分治的思想：先保证列表的前半部分都小于后半部分，然后分别对前半部分和后半部分排序，这样整个列表就有序了。这是一种先进的思想，也是它高效的原因。因为在排序算法中，算法的高效与否与列表中数字间的比较次数有直接的关系，而"保证列表的前半部分都小于后半部分"就使得前半部分的任何一个数从此以后都不再跟后半部分的数进行比较了，大大减少了数字间不必要的比较。但查找数据得另当别论了。 2.排序过程 设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。 一趟快速排序的算法是： 1）设置两个变量I、J，排序开始的时候：I=0，J=N-1； 2）以第一个数组元素作为关键数据，赋值给key，即 key=A[0]； 3）从J开始向前搜索，即由后开始向前搜索（J=J-1即J--），找到第一个小于key的值A[j]，A[j]与A[i]交换； 4）从I开始向后搜索，即由前开始向后搜索（I=I+1即I++），找到第一个大于key的A[i]，A[i]与A[j]交换； 5）重复第3、4、5步，直到 I=J。 例： 待排序的数组A的值分别是：（初始关键数据：key=49） 注意关键key永远不变，永远是和key进行比较，无论在什么位置，最后的目的就是把key放在中间，小的放前面大的放后面。 A[0]A[1]A[2]A[3]A[4]A[5]A[6]49386597761327 进行第一次交换后：27 38 65 97 76 13 49 ( 按照算法的第三步从后面开始找，此时:J=6） 进行第二次交换后：27 38 49 97 76 13 65 ( 按照算法的第四步从前面开始找>key的值，65>49,两者交换，此时：I=2 ) 进行第三次交换后：27 38 13 97 76 49 65 ( 按照算法的第五步将又一次执行算法的第三步从后开始找 进行第四次交换后：27 38 13 49 76 97 65 ( 按照算法的第四步从前面开始找大于key的值，97>49，两者交换，此时：I=3,J=5 ) 此时再执行第三步的时候就发现I=J=3，从而结束一趟快速排序，那么经过一趟快速排序之后的结果是：27 38 13 49 76 97 65，即所有大于key49的数全部在49的后面，所有小于key（49）的数全部在key（49）的前面。 3.性能 期望时间： O(nlog n) 最坏情况：O(n^2) 最坏情况 对于大的、乱数列表一般相信是最快的已知排序 4.高效思路 特别的，利用快排思想可以解决的问题： (1)找出数组中超过一半的数字。 普通思路：排序，之后统计各个元素的次数，进而找出。由于要排序，所以效率为O(nlogn)。 利用快排思想，问题转化为求中位数，效率可以达到O(n)。 (2)找出数组中最小的k个数。 普通思路：排序，之后找出最前的k个数字，由于要排序，所以效率为O(nlogn)。 利用快排思想，找出第k个位置左边的数字即可，即一次key值为k位置的排序即可，效率可以达到O(n)。 然而，快排思路解决问题是有限制的，因为他会改变输入的数组。 八.堆排序 1.排序过程 (1)初始化操作：将R[1..n]构造为初始堆； (2)每一趟排序的基本操作：将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换，然后将新的无序区调整为堆（亦称重建堆）。 注意：只需做n-1趟排序，选出较大的n-1个关键字即可以使得文件递增有序。 2.效率 堆排序的时间，主要由建立初始堆和反复重建堆这两部分的时间开销构成。堆排序的最坏时间复杂度为O(nlogn)。堆序的平均性能较接近于最坏性能。由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。堆排序是就地排序，辅助空间为O(1），它是不稳定的排序方法。 (责任编辑：机器AI) |