排序和搜索

发表于 | 更新于 | 分类于

排序和搜索

排序算法分为两大类：比较排序和线性时间排序。比较排序依赖于比较和交换来将元素移动到正确的位置上。令人惊讶的是，并不是所有的排序算法都依赖于比较。对于那些确实依赖于比较来进行排序的算法来说，它们的运行时间往往不可能小于O(nlg n)。对于线性时间排序，从它的名字就可以看出，它的运行时间往往与它处理的数据元素个数成正比，即为O(n)。遗憾的是，线性时间排序依赖于数据集合中的某些特征，所以我们并不是在所有的场合都能够使用它。某些排序算法只使用数据本身的存储空间来处理和输出数据（这些称为就地排序），而有一些则需要额外的空间来处理和输出数据（虽然可能最终结果还是会拷贝到原始的内存空间中）。

搜索就是在一个数据集中找到一个元素的位置，它可用于任何任务中。一种最简单的、不需要费任何脑筋的搜索方法是：简单地从数据集的一端查找到另一端。这就是所谓的线性搜索。通常，线性搜索用在那些对随机访问支持得不太好的数据结构中，例如：链表。另一种方法是使用二分查找，这会在本章中介绍。还有一些搜索方法专门用于特定的数据结构，例如哈希表和二叉树。

插入排序（Insertion sort）

描述

插入排序虽然不是最有效的排序方法，但它简单，并且不需要额外的存储空间。其最佳应用场景是对一个小的数据集合进行递增排序。

插入排序每次从无序数据集中取出一个元素，扫描已排好序的数据集，并将它插入有序集合合适的位置上。虽然乍一看，插入排序需要独立为有序和无序的元素集合预留足够的存储空间，但实际上它是不需要额外的存储空间的。

插入排序是一种较为简单的算法，但是它在处理大型数据集时并不高效。因为很明显，在决定将元素插入哪个位置之前，需要将被插入元素和有序数据集中的其他元素进行比较，这会随着数据集的增大而增加额外的开销。然而插入排序的优点是，当将元素插入一个有序数据集中时，只需要对有序数据集最多进行一次遍历，而不需要完整地运行算法。这个特性使得插入排序在增量排序中非常高效。

分析

插入排序使用一个嵌套循环来解决问题。外部循环用标号j来控制元素，使元素从无序数据集中插入有序数据集中。由于待插入的元素总是会被插入有序数据集的右边，因此也可以认为j是data中分隔有序元素集和无序元素集的界线。对于每个处于位置j的元素，都会使用变量i来向后查找元素将要放置的位置。当向后查找数据时，每个处于位置i的元素都要向右移动一位，以保证预留出足够的空间来插入新元素。一旦j到达无序数据集的尾部，data就是一个有序数据集了。

插入排序的时间复杂度关键在于它的嵌套循环部分。考虑到这一点，外部循环运行时间T（n）=n-1，乘以一段固定时间，其中n为要排序元素的个数。考虑内部循环运行在最坏的情况，假设在插入元素之前，必须从右到左遍历完所有的元素。这样的话，内部循环对于第一个元素迭代一次，对于第二个元素迭代二次，以此类推，直到外循环终止。嵌套循环的运行时间表示为从1到n-1数据的和，即运行时间T（n）=（n（n+1）/2-n，乘以一段固定时间。（这是由1到n的著名求和公式推导出来。）用O表示法可以简化为O（n2）。当在递增排序中使用插入排序时，其时间复杂度为O（n）。插入排序不需要额外的空间，因此它只使用无序数据本身的存储空间即可。

实现

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <stdio.h>
#include <stdlib.h>
#include <string.h>


int issort(void *data, int size, int esize,
           int (*compare)(const void *key1, const void *key2)) {
    char *a = data;
    void *key;
    int i, j;
    
    if ((key = (char *)malloc(esize)) == NULL)
        return -1;
    
    for (j = 1; j < size; j++) {
        memcpy(key, &a[j * esize], esize);
        i = j - 1;
        while (i >= 0 && compare(&a[i * esize], key) > 0) {
            memcpy(&a[(i + 1) * esize], &a[i * esize], esize);
            i--;  
        } 
        memcpy(&a[(i + 1) * esize], key, esize);  
    }
    
    free(key);
    return 0; 
}

