第12章 排序和搜索
通常有两种排序方法：升序排列和降序排列
排序算法分为两大类：比较排序和线性时间排序
比较排序依赖于比较和交换，线性时间排序依赖于数据集合中的某些特征。
1、插入排序
2、快速排序
3、归并排序
4、计数排序
5、基数排序
1、插入排序
每次从无序数据集中取出一个元素，扫描已排好序的数据集，并将它插入有序集合合适的位置上。
但并不需要额外的存储空间。
处理大型数据集时并不高效。在决定将元素插入之前，需要将被插入元素和有序数据集中其他元素进行比较，会随着数据集的增大而增加额外的开销。
优点是只需要对有序数据集最多进行一次遍历，而不需要完整地运行算法。在增量排序中非常高效。
复杂度 O(n²)
.c文件：
#include "issort.h"
#include <stdlib.h>
#include <string.h>
/*
*插入排序
*参数：data:待排序的数组
* size:数组元素的个数
* esize:每个元素的大小
* compare:函数指针，比较函数大小的函数
*返回值：成功返回0，否则-1，data包含已排序的元素
*/
int issort(void *data,int size,int esize,int (*compare)(const void *key1,const void *key2) )
{
char *a = data;
void *key;
int i;
if ((key = (char *)malloc(esize)) == NULL)
{
return -1;
}
for (int 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;
}
自定义比较函数，在其他排序中也能用到
int compare(const void *key1,const void *key2){
if (*(int *)key1 > *(int *)key2) {
return 1;
}
else if (*(int *)key1 == *(int *)key2){
return 0;
}
else{
return -1;
}
}
调用
#include <stdio.h>
#include "issort.h"
int main(int argc, const char * argv[]) {
int a[10]={0,2,1,3,5,7,9,8,6,4};
int result = issort(a, 10, sizeof(int), compare);
for (int i=0; i<10; i++)
{
printf("%d\n",a[i]);
}
return 0;
}
2、快速排序
不断地将无序元素集递归分割，直到所有的分区都只包含单个元素。
一种分治排序算法，比较排序的一种。也不需要额外的存储空间。
处理中到大型数据集的一个比较好的选择，解决一般问题的最佳算法
复杂度最坏为O(n²) 平均为O(nlgn)
分：设定一个分割值将数据分为两部分，这点很关键，影响到性能。
治：分别在两部分用递归继续调用
合：对分割部分排序直至完成
.c文件：
#include "qksort.h"
#include <stdlib.h>
#include <string.h>
#include "issort.h"
//分割数据
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];
//初始化
if ((pval = malloc(esize)) == NULL) {
return -1;
}
if ((temp = malloc(esize)) == NULL) {
free(pval);
return -1;
}
//中位数法找出分割值
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);
memcpy(pval, &a[r[1]*esize], esize);
//根据分割值分成两个区
i--;
k++;
while (1) {
//移动左边直到找到一个元素在错误的分区
do {
k--;
} while (compare(&a[k * esize],pval) > 0);
//移动右边直到找到一个元素在错误的分区
do {
i++;
} while (compare(&a[i * esize],pval) < 0);
if (i >= k) {
//一旦i和k重合，那么左边的元素将小于等于它，右边的元素将大于等于它，停止分区
break;
}else{
//交换元素
memcpy(temp, &a[i * esize], esize);
memcpy(&a[i * esize], &a[k * esize], esize);
memcpy(&a[k * esize], temp, esize);
}
}
free(pval);
free(temp);
//返回划分两个区的位置
return k;
}
int qksort(void *data,int size,int esize,int i,int k,int(*compare)(const void *key1,const void *key2))
{
int j;
//可以进一步划分时停止递归
while (i<k){
//确定分区的元素
if ((j = partition(data, esize, i, k, compare)) < 0) {
return -1;
}
//递归左边的分区
if (qksort(data, size, esize, i, j, compare) < 0) {
return -1;
}
//迭代和排序右边的分区
i = j+1;
}
return 0;
}
3、归并排序
将一个无序元素集分割成许多个只包含一个元素的集，然后不断地将这些小集合并，直到成为一个新的大有序数据集。
一种分治排序算法，比较排序的一种。但是需要额外的存储空间。
与快速排序最大的不同在于它的归并过程。将两个有序的数据集合并成一个有序的数据集，并且合并过程不能在无序数据集本身中进行，要有两倍于无序数据集的空间来运行算法。
对于海量数据处理还是很有价值的，因为能够按预期将数据集分开，成为更加可管理的数据，然后合并，并不需要一次存储所有的数据。
复杂度平均为O(nlgn)
//归并排序
#include "mgsort.h"
//将两个有序集合合并成一个有序集合
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;
if ((m = (char *)malloc(esize *((k-i)+1))) == NULL){
return -1;
}
//当两个部分都有元素合并时继续
while (ipos <= j || jpos <= k){
if (ipos > j){
//左部分没有元素要合并了
while (jpos <= k) {
memcpy(&m[mpos * esize], &a[jpos * esize], esize);
jpos++;
mpos++;
}
continue;
}
else if (jpos > k){
//右部分没有元素要合并了
while (ipos <= j) {
memcpy(&m[mpos * esize], &a[ipos * esize], esize);
ipos++;
mpos++;
}
continue;
}
//追加下一个元素到合并元素
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++;
}
}
memcpy(&a[i * esize], m, esize * ((k-i)+1));
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;
if (i < k) {
//确定分割点
j = (int)((i+k-1)/2);
//递归排序
if (mgsort(data, size, esize, i, j, compare) < 0) {
return -1;
}
if (mgsort(data, size, esize, j+1, k, compare) < 0) {
return -1;
}
//合并
if (merge(data, esize, i, j, k, compare) < 0) {
return -1;
}
}
return 0;
}
4、计数排序
计算一个集合中元素出现的次数来确定集合如何排列。
一种线性排序。
只能用于整型或者那些可以用整型来表示的数据集合，还需要知道集合中最大整数的值用来分配空间。
优点是速度快，稳定。
时间复杂度为O(n+k) k为data中最大整数加1
//计数排序
#include "ctsort.h"
#include <stdlib.h>
#include <string.h>
int ctsort(int *data,int size,int k)
{
int *counts,*temp;
int i,j;
if ((counts = (int *)malloc(k * sizeof(int))) == NULL) {
return -1;
}
if ((temp = (int *)malloc(size * sizeof(int))) == NULL) {
return -1;
}
for (i = 0; i < k; i++) {
counts[i] = 0;
}
for (j = 0; j < size; j++) {
counts[data[j]] = counts[data[j]] + 1;
}
for (i = 1; i < k; i++) {
counts[i] = counts[i] + counts[i-1];
}
for (j = size-1; j>=0; j--) {
temp[counts[data[j]] - 1] = data[j];
counts[data[j]] = counts[data[j]] - 1;
}
memcpy(data, temp, size * sizeof(int));
free(counts);
free(temp);
return 0;
}
5、基数排序
将数据按位分开，并从数据的最低有效位到最高有效位进行比较，依次排序，（从个位数排序，然后排序十位数...）
一种线性排序
不局限于整型，只要能把元素分割成整型即可。
时间复杂度为O(pn+pk) k为基数（10进制），p为位的个数（100就是3位）
//基数排序
#include "rxsort.h"
#include <stdlib.h>
#include <string.h>
#include <math.h>
int rxsort(int *data,int size,int p,int k)
{
int *counts,*temp;
int index,pval,i,j,n;
if ((counts = (int *)malloc(k * sizeof(int))) == NULL) {
return -1;
}
if ((temp = (int *)malloc(size * sizeof(int))) == NULL) {
return -1;
}
for (n=0; n<p; n++) {
for (i=0; i<k; i++) {
counts[i] = 0;
}
pval = (int)pow((double)k, (double)n);
for (j = 0; j < size; j++) {
index = (int)(data[j] / pval) % k;
counts[index]=counts[index] + 1;
}
for (i = 1; i < k; i++) {
counts[i] = counts[i] + counts[i-1];
}
for (j = size-1; j >= 0; j--) {
index = (int)(data[j] / pval) % k;
temp[counts[index]-1] = data[j];
counts[index] = counts[index] - 1;
}
memcpy(data, temp, size * sizeof(int));
}
free(counts);
free(temp);
return 0;
}
问与答
1、假设有一个全球性投资公司，需要将其客户按照名字排序，由于数据量巨大，不可能一次将所有数据读入内存，排序应该选择哪种算法？
归并排序。O(nlgn)，还以可预见的方式合并有序分区和数据，让我们很容易管理数据。
2、在一个用户界面中维护一个有序元素的列表，相对较小，排序用哪种算法？
插入排序。 O(n)
3、在生物研究中，用1000w个80个字符宽的字符串来表示DNA的信息，排序用哪种算法？
基数排序。性能取决于基值的选择和空间的限制。可以把
4、假设有1w个c数据结构，包含一个航空公司的航班时刻表，排序用那种算法
快速排序。一般情况下最好的。
作者还在该章的末尾讲了下二分查找，更多的排序与查找算法就没有了，略失望，感觉少了点。
网友评论