排序复习

若表R在排序前已按关键字正序排序,则___方法的比较次数最少?
A.直接插入排序
B.快速排序
C.归并排序
D.选择排序

A 插入排序
插入排序是把当前K位置上的数在之前【(0)…..(k-1)】比较找一个位置插入,根据题意,第一次比较(即(k-1))就会判定结束,插入位置为原位置K.
所以时间复杂度为O(1*n) = O(n)

B快速排序
冒泡排序和快速排序都属于交换排序,

冒泡排序是判定将无序区内最大(或最小)的元素与无序区内第一位置交换,然后并入之前的有序区。
实际上,一旦算法中某一趟比较时不出现记录交换,说明已排好序了,就可以结束本算法。
比如
0 1 2 3 4 5 6 7 位置号码
0 1 2 3 4 5 6 7 数值
我们有循环
i 从 0到7
j 从 7到i-1 每到a[j]<a[j-1]时 交换他们,当出现01234567的数值串时,无论如何都不会出现交换。
优化后的冒泡排序实际上在本题的时间复杂度是O(n-1)。

快速排序的主要理念是选出一个元素当“枢轴”,让比他大(或小)的元素在他的左(或右),这样就可以使用递归方法再次对“枢轴”两边分别快排,整个数据操作的总任务就是“选择枢轴,调整队列后放下枢轴”。
书上的快排算法默认去每次快排目标第一位做为“枢轴”。然后算法全部比较后发现枢轴应摆在第一位。比如我们用B表示枢轴+表示任意数
B+++++       
   B++++
      B+++
         B++
而理想的快排为 
+++B+++
+B+   +B+ 
这里我可能说的不是很清楚。估计此时(上面情况时)快排的时间复杂度近似于  n+ n-1 + n-2 +….+1 = (n+1)*n/2

C 归并排序

归并的思想很简单,我们在刚学链表的时候有试过把两个有序的链表合成一个有序的链表,总的来说就是每次对链头的元素比较,然后取大(或小)的加入新的队列。

标准的归并排序是稳定的算法,不会因为特殊情况而时间复杂度改变。
时间复杂度为O(NlogN).

D 选择排序
选择排序分为
直接选择排序(或简单选择排序)和 堆排序

直接选择排序有点类似冒泡,但是不同处很明显。
冒泡每次都对相邻位置不"和谐"(不符合有序关系)的地方交换位置,使他们总是大的在后面(或者总是小的在后面)。
直接选择排序则只在无序区内找出最小的(或者最大的),放到最前。
根据思想可以计算时间复杂度,
0 1 2 3 4 5 6 7 位置
0 1 2 3 4 5 6 7 数值
设 i 从 0 到 6 遍历队列,那么对应 i 每次状态,都要找一个最小数出来,
(从8个数里面找1个最小的,要比较几次?)
则 要比较 7+6+5+4+3+2+1 次 所以比较 n(n-1)/2次,
然后如果加上移动位置的时间消耗(最小值为 0, 最大值为3(n-1) 。)当然这里不会算上。
不管怎么说,也算O(N^2)了。

堆排序是不断维护一棵完全二叉树而取得最大值或最小值的方法,在取得最大最小值后可以借助选择排序的思想把他“归位”,在继续维护二叉树。

理解堆排序需要先理解怎么把一个队列看成二叉树堆

1    2    3    4    5     6      7    8     9    10    11
12, 36, 27, 65, 40, 34, 98, 81, 73, 55, 49

我们规定(假定肯定设定) i位置是 2i位置和2i+1位置的父亲,事实上在完全二叉树里面他们就是。
那么12(1)的儿子就是36(2)和27(3)等等,具体大根小根概念就不说了。
注意有序才是堆,随便一棵满二叉树不叫堆,还叫树。

书上的堆排方法是多次优化后的,有很巧妙的地方。
比如把堆顶的元素放到最后,堆长度-1就是为了遵循选择排序(每次选最大或者最小的放到后面)
关于堆排书上有详细介绍,(实际上是我懒得打了,脚冷。。。)。
这里最后在扯皮一点点,生成初始堆h(=logn+1)需要比较大约2.54n次
然后n-1次的调整“堆顶”2 (log(n-1)+ log(n-2)+ …+log2) < 2n(logn)
实际上是 2.54n+2nlogn = nlogn

所以
A O(n)
B (n+1)*n/2 ~ n^2
C O(NlogN).
D O(NlogN)

此条目发表在C, 编程分类目录,贴了标签。将固定链接加入收藏夹。

发表评论

邮箱地址不会被公开。 必填项已用*标注