《算法精解:C语言描述》笔记(排序)

第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数据结构，包含一个航空公司的航班时刻表，排序用那种算法
快速排序。一般情况下最好的。

作者还在该章的末尾讲了下二分查找，更多的排序与查找算法就没有了，略失望，感觉少了点。