第七节 排序(一)

  我们在写程序的时候,经常需要去进行排序这种操作。在面对大量数据进行排序的时候,我们可能需要花费很多的时间和资源。因此,优化排序算法是我们在优化程序中的一个重要步骤。在我们前面的学习中,我们已经接触到了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)