rambo

排序算法(一)选择排序与冒泡排序及稳定性

排序问题 要求按照升序重新排列给定列表中的数据项,基于每个记录内包含的键对这些记录(或者指向这些记录的指针)重新进行排序。这个所谓的键(key)通常是记录内的单个数据项,当然也可以通过考虑记录内的多个数据项来创建这个键。

排序领域有几十种不同的排序算法,但没有一种算法在任何情况下都是最优的。有些算法比较简单,但速度相对较慢;另外一些速度比较快,但更复杂。有些算法比较适合随机排列的输入,而另一些则更适合基本有序的列表。有些算法仅适合排列驻留在快速存储器中的列表,而另一些可以用来对存储在磁盘上的大型文件排序(B树的意义)。

排序的基本特征:

1)稳定的排序是指能够维持要排序的记录中预先存在的顺序。也就是说,如果一个输入列表包含两个相等的元素,它们的位置分别是iji<j,而在排好序的列表中,它们的位置是i^{'},j^{'},那么i^{'}<j^{'}肯定就是成立的。一般来说,将相隔很远的键交换位置的算法虽然不稳定,但往往速度更快。

2)对链表进行排序的能力

虽然几乎所有的排序算法都设计用于对象(或者指向对象的指针)的数组,但是可以轻松的修改一些排序算法,以对链表进行排序;对其他算法则不能这样做。

3)输入的阶的相关性

排序算法的阶或者O()具有显著的差别,阶的范围包括从NN^{2}。估计排序算法的阶的额外问题是:阶可能依赖于待排序的数据。

4)对额外存储空间的需求

一些排序算法需要额外的临时存储空间来存储一个或更多待排序的记录。一种可能不是立即显而易见的额外空间是以递归方式实现的排序算法对栈空间的需求。

5)内部排序技术与外部排序技术

在内部排序中,可以同时把待排序的所有记录都加载进主内存中,外部排序在排序期间一部分记录将总是驻留在大容量存储设备上。所有外部排序的基本策略就是:将待排序的数据分成块,这些块非常小,足以放入主内存中,并且利用内部排序技术一次对其中一个块进行排序,然后合并这些块,最终产生排好序的输出。当需要对大量数据进行排序时,将数据加载进B树。
QQ截图20150823025955

蛮力法在排序问题中应用
1、选择排序
扫描整个列表,找到它的最小元素,然后和第一个元素交换,将最小元素放到它在有序表中的最终位置上。从第二个元素开始扫描列表,找到最后n-1个元素中的最小元素,再和第二个元素交换位置。也就是说,在对该列表做第i遍扫描的时候(i的值从0~n-2),该算法在最后的n-i个元素中寻找最小元素,然后和元素A_{i}交换。

QQ截图20150613223139

 

 

 

伪代码,基于数组:

QQ截图20150613223152

QQ截图20150613223903

该算法的基本操作是键值比较A[j]<A[min]。这个比较的执行次数仅仅依赖于数组的规模。

QQ截图20150613223838

QQ截图20150613223846

对于任何输入来说,选择排序都是一个O(n^{2})的算法,键的交换次数仅为O(n),更精确的是n-1次。

注意:选择排序不是稳定的排序。自己推导下就可以得出这个结论。(89 45 68 45 90 29 34 17)

 2、冒泡排序

比较表中的相邻元素,如果它们是逆序的话就交换它们的位置。重复多次以后,最终,最大的元素就沉到列表中的最后一个位置。第二遍操作就将第二大的元素沉下去。这样做n-1遍后,该列表就排好序了。

伪代码,基于数组:

QQ截图20150613225400

QQ截图20150613225212

对于所有规模为n的数组,该冒泡排序版本的键值比较次数都是相同的。

QQ截图20150613225847

但它的键交换次数取决于特定的输入。最坏的情况就是遇到降序的数组,这时,键交换次数和键比较次数是相同的。

QQ截图20150613230009