第七节 排序（一）

  我们在写程序的时候，经常需要去进行排序这种操作。在面对大量数据进行排序的时候，我们可能需要花费很多的时间和资源。因此，优化排序算法是我们在优化程序中的一个重要步骤。在我们前面的学习中，我们已经接触到了C++的STL中sort()函数。那么，在无法使用STL的情况或者是需要一些特殊的要求的排序，我们就需要对排序算法进行手撸。因此，掌握各种常见的排序方法极为重要。接下来，我们将会从冒泡排序开始，系统地对常见的排序算法进行练习。

冒泡排序（Bubble Sort）

  我们早在学习C语言的时候，就已经接触到这种排序方法了，是一种非常简便的排序方法。我们依次比较相邻的两个元素，以达到排序的目的。冒泡排序的运作方式如下：

重复走访所要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们相互交换
如果这个数列一共有n个元素，我们需要进行n-1组比较，每一组需要进行n-i次比较

  下面是冒泡排序的C语言代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
    int a[15];
    int n=10,i,j,t;
    for(i=0;i<n;i++)
        a[i]=10-i;
    for(i=1;i<n;i++)
        for(j=0;j<n-i;j++) //这里可以记作i+j=n;
        sif(a[j]>a[j+1]) {
                t=a[j];
                a[j]=a[j+1];
                a[j+1]=t;
            }
    for(i=0;i<n;i++)
        printf("%d ",a[i]);
    printf("\n");
    return 0;
}

  冒泡排序是一种常用的排序方法，但是它的时间复杂度为O(n^2)，在做题时不推荐使用。

快速排序（Quick Sort）

  快速排序是对冒泡排序的一种改进，它的基本思想和冒泡排序类似：

通过一趟排序将序列分成两部分
保证左侧部分的数据都比右侧的小
再分别对两侧进行排序

  快速排序是排序算法中的优等生，它的时间复杂度为O(logn)，但是要到达了最不理想的状态，也就是针对一个完全反序的数列进行排序。这个时候，它就变成了冒泡排序，时间复杂度为O(n^2)。在去年的蓝桥杯比赛中，就成为了一道代码填空题，题目是这样的：

排序在各种场合经常被用到。

快速排序是十分常用的高效率的算法。

其思想是：先选一个“标尺”，

用它把整个队列过一遍筛子，

以保证：其左边的元素都不大于它，其右边的元素都不小于它。

这样，排序问题就被分割为两个子区间。

再分别对子区间排序就可以了。

下面的代码是一种实现，请分析并填写划线部分缺少的代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <stdio.h>
void swap(int a[], int i, int j)
{
    int t = a[i];
    a[i] = a[j];
    a[j] = t;
}
int partition(int a[], int p, int r)
{
    int i = p;
    int j = r + 1;
    int x = a[p];
    while(1){
        while(i<r && a[++i]<x);
        while(a[--j]>x);
        if(i>=j) break;
        swap(a,i,j);
    }
______________________;

return j;
}

void quicksort(int a[], int p, int r)
{
    if(p<r){
    int q = partition(a,p,r);
    quicksort(a,p,q-1);
    quicksort(a,q+1,r);
    }
}

int main()
{
    int i;
    int a[] = {5,13,6,24,2,8,19,27,6,12,1,17};
    int N = 12;
    quicksort(a, 0, N-1);
    for(i=0; i<N; i++) printf("%d ", a[i]);
    printf("/n");
    return 0;
}

注意：只填写缺少的内容，不要书写任何题面已有代码或说明性文字。

  这里的答案是swap(a,p,j)，我们就以上面的例子来简单地描述一下快速排序。首先我们看，这个程序中有四个函数，swap()函数实现的是值交换，main()是声明了一个数组，然后对他进行快速排序然后打印出来，我们就不多说了。现在我们来看一下quicksort这个函数。这个函数就是用来实现我们在前面描述过的“分别对两个子区间进行快速排序”这个过程，也比较简单。比较让人头疼就是要我们填空的这个partition()函数。

  下面就让我们来回忆一下快速排序的方法。快速排序就是找一个标尺（一般是一段序列的第一个），比他大的放在他左边，比他小的放在他右边。那么程序上是怎么实现的呢？

  我们需要在程序中定义两个指针，分别从序列的两端出发，左侧的指针向右寻找比标尺大的数据，右侧的指针向左寻找比标尺小的数据，但是在实现上，有两种方法。第一种：先从右侧出发，找到第一个比标尺小的数据，将其和标尺交换位置。然后从左侧出发，找到第一个比标尺大的数据，交换位置，直到两标尺相遇。但是这种方法会频繁地使用赋值操作，那么还有一种改进思路：我们让标尺在a[0]的位置不动，将a[1]作为左侧指针的出发点。两指针分别从左右出发，找到相应的数据之后对两个数据交换位置，直到两个指针相遇。之后再把标尺放在正确的位置上，完成排序。而这个正确的位置呢，就是两指针相遇的位置。

  在partition()函数中，有三个参数，第一个参数i,j,x。i作为low指针，j作为high指针，而x即是标尺。我们看在函数中，i初始化为标尺的位置后，在下面的while循环里，使用的是++i。这就保证了标尺是不移动的，也就是说这个程序使用的是第二种思路。仔细阅读代码，我们可以发现，函数中缺少的正是最后一步——将标尺移动到正确的位置。所以需要补填的代码是swap(a,p,j)。