C++爱好者 - 网友留言

一：直接插入排序
 例：设有八个记录，其关键字为{47，33，61，82，72，11，25，47'}

初始关键字  [47] 33 61 82 72 11 25 47'
 i=2  (33)  [33 47] 61 82 72 11 25 47'
 i=3  (61)  [33 47 61] 82 72 11 25 47'
 i=4  (82)  [33 47 61 82] 72 11 25 47'
 i=5  (72)  [33 47 61 72 82] 11 25 47'
 i=6  (11)  [11 33 47 61 72 82] 25 47'
 i=7  (25)  [11 25 33 47 61 72 82] 47'
 i=8  (47') [11 25 33 47 47' 61 72 82]

直接插入排序的时间复杂度为O(n2)，空间复杂度为O(1)。

二：折半插入排序
 基本思想是:设在顺序表中有一个对象序列V[0],V[1],…,V[n-1]。其中，V[0],V[1],…,V[i-1]是已经排好序的对象。在插入V[i]时,利用折半查找法寻找V[i]的插入位置。

初始关键字  47 33  82 72 11 25 47'
已排序的    11 25 33 47 47' 72 82
 待插数：61
 取中间值 47
排序结果 11 25 33 47 47' 61 72 82
 



三：冒泡排序
 基本思想：通过两两比较待排序元素，若为逆序（递增或递减）则进行交换，将待排序元素从左至右比较一遍称为一趟“冒泡”。每趟冒泡都将待排序列中的最大关键字交换到最后（或最前）位置。直到全部元素有序为止。

初始关键字  47 33 61 82 72 11 25 47'
 第一趟     11 47 33 61 82 72 25 47'
 第二趟     11 25 47 33 61 82 72 47'
 第三趟     11 25 33 47 47' 61 82 72
 第四趟     11 25 33 47 47' 61 72 82
 第五趟     11 25 33 47 47' 61 72 82
 第六趟     11 25 33 47 47' 61 72 82
 第七趟     11 25 33 47 47' 61 72 82

算法分析：最坏情况，比较(n2-n)/2次，移动(n2-n)*3/2。算法时间复杂度O(n2)。

四：快速排序
基本思想：每一步都要把要排序的表（或称做子表的表的一部分）第一个元素放到它在表中的最终位置，同时在这个元素的前面和后面个形成一个子表。在前面子表中的所有元素的关键字都比该元素的关键字小，而在后面子表中的都比它大。此后再对每个子表做这同样的一步，直至最后每个子表都只有一个元素，排序完成。

未排序表    47  33 61 82 72 11  25   47'
             i                 j-1   j
            25  33 61 82 72 11  47   47'
            25  33 47 82 72 11  61   47'
            25  33 11 82 72 47  61   47'
            25  33 11 47 72 82  61   47'
第一步结束 [25  33 11] 47 [72 82 61   47']
           [11  33 25] 47 [47' 82 61  72]
           [11  25 33] 47 [47' 72  61 82]
已排序表   [11  25 33] 47 [47' 61  72 82]


最坏情况的时间复杂度为O(n2)，最好情况时间复杂度为O(nlog2n)。


五：简单选择排序
基本思想是：每次从待排序的记录中选出关键字最小（或最大）的记录，顺序放在已有序的记录序列的最后（或最前）面，直到全部数列有序。
初始关键字  47 33 61 82 72 11 25 47'
 第一趟     11 [33 61 82 72 47 25 47']
 第二趟     11 25 [61 82 72 47 33 47']
 第三趟     11 25 33 [82 72 47 61 47']
 第四趟     11 25 33 47 [72 82 61 47']
 第五趟     11 25 33 47 47'[82 61 72 ]
 第六趟     11 25 33 47 47' 61 [82 72]
 第七趟     11 25 33 47 47' 61 72 [82]

最大移动次数3(n-1)，时间复杂度为O(n2)。

六：2-路归并排序
归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表：即把待排序序列分为若干个子序列，每个子序列是有序的，然后再把有序子序列合并为整体有序序列。
    将已有序的子序列合并，得到完全有序的序列：即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

初始关键字    47 33 61 82 72 11 25 47'
n=8个子文件   [47] [33] [61] [82] [72] [11] [25] [47']
第一趟归并后  [33,47] [61,82] [11,72] [25,47']
第二趟归并后  [33,47,61,82] [11,25,47',72]
第三趟归并后  [11,25,33,47,47',61,72,82]

算法时间复杂度为O(nlog2n)。算法中需要辅助数组。












--------------------next---------------------