罗朝辉(飘飘白云)

关注嵌入式操作系统,移动平台,图形开发。-->加微博 ^_^

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  85 随笔 :: 0 文章 :: 169 评论 :: 0 Trackbacks

排序算法之交换排序   

罗朝辉(http://www.cppblog.com/kesalin

转载请注明出处

排序是数据处理中经常使用的一种重要运算,在计算机及其应用系统中,花费在排序上的时间在系统运行时间中占有很大比重,其重要性无需多言。下文将介绍常用的如下排序方法,对它们进行简单的分析和比较,并提供 C 语言实现。


所谓排序,就是要将一堆记录,使之按关键字递增(或递减)次序排列起来。根据排序所采用的策略,可以分为如下五种:

1、插入排序(直接插入排序、希尔排序)

2、交换排序(冒泡排序、快速排序);

3、选择排序(直接选择排序、堆排序);

4、归并排序;

5、桶排序(桶排序,基数排序);


---------------------------------------------------------------------------------


前面我们讲了插入排序,下面接着来讲交换排序。


交换排序的基本思想是:两两比较待排序记录的关键字,发现两个记录的次序相反时即进行交换,直到没有反序的记录为止。应用交换排序基本思想的主要排序方法有:冒泡排序和快速排序。


冒泡排序(Bubble Sorting)


基本思想:从后往前扫描序列,通过相邻元素之间的比较与交换,使值较小的元素逐渐从后部移向前部(从下标较大的单元移向下标较小的单元),就象水底下的气泡一样逐渐向上冒。故称为冒泡排序法。


C 代码实现:

 1void bubble_sort(int* array, int length)
 2{
 3    assert(array && length >= 0);
 4
 5    int i, j, temp;
 6
 7    for (i = 1; i < length; ++i) {
 8        for (j = length - 1; j >= i; --j) {
 9            if (array[j] < array[j - 1]) {
10                temp = array[j];
11                array[j] = array[j - 1];
12                array[j - 1= temp;
13            }

14        }

15    }

16}


   若在某一趟排序中未发现气泡位置的交换,则说明待排序的无序区中所有气泡均满足轻者在上,重者在下的原则,因此,冒泡排序过程可在此趟排序后终止。因此,上面的实现可以优化如下:

 1void bubble_sort(int* array, int length)
 2{
 3    assert(array && length >= 0);
 4
 5    int i, j, temp;
 6    bool exchange;
 7
 8    for (i = 1; i < length; ++i) {
 9        exchange = false;
10
11        for (j = length - 1; j >= i; --j) {
12            if (array[j] < array[j - 1]) {
13                temp = array[j];
14                array[j] = array[j - 1];
15                array[j - 1= temp;
16
17                exchange = true;
18            }

19        }

20
21        if (!exchange) {
22            break;
23        }

24    }

25}


   还可以通过减少排序的趟数作进一步的优化。在每趟扫描中,记住最后一次交换发生的位置 lastExchange (该位置之前的相邻记录均已有序)。下一趟排序开始时,array[1..lastExchange - 1] 是有序区, array[lastExchange..n] 是无序区。这样,一趟排序可能使当前有序区扩充多个记录,从而减少排序的趟数。实现如下:

 1void bubble_sort(int* array, int length)
 2{
 3    assert(array && length >= 0);
 4
 5    int i, j, temp;
 6    bool exchange;
 7    int lastExchange = 1;
 8
 9    for (i = 1; i < length;) {
10        exchange = false;
11
12        for (j = length - 1; j >= i; --j) {
13            if (array[j] < array[j - 1]) {
14                temp = array[j];
15                array[j] = array[j - 1];
16                array[j - 1= temp;
17
18                lastExchange = j;
19                exchange = true;
20            }

21        }

22
23        if (!exchange) {
24            break;
25        }

26
27        i = lastExchange + 1;
28    }

29}


   如果待排序序列是基本有序(比如只有第一个元素是最大的,其他的都已有序,在这种情况下,本该只需要 1 趟排序就可以完成),如果用上面的实现 ,这时平均时间复杂达到最坏 O(n^2)。 在这种情况下,可以通过交替改变扫描方向(从后往前,从前往后,再从后往前...)改变不对称性达到优化的目的。具体实现就留着当作业啦,^_^

时间复杂度:
最好的情况下,待排序记录已经有序,只需要一趟排序就可以完成,所以冒泡排序的最好时间复杂度为 O(n)。
最坏的情况下,待排序记录反序,这时需要 n - 1 趟排序,每趟排序需要比较 n - i 次比较操作,这时比较和移动的次数达到最大值,所以冒泡排序的最坏时间复杂度为 O(n ^ 2)。

冒泡排序的平均时间复杂度为 O(n ^ 2)。因为它移动的次数较多,其平均时间性能还不如直接插入排序。

空间复杂度:
很明显,O(1)。

补充:
冒泡排序是就地排序,且是稳定排序。

快速排序

基本思想:采用分治法。设当前待排序的无序区为 array[low..high],在其中任选一个记录作为基准(Pivot),调整基准在序列中的位置 prvotpos,使左边子区间中所有记录的关键字均小于等于基准记录的关键字,右边的子区间中所有记录的关键字均大于等于基准记录的关键字。即基准将当前无序区划分为左、右两个较小的子区间 array[low..pivotpos - 1] 和 array[pivotpos + 1..high],而基准记录已经处在正确的位置上,它无须参加后续的排序。这时,排序问题就分解成两个子区间的排序问题(这就是分而治之的思想啊), 递归对左右子区间进行快速排序,就可以完成排序。

BTW,分治法的基本思想:将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题,然后将这些子问题的解组合为原问题的解。

代码实现:

 1// 对 [low, high] 做划分,并返回基准记录的位置
 2int quick_partition(int* array, int low, int high)
 3{
 4    assert(array && low >= 0 && low <= high);
 5
 6    int pivot = array[low]; // 用区间的第 1 个记录作为基准
 7
 8    while (low < high) {
 9        while (low < high && array[high] >= pivot) {
10            --high;
11        }

12
13        if (low < high) {
14            array[low++= array[high];
15        }

16
17        while (low < high && array[low] <= pivot) {
18            ++low;
19        }

20
21        if (low < high) {
22            array[high--= array[low];
23        }

24    }

25
26    array[low] = pivot;
27
28    return low;
29}

30
31void quick_sort_impl(int* array, int low, int high)
32{
33    if (low < high) {
34        int pivotPos = quick_partition(array, low, high);
35
36        quick_sort_impl(array, low, pivotPos - 1);
37        quick_sort_impl(array, pivotPos + 1, high);
38    }

39}

40
41// 快速排序
42//
43void quick_sort(int* array, int length)
44{
45    assert(array && length >= 0);
46
47    if (length <= 1{
48        return;
49    }

50
51    quick_sort_impl( array, 0, length - 1);
52}


时间复杂度分析:
最坏情况是每次划分选取的基准都是当前无序区中关键字最小(或最大)的记录,划分的结果是基准左边的子区间为空(或右边的子区间为空),而划分所得的另一个非空的子区间中记录数目,仅仅比划分前的无序区中记录个数减少一个。此时,时间复杂度为 O(n ^ 2)。

在最好情况下,每次划分所取的基准都是当前无序区的"中值"记录,划分的结果是基准的左、右两个无序子区间的长度大致相等。总的关键字比较次数:0(nlgn)。

尽管快速排序的最坏时间为 O(n ^ 2),但就平均性能而言,它是基于关键字比较的内部排序算法中速度最快者,快速排序亦因此而得名。它的平均时间复杂度为 O(nlgn)。

空间复杂度分析:
快速排序需要一个栈来实现递归。若每次划分较为均匀(也就是对半分,基准值总是中值),则其递归树的高度为O(lgn),故递归后需栈空间为O(lgn)。最坏情况下,递归树的高度为O(n),所需的栈空间为O(n)。

补充:
快速排序是非稳定的。例如,对 [5, 5, 1] 进行排序。

对时间复杂度进行分析之后,可以看出,在当前无序区中选取划分的基准关键字是决定算法性能的关键。可以对这个进行一定程度的优化:
第一办法是,取中值,即比较当前无序区间的第一个,中间那个以及最后一个记录的大小,取中间的那个记录作为基准,进行快速排序;
第二个办法是,在当前无需区间中进行随机选取。

测试:
在前文《排序算法之插入排序》测试代码的基础上添加两行代码即可:

SortFucntionInfo sort_function_list[] = {
    {
"直接插入排序",            insert_sort},
    {
"希尔排序",                shell_sort},
    {
"冒泡排序",                bubble_sort},
    {
"快速排序",                quick_sort},
    {
"", NULL}
};

运行结果:


     === 冒泡排序 ===

 original: 65 32 49 10 8 72 27 42 18 58 91

   sorted: 8 10 18 27 32 42 49 58 65 72 91


 original: 10 9 8 7 6 5 4 3 2 1 0

   sorted: 0 1 2 3 4 5 6 7 8 9 10



 === 快速排序 ===

 original: 65 32 49 10 8 72 27 42 18 58 91

   sorted: 8 10 18 27 32 42 49 58 65 72 91


 original: 10 9 8 7 6 5 4 3 2 1 0

   sorted: 0 1 2 3 4 5 6 7 8 9 10


posted on 2011-03-04 23:47 罗朝辉 阅读(1464) 评论(0)  编辑 收藏 引用 所属分类: Algorithms

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理