数据结构

常用的排序方法

排序分为内排序和外排序，区别在于：

内排序：在内存中进行的排序

外排序：当参与排序的数据量特别大，一次不能全部读入内存，此时用内排序方法就不能完成对数据的整体排序，只能将数据存储在文件中，而且在排序过程中需要进行多次的内外存之间的数据交换

在这里，不对外排序作详细描述。主要是针对直接插入排序、冒泡排序、快速排序、直接选择排序以及堆排序展开描述（默认这里的排序是从小到大排序）。

直接插入排序、冒泡排序、快速排序、直接选择排序以及堆排序的性能：

排序方法的性能

快速排序

快速排序是由冒泡排序改进而得的，基本思路是：在待排序的n个记录中任取一个记录t（通常是第一个记录），把记录 t 放在适当位置，将该数据序列一分为二，所有比记录 t 小的放在前一部分，比记录 t 大的放在后一部分，之后，每一部分按递归方式继续上述过程，直到每一部分只有一个记录或空为止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void QuickSort(RectType R[],int s,int t) {
    int i = s,j = t;
    RectType tmp;
    if (s < t)
    {
        tmp = R[s];
        while (i != j)
        {
            while (j > i && R[j].key > tmp.key)
                j--;
            R[i] = R[j];
            while (i < j && R[i].key < tmp.key)
                i++;
            R[j] = R[i];
        }
        R[i] = tmp;
        QuickSort(R, s, i - 1);
        QuickSort(R, i + 1, t);
    }
}

快速排序一趟排序具体过程为（对R[s] 至 R[t]的元素进行快速排序）：

先判断区间内至少存在两个元素，用区间的第一个元素作为基准，从区间两端交替向中间扫描，直至i = j为止。首先，从右向左扫描，找第一个小于tmp.key的 R[j] ，没找到，即 while (j > i && R[j].key > tmp.key)成立时，j 向下移 j–，直到找到这样的R[j]，R[i] 、R[j] 进行交换。
从左向右扫描，找第一个大于tmp.key的 R[i] ，没找到，即 while (i < j && R[i].key < tmp.key)成立时，i 向上移 i++，直到找到这样的R[i]，R[i] 、R[j] 进行交换。
直到i = j，此时将tmp中的记录所指的为止R[i]，接着对左区间递归排序，对右区间递归排序。

比如有一数据序列为{4，2，8，7，9，1，3，6}，排序过程：

快速排序

冒泡排序

冒泡排序的基本思想：对每两个相邻的关键字进行比较，且使关键字较小的记录换至关键字较大的记录之上，使得经过一趟冒泡排序后，关键字最小的记录换到了第一位。接着，再在剩下的记录中找次小的记录，并把它换到第二个位置上，以此类推，一直到所有记录都有序为止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void BubbleSort(RecType R[],int n)
{
    int i,j;
    RecType tmp;
    for (int i = 0; i < n - 1; i++)
    {
        for (int j = n - 1; j > i; j--)
            if (R[j].key < R[j-1].key)
            {
                tmp = R[j];
                R[j] = R[j-1];
                R[j-1] = tmp;
            }
    }
}

但是有些情况下，在第i （i < n -1）趟时已排好序了，但仍执行后面几趟的比较。实际上，一旦算法中某一趟比较时没有出现任何记录交换，说明已经排好序了，就可以结束了。改进后的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void BubbleSort1(RecType R[],int n)
{
    int i,j,exchange;
    RecType tmp;
    for (int i = 0; i < n - 1; i++)
    {
        exchange = 0;
        for (int j = n - 1; j > i; j--)
            if (R[j].key < R[j-1].key)
            {
                tmp = R[j];
                R[j] = R[j - 1]
                R[j-1] = tmp;
                exchange = 1;
            }
        if (exchange == 0)
            return;  // 中途结束
    }
}

比如有一数据序列为{9，8，7，6，5，4，3，2，1，0}，排序过程：
初始序列： 9 8 7 6 5 4 3 2 1 0

i = 0： 0 9 8 7 6 5 4 3 2 1
i = 1： 0 1 9 8 7 6 5 4 3 2
i = 2： 0 1 2 9 8 7 6 5 4 3
i = 3： 0 1 2 3 9 8 7 6 5 4
i = 4： 0 1 2 3 4 9 8 7 6 5
i = 5： 0 1 2 3 4 5 9 8 7 6
i = 6： 0 1 2 3 4 5 6 9 8 7
i = 7： 0 1 2 3 4 5 6 7 9 8
i = 8： 0 1 2 3 4 5 6 7 8 9

未完待续…