static void print_idata(const int *array, int size) {
    for (int i = 0; i < size; i++)
        fprintf(stdout, " %d", array[i]);
    
    fprintf(stdout, "\n");
    return;
}

static int compare_int(const void *int1, const void *int2) {
    if (*(const int *)int1 > *(const int *)int2)
        return 1;
    else if (*(const int *)int1 < *(const int *)int2)
        return -1;
    else
        return 0;
}

int main(int argc, char **argv) {
    int iarray[10] = {0, 5, 1, 7, 3, 2, 8, 9, 4, 6};    
    int size = 10;
    
    fprintf(stdout, "Before issort\n");
    print_idata(iarray, size);
    
    if (issort(iarray, size, sizeof(int), compare_int) != 0)
        return 1;
    
    fprintf(stdout, "After issort\n");
    print_idata(iarray, size);
    
    return 0;
}

控制台输出

1
2
3
4
Before issort
 0 5 1 7 3 2 8 9 4 6
After issort
 0 1 2 3 4 5 6 7 8 9

快速排序（Quick sort）

在一般情况下，一致认为快速排序是最好的一种排序算法，而且不需要额外的存储空间。其最佳应用场合是应用于大型数据集。

描述

快速排序是一种分治排序算法。广泛认为它是解决一般问题的最佳排序算法。同插入排序一样，快速排序也属于比较排序的一种，而且不需要额外的存储空间。在处理中到大型数据集时，快速排序是一个比较好的选择。

由于快速排序是一种分治算法，因此可以用分治法的思想将排序分为三个步骤，这样有助我们理解：

  • 分：设定一个分割值并将数据分为两部分。
  • 治：分别在两部分用递归的方式继续使用快速排序法。
  • 合：对分割部分排序直至完成。

考虑到其流行程度，快速排序最坏情况下的性能不会比插入排序的最坏情况好。而事实上，通过一点点修改，可以大大改善快速排序最坏情况的效率，使其表现得与其平均情况相当。怎样做到这一点，关键取决于如何选择分割值。“如果选择的分割值会将大部分的元素放到其中一堆中，那么此时快速排序的性能会非常差。所选分割值需要尽可能地将元素平均分开。

选择分割值的一种行之有效的方法是通过随机选择法来选取。还可以改进这种随机选择方法，方法是首先随机选择三个元素，然后选择三个元素中的中间值。这就是所谓的中位数方法，可以保证平均情况下的性能。由于这种分割方法依赖随机数的统计特性，从而保证快速排序的整体性能，因此快速排序是随机算法的一个好例子。

接口定义

1
2
int qksort(void *data, int size, int esize, int i, int k,
	int (*compare) (const void *key1, const void *key2));

返回值 如果排序成功，返回0；否则，返回-1。

描述 利用快速排序将数组data中的元素进行排序。数组中的元素个数由size决定。而每个元素的大小由esize决定。参数i和k定义当前进行排序的两个部分，其值分别初始化为0和size-1。函数指针compare会指向一个用户定义的函数来比较元素大小。其函数功能与issort中描述的一样。当qksort返回时，data包含已排序的元素。

复杂度 O(nlg n)，n为要被排序的元素的个数。

分析

首先用之前提到过的中位数法选取一个分割值。一旦选定分割值，就将k往data的左边移动，直到找到一个小于或等于分割值的元素。这个元素属于左边分区。接下来，将i往右边移动，直到找到一个大于或等于分割值的元素。这个元素属于右边分区。一旦找到的两个元素处于错误的位置，就交换它们的位置。重复这个过程直到i和k重合。（你可能会问，我们如何知道，如果一个元素处在错误的分区，总会有一个可以用来交换的元素处在另一外分区。）一旦i和k重合，那么所有处于左边的元素将小于等于它，所有处于右边的值将大于等于它。

在初次调用qksort时，i设置为0，k设置为size-1。首先调用partition将data中处于i和k之间的元素分区。当partition返回时，把j赋予分割点的元素。接下来，递归调用qksort来处理左边的分区（从i到j）。左边的分区继续递归，直到传入qksort的一个分区只包含单个元素。此时i不会比k小，所以递归调用终止。同样，分区的右边也在进行递归处理，处理的区间从j+1至k。总的来说，以这种递归方式继续运行，直到首次达到qksort终止的条件，此时，数据就完全排好序了。

围绕其平均情况下的性能分析是快速排序的重点，因为一致认为平均情况是它复杂度的度量。虽然在最坏的情况下，其运行时间（为O(n2)）并不比插入排序好，但快速排序的性能一般能比较有保障地接近其平均性能（为O(nlg n)，其中n要排序元素的个数）。

实现

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include <stdio.h>
#include <stdlib.h>
#include <string.h>


static void print_idata(const int *array, int size) {
    int i;
    for (i = 0; i < size; i++)
        fprintf(stdout, " %d", array[i]);
    
    fprintf(stdout, "\n");
    return;
}

int issort(void *data, int size, int esize,
           int (*compare)(const void *key1, const void *key2)) {
    char *a = data;
    void *key;
    int i, j;
    
    if ((key = (char *)malloc(esize)) == NULL)
        return -1;
    
    for (j = 1; j < size; j++) {
        memcpy(key, &a[j * esize], esize);
        i = j - 1;
        while (i >= 0 && compare(&a[i * esize], key) > 0) {
            memcpy(&a[(i + 1) * esize], &a[i * esize], esize);
            i--;  
        } 
        memcpy(&a[(i + 1) * esize], key, esize);  
    }
    
    free(key);
    return 0; 
}

static int compare_int(const void *int1, const void *int2) {
    if (*(const int *)int1 > *(const int *)int2)
        return 1;
    else if (*(const int *)int1 < *(const int *)int2)
        return -1;
    else
        return 0;
}

static int partition(void *data, int esize, int i, int k, int (*compare)
                     (const void *key1, const void *key2)) {
    char *a = data;
    void *pval, *temp;
    int r[3];
    
    // Allocate storage for the partition value and swapping
    if ((pval = malloc(esize)) == NULL)
        return -1;
    
    if ((temp = malloc(esize)) == NULL) {
        free(pval);
        return -1;
    }
    
    // Use the median-of-three method to find the partition value
    r[0] = (rand() % (k - i + 1)) + i;
    r[1] = (rand() % (k - i + 1)) + i;
    r[2] = (rand() % (k - i + 1)) + i;
    issort(r, 3, sizeof(int), compare_int);
    memcpy(pval, &a[r[1] * esize], esize);
    
    // Create two partitions around the partition value
    i--;
    k++;
    
    while (1) {
        
        // Move left until an element is found in the wrong partition
        do {
            k--;
        } while (compare(&a[k * esize], pval) > 0);
        
        // Move right until an element is found in the wrong partition
        do {
            i++;
        } while (compare(&a[i * esize], pval) < 0);
        
        if (i >= k) {
            // Stop partitioning when the left and right counters cross
            break;   
        } else {
            // Swap the elements now under the left and right counters
            memcpy(temp, &a[i * esize], esize);
            memcpy(&a[i * esize], &a[k * esize], esize);
            memcpy(&a[k * esize], temp, esize);
        }
    }
    
    // Free the storage allocated for partitioning
    free(pval);
    free(temp);
    
    // Return the position dividing the two partitions
    return k;
    
}

int qksort(void *data, int size, int esize, int i, int k,
           int (*compare)(const void *key1, const void *key2)) {
    
    int j;
    
    // Stop the recursion when it is not possible to partition further
    if (i < k) {
        // Determine where to partition the elements
        if ((j = partition(data, esize, i, k, compare)) < 0)
            return -1;
        
        // Recursively sort the left partition
        if (qksort(data, size, esize, i, j, compare) < 0)
            return -1;
        
        // Recursively sort the right partition
        if (qksort(data, size, esize, j + 1, k, compare) < 0)
            return -1;
    }
    return 0;
}



int main(int argc, char **argv) {
    int qarray[10] = {0, 5, 1, 7, 3, 2, 8, 9, 4, 6};    
    int size = 10;
    
    fprintf(stdout, "Before qksort\n");
    print_idata(qarray, size);
    
    if (qksort(qarray, size, sizeof(int), 0, size - 1, compare_int) != 0)
        return 1;
    
    fprintf(stdout, "After qksort\n");
    print_idata(qarray, size);
    
    return 0;
}

控制台输出

1
2
3
4
Before qksort
 0 5 1 7 3 2 8 9 4 6
After qksort
 0 1 2 3 4 5 6 7 8 9

归并排序（Merge sort）

归并排序基本上与快速排序算法的性能相同，但它需要使用两倍于快速排序的存储空间。而具有讽刺意味的是，其最佳应用场景是在超大数据集中，因为归并排序的原理就是对原始的乱序数据不断进行对半分割。

描述

像快速排序算法一样，由于归并排序也是一种分治算法，因此可以用分治法的思想将排序分为三个步骤，这样有助我们理解：

  1. 分：将数据集等分为两半。
  2. 治：分别在两个部分用递归的方式继续使用归并排序法。
  3. 合：将分开的两个部分合并成一个有序的数据集。

归并排序与其他排序最大的不同在于它的归并过程。这个过程就是将两个有序的数据集合并成一个有序的数据集。正如我们看到的，合并两个有序数据集的过程是高效的，因为我们只需要遍历一次即可。根据以上事实，再加上该算法是按照可预期的方式来划分数据的，这使得归并排序在所有的情况下都能达到快速排序的平均性能。

遗憾的是，归并排序需要额外的存储空间来运行，这也是它的一个缺点。因为合并过程不能在无序数据集本身中进行，所以必须要有两倍于无序数据集的空间来运行算法。这点不足极大地降低实际中使用归并排序的频率，因为通常可以使用不需要额外存储空间的快速排序来代替它。然而，归并排序对于海量数据处理还是非常有价值的，因为它能够按预期将数据集分开。这使得我们能够将数据集分割为更加可管理的数据块，接着用归并排序进行处理，然后不断地合并数据，在这个过程中并不需要一次存储所有的数据。

接口定义

1
2
int mgsort(void *data, int size, int esize, int i, int k,
	int (*compare)(const void *key1, const void *key2));

返回值　如果排序成功，返回0；否则，返回-1。

描述　利用归并排序将数组data中的元素进行排序。数组中的元素个数由size决定。而每个元素的大小由esize决定。参数i和k定义当前进行排序的两个部分，其值分别初始化为0和size-1。函数指针compare会指向一个用户定义的函数来比较元素大小。其函数功能与issort中描述的一样。当mgsort返回时，data中包含已排序的元素。

复杂度　O(nlg n)，n为要排序的元素的个数。

分析

归并排序本质上是将一个无序元素集分割成许多个只包含一个元素的集，然后不断地将这些小集合并，直到一个新的大有序数据集生成。

最初，ipos和jpos指向每个有序集的头部。只要数据集中还有元素存在，合并过程就将持续下去。如果数据集中没有元素，进行如下操作：如果一个集合没有要合并的元素，那么将另外一个集中要合并的元素全部放到合并的集合中。否则，首先比较两个集合中的首元素，判断哪个元素将要放到合并的集合中，然后将它放置进去，接着根据元素来自的集合移动ipos或jpos的位置（见下图），依此类推。

现在我们来看看在mgsort中如何处理递归。在初次调用mgsort时，i设置为0，k设置为size-1。首先，分割data，此时j处于数据中间元素的位置。然后，调用mgsort来处理左边分区（从i到j）。左边的分区继续递归分割，直到传入mgsort的一个分区只包含单个元素。在此过程中，i将不小于k，因此调用过程终止，在前一个mgsort过程中，在分区的右边也在调用mgsort，处理的区间从j+1至k。一旦调用过程终止，就开始归并两个数据集。总的来说，以这种递归方式继续，直到最后一次归并过程完成，此时，数据就完全排好序了（见下图）。

实现

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <stdio.h>
#include <stdlib.h>
#include <string.h>


static void print_idata(const int *array, int size) {
    int i;
    for (i = 0; i < size; i++)
        fprintf(stdout, " %d", array[i]);
    
    fprintf(stdout, "\n");
    return;
}

static int compare_int(const void *int1, const void *int2) {
    if (*(const int *)int1 > *(const int *)int2)
        return 1;
    else if (*(const int *)int1 < *(const int *)int2)
        return -1;
    else
        return 0;
}

static int merge(void *data, int esize, int i, int j, int k,
                 int (*compare)(const void *key1, const void *key2)) {
    char *a = data, *m;
    int ipos, jpos, mpos;
    
    ipos = i;
    jpos = j + 1;
    mpos = 0;
    
    // Allocate storage for the merged element
    if ((m = (char *)malloc(esize * ((k - i) + 1))) == NULL)
        return -1;
    
    // Continue while either division has elements to merge
    while (ipos <= j || jpos <= k) {
        if (ipos > j) {
            // The left division has no more elements to merge
            while (jpos <= k) {
                memcpy(&m[mpos * esize], &a[jpos * esize], esize);
                jpos++;
                mpos++; 
            }
            continue;
        } else if (jpos > k) {
            // The right division has no more elements to merge
            while (ipos <= j) {
                memcpy(&m[mpos * esize], &a[ipos * esize], esize);
                ipos++;
                mpos++; 
            }
            continue;
        }
        
        // Append the next ordered element to the merged elements
        if (compare(&a[ipos * esize], &a[jpos * esize]) < 0) {
            memcpy(&m[mpos * esize], &a[ipos * esize], esize);
            ipos++;
            mpos++;
        } else {
            memcpy(&m[mpos * esize], &a[jpos * esize], esize);
            jpos++;
            mpos++;
        }
    }
    
    // Prepare to pass back the merged data
    memcpy(&a[i * esize], m, esize * ((k - i) + 1));
    
    //Free the storage allocated for merging
    free(m);
    return 0;
    
}

int mgsort(void *data, int size, int esize, int i, int k,
           int (*compare)(const void *key1, const void *key2)) {
    int j;
    
    // Stop the recursion when no more divisions can be made
    if (i < k) {
        j = (int)(((i + k - 1)) / 2);
        
        // Recursively sort the two divisions
        if (mgsort(data, size, esize, i, j, compare) < 0)
            return -1;
        
        if (mgsort(data, size, esize, j + 1, k, compare) < 0)
            return -1;
        
        // Merge the two sorted divisions into a single sorted set
        if (merge(data, esize, i, j, k, compare) < 0)
            return -1;
    }
    return 0;
}

int main(int argc, char **argv) {
    int mgarray[10] = {0, 5, 1, 7, 3, 2, 8, 9, 4, 6};    
    int size = 10;
    
    fprintf(stdout, "Before mgsort\n");
    print_idata(mgarray, size);
    
    if (mgsort(mgarray, size, sizeof(int), 0, size - 1, compare_int) != 0)
        return 1;
    
    fprintf(stdout, "After mgsort\n");
    print_idata(mgarray, size);
    
    return 0;
}

控制台输出

1
2
3
4
Before mgsort
 0 5 1 7 3 2 8 9 4 6
After mgsort
 0 1 2 3 4 5 6 7 8 9

计数排序（Counting sort）

计数排序是一种稳定的线形时间排序算法，当知道数据集中整数的最大值的情况下会经常用到此算法。它主要用来实现基数排序。

描述

计数排序是一种高效的线性排序，它通过计算一个集合中元素出现的次数来确定集合如何排列。不同于之前介绍的一些算法是基于比较的，计数排序不需要进行元素比较，而且它的运行效率要比效率为O(nlg n)比较排序高。

计数排序有一定的局限性。其中最大的局限就是它只能用于整型或者那些可以用整型来表示的数据集合。这是因为计数排序利用一个数组的索引来记录元素出现的次数。例如，如果整数3出现过4次，那么4将存储到数组索引为3的位置上。同时，我们还需要知道集合中最大整数的值，以便于为数组分配足够的空间。

除了速度快之外，计数排序的另一个优点就是非常稳定。稳定的排序能使具有相同数值的元素有相同的顺序，就像它们在原始集合中表现出来的一样。在某些情况下，这是一个重要的特性，我们将在基数排序中看到这一点。

接口定义

1
int ctsort(int *data, int size, int k);

返回值　如果排序成功，返回0；否则，返回-1。

描述　利用计数排序将数组data中的整数进行排序。data中的元素个数由size决定。参数k为data中最大的整数加1。当ctsort返回时，data中包含已排序的元素。

复杂度　O(n+k)，n为要排序的元素的个数，k为data中最大的整数加1。

分析

计数排序本质上是通过计算无序集合中整数出现的次数来决定集合应该如何排序的。在以下介绍的实现方法中，data初始包含size个无序整型元素，并存放在单块连续的存储空间中。另外需要分配存储空间来临时存放已排序的元素。在ctsort返回时，得到的有序集合将会拷贝回data。

分配了存储空间后，首先计算data中每个元素出现的次数（见下图）。这些结果将存储到计数数组counts中，并且数组的索引值就是元素本身（见下图1b）。一旦data中的每个元素出现的次数都统计出来后，就调整计数值，使元素在进入有序集合之前，清楚每个元素插入的次数。用元素本身的次数加上它后一个元素的次数（见图12-6步骤1c）。事实上，此时counts包含每个元素在有序集合temp中的偏移量。

要完成排序，还必须按照元素在temp中的偏移量放置元素（图12-6步骤2a～2f）。当temp更新时每个元素的计数要减1，这样在data中出现不止一次的整数也会在temp出现不止一次，这样保持同步。

实现

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <stdio.h>
#include <stdlib.h>
#include <string.h>


static void print_idata(const int *array, int size) {
    int i;
    for (i = 0; i < size; i++)
        fprintf(stdout, " %d", array[i]);
    
    fprintf(stdout, "\n");
    return;
}

int ctsort(int *data, int size, int k) {
    int *counts, *temp;
    int i, j;
    
    // Allocate storage for the counts
    if ((counts = (int *)malloc(k * sizeof(int))) == NULL)
        return -1;
    
    // Allocate storage for the sorted elements
    if ((temp = (int *)malloc(size * sizeof(int))) == NULL)
        return -1;
    
    // Initialize the counts
    for (i = 0; i < k; i++)
        counts[i] = 0;
    
    // Count the occurrences of each element
    for (j = 0; j < size; j++)
        counts[data[j]] = counts[data[j]] + 1;
    
    // Adjust each count to reflect the counts before it
    for (i = 1; i < k; i++)
        counts[i] = counts[i] + counts[i - 1];
    
    // Use the counts to position each element where it belongs
    for (j = size - 1; j >= 0; j--) {
        temp[counts[data[j]] - 1] = data[j];
        counts[data[j]] = counts[data[j]] - 1;
    }
    
    // Prepare to pass back the sorted data
    memcpy(data, temp, size * sizeof(int));
    
    // Free the storage allocated for sorting
    free(counts);
    free(temp);
    
    return 0;
}

int main(int argc, char **argv) {
    int carray[10] = {0, 5, 1, 7, 3, 2, 8, 9, 4, 6};    
    int size = 10;
    
    fprintf(stdout, "Before ctsort\n");
    print_idata(carray, size);
    
    if (ctsort(carray, size, 10) != 0)
        return 1;
    
    fprintf(stdout, "After ctsort\n");
    print_idata(carray, size);
    
    return 0;
}

控制台输出

1
2
3
4
Before ctsort
 0 5 1 7 3 2 8 9 4 6
After ctsort
 0 1 2 3 4 5 6 7 8 9

基数排序（Radix sort）

基数排序是逐位对元素进行排序的线性时间排序算法。基数排序适用于固定大小的元素集，并且其中的元素易于分割，且易于用整数表示。

描述

基数排序是另外一种高效的线性排序算法。其方法是将数据按位分开，并从数据的最低有效位到最高有效位进行比较，依次排序，从而得到有序数据集合。我们来看一个例子，用基数排序对十进制数据 {15,12,49,16,36,40} 进行排序。在对个位进行排序之后，其结果为 {40,12,15,16,36,49}，在对十位进行排序之后，其结果为 {12,15,16,36,40,49}。

有一点非常重要，在对每一位数值进行排序时其排序过程必须是稳定的。因为，一旦一个数值通过较低有效位的值进行排序之后，此数据的位置不应该改变，除非通过较高有效位的值进行比较后需要它调整位置。例如，在以上的例子中，整数12和15的十位数都包含1，当对其十位数进行排序时，一个不稳定的排序算法可能不会维持其在个位数排序过程中的顺序。而一个稳定的排序算法可以保证它们不重新排序。基数排序会用到计数排序，因为对于基数排序来说，除了稳定性，它还是一种线性算法，且必须知道每一位可能的最大整数值。

基数排序并不局限于对整型数据进行排序，只要能把元素分割成整型数，就可以使用基数排序。例如，可以对以2^8为基数字符串进行基数排序；或者，可以对64位的整数，按4位以2^16为基数的值进行排序。具体该选择什么值作为基数取决于数据本身，同时考虑到空间的限制，需要将pn+pk最小化。（其中p为每个元素的位数，n为元素的个数，k为基数）。一般情况下，通常使k小于等于n。

接口定义

1
int rxsort(int *data, int size, int p, int k);

返回值　如果排序成功，返回0；否则，返回-1。

描述　利用计数排序将数组data中的整数进行排序。数组data中整数的个数由size决定。参数p指定每个整数包含的位数，k指定基数。当rxsort返回时，data包含已排序的整数。

复杂度　O(pn+pk)，n为要排序的元素的个数，k为基数，p为位的个数。

分析

基数排序实质上是在元素每一位上应用计数排序来对数据集合排序。

如果我们理解计数排序的方法，那么基数排序也就非常简单了。单个循环控制正在进行排序的位置（见下图）。从最低位开始，一个位置一个位置地应用计数排序来不断调整元素。一旦调整完了最高有效位的数值，排序过程完成。获取每位数值的简单方法就是使用幂运算和模运算。这对于整数来说特别有效，但不同的数据类型需要使用不同的方法。有一些方法可能需要考虑机器具体细节，例如字节顺序和字对齐。

实现

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>


static void print_idata(const int *array, int size) {
    int i;
    for (i = 0; i < size; i++)
        fprintf(stdout, " %d", array[i]);
    
    fprintf(stdout, "\n");
    return;
}

int rxsort(int *data, int size, int p, int k) {
    int *counts, *temp;
    int index, pval, i, j, n;
    
    // Allocate storage for the counts
    if ((counts = (int *)malloc(k * sizeof(int))) == NULL)
        return -1;
    
    // Allocate storage for the sorted elements
    if ((temp = (int *)malloc(size * sizeof(int))) == NULL)
        return -1;
    
    // Sort from the least significant position to the most significant
    for (n = 0; n < p; n++) {
        
        // Initialize the counts
        for (i = 0; i < k; i++)
            counts[i] = 0;
        
        // Calculate the position value
        pval = (int)pow((double)k, (double)n);
        
        // Count the occurrences of each digit value
        for (j = 0; j < size; j++) {
            index = (int)(data[j] / pval) % k;
            counts[index] = counts[index] + 1;
        }
        
        // Adjust each count to reflect the counts before it
        for (i = 1; i < k; i++)
            counts[i] = counts[i] + counts[i - 1];
        
        // Use the counts to position each element where it belongs
        for (j = size - 1; j >= 0; j--) {
            index = (int)(data[j] / pval) % k;
            temp[counts[index] - 1] = data[j];
            counts[index] = counts[index] - 1;
        }
        
        // Prepare to pass back the data as sorted thus far
        memcpy(data, temp, size * sizeof(int));
    }
    
    // Free the storage allocated for sorting
    free(counts);
    free(temp);
    
    return 0;
}

int main(int argc, char **argv) {
    int rarray[10] = {11111323, 99283743, 98298383, 99987444,
        43985209, 99911110, 11111324, 39842329, 97211029, 99272928};    
    int size = 10;
    
    fprintf(stdout, "Before rxsort\n");
    print_idata(rarray, size);
    
    if (rxsort(rarray, size, 8, 10) != 0)
        return 1;
    
    fprintf(stdout, "After rxsort\n");
    print_idata(rarray, size);
    
    return 0;
}

控制台输出

1
2
3
4
Before rxsort
 11111323 99283743 98298383 99987444 43985209 99911110 11111324 39842329 97211029 99272928
After rxsort
 11111323 11111324 39842329 43985209 97211029 98298383 99272928 99283743 99911110 99987444

二分查找（Binary search）

在一个不期望频繁地进行插入和删除操作的有序数据集中，使用二分查找非常高效。因为通常排序的代价大于搜索的代价。当数据集不变时，二分搜索的应用效果最佳。

描述

二分查找是对一个有序数据集合所做的操作。查找开始时，首先找出有序集合中间的那个元素。如果此元素比要查找的元素大，就接着在较小的一个半区进行查找；反之，如果此元素比要查找的元素小，就在较大的一个半区进行查找。在每个更小的数据集中重复这个查找过程，直到找到要查找的元素或者数据集不能再分割。

二分查找能够应用于任何类型的数据，只要能将这些元素按某种规则进行排序。这是一个简单的算法，但是你可能会怀疑，因为它依赖于一个有序集合，这使得它在处理那些频繁进行插入和删除操作的数据集时不太高效。这是因为，对于插入和删除操作来说，为了保证查找过程正常进行，必须保证数据集始终有序。相对于查找来说，维护一个有序数据集的代价更高。此外，元素必须存储在连续的空间中。因此，当待搜索的集合是相对静态的数据集时，此时使用二分查找法是最好的选择。

接口定义

1
2
int bisearch(void *sorted, void *target, int size, int esize,
	int (*compare)(const void *key1, const void *key2);

返回值　如果查找成功，返回目标的索引值；否则，返回-1。

描述　利用二分查找定位sorted（一个包含有序元素的数组）中的target。数组中的元素个数由size决定，每个元素的大小由esize决定。函数指针compare指向一个用户定义的比较函数。如果key1＞key2，函数返回1，如果key1=key2，函数返回0，如果key1＜key2，函数返回-1。

复杂度　O(lg n)，n为要查找数元素的个数。

分析

二分查找法实质上是不断地将有序数据集进行对半分割，并查检每个分区的中间元素。在以下介绍的实现方法中，有序数据集存放在sorted中，sorted是一块连续的存储空间。参数target是要查找的数据。

此实现过程的实施是通过变量left和right控制的一个循环来查找元素（其中left和right是正在进行查找的数据集的两个边界值）。首先，将left和right分别设置为0和size-1。在循环的每次迭代过程中，将middle设置为left和right之间区域的中间值。如果处于middle的元素比目标值小，将左索引值移动到middle后一个元素的位置上。即下一组要搜索的区域是当前数据集的上半区。如果处于middle的元素比目标值大，将右索引值移动到middle前一个元素的位置上。即下一组要搜索的区域是当前数据集的下半区。随着搜索的不断进行，left从左向右移，right从右向左移。一旦在middle处找到目标，查找将停止；如果目标没有找到，left和right将重合。下图显示了此过程。

二分查找的时间复杂度取决于查找过程中分区数可能的最大值。对于一个有n个元素的数据集来说，最多可以进行lg n次分区。对于二分查找，这表示最终可能在最坏情况下执行的检查次数：例如，当没有找到目标时。所以，二分查找的时间复杂度为O(lg n)。

实现

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static int compare_str(const void *key1, const void *key2) {
    
    int retval;
    if ((retval = strcmp((const char *)key1, (const char *)key2)) > 0)
        return 1;
    else if (retval < 0)
        return -1;
    else
        return 0;
    
}

int bisearch(void *sorted, const void *target, int size, int esize,
             int (*compare)(const void *key1, const void *key2)) {
    
    int left, middle, right;
    
    // Continue searching until the left and right indices cross
    left = 0;
    right = size - 1;
    
    while (left <= right) {
        middle = (left + right) / 2;
        switch (compare(((char *)sorted + (esize * middle)), target)) {   
            case -1:
                // Prepare to search to the right of the middle index
                left = middle + 1;
                break;
            case 1:
                // Prepare to search to the left of the middle index
                right = middle - 1;
                break;
            case 0:
                // Return the exact index where the data has been found
                return middle;       
        }
    }
    
    // Return that the data was not found
    return -1; 
}

int main(int argc, char **argv) {
    char barray[12][6] = {"bat", "cat", "dip", "hat", "hop",
        "mom", "mop", "tap", "tip", "top", "wax", "zoo"};    
    
    char *target = "tap";
    int retval = bisearch(barray, target, 12, 6, compare_str);
    if (retval < 0)
        fprintf(stdout, "Could not find %s\n", target);
    else
        fprintf(stdout, "Found %s at position %d\n", target, retval);
    
    return 0;
}

控制台输出

1
Found tap at position 7

排序和搜索算法的一些应用

次序统计

寻找集合中第i小的元素。一个简单的方法就是，一旦数据集排好序，取出第i个元素即可。

二分搜索

一种有效的查找方法，它依赖于有序数据集。二分搜索不断地将数据集从中分段，并检查每段中心位置的元素，从而最终找到目标元素。

目录列表

有组织地列出文件系统中的文件。通常来说，操作系统在显示目录列表之前会以某种方式将文件排序。

数据库系统

通常，大型系统包含海量的数据，并且这些数据要求快速地存取。一般情况下，在存储数据的数据库中使用一些高效而灵活的方法来查找数据是至关重要的。

拼写查检器

这是一种查检文本中单词拼写正确与否的程序。它通常以单词为单位在字典中进行对比校验。由于拼写检查器会频繁地在包含数以万计的文本中寻找单词并检查，因此它必须能够快速而高效地查询到可接受的单词。

电子表格

它是大多数企业的一个重要组成部分，企业用电子表格来管理库存和财务数据。当对表格中的数据分类和排序后，其数据才会更有意义。