10.1 快速排序

在大多数的情况下，快速排序的表现都非常好。

10.1.1 算法概述

和归并排序一样，都是使用了分而治之的思想。

分而治之的例子：

伪代码描述：

10.1.2 选主元

取头、中、尾的中位数。

伪代码描述：

C 语言实现：快速排序

直接调用库函数

/* 快速排序 - 直接调用库函数 */ #include <stdlib.h> /*---------------简单整数排序--------------------*/ int compare(const void *a, const void *b) { /* 比较两整数。非降序排列 */ return (*(int*)a - *(int*)b); } /* 调用接口 */ qsort(A, N, sizeof(int), compare); /*---------------简单整数排序--------------------*/ /*--------------- 一般情况下，对结构体Node中的某键值key排序 ---------------*/ struct Node { int key1, key2; } A[MAXN]; int compare2keys(const void *a, const void *b) { /* 比较两种键值：按key1非升序排列；如果key1相等，则按key2非降序排列 */ int k; if ( ((const struct Node*)a)->key1 < ((const struct Node*)b)->key1 ) k = 1; else if ( ((const struct Node*)a)->key1 > ((const struct Node*)b)->key1 ) k = -1; else { /* 如果key1相等 */ if ( ((const struct Node*)a)->key2 < ((const struct Node*)b)->key2 ) k = -1; else k = 1; } return k; } /* 调用接口 */ qsort(A, N, sizeof(struct Node), compare2keys); /*--------------- 一般情况下，对结构体Node中的某键值key排序 ---------------*/

自实现

/* 快速排序 */ ElementType Median3( ElementType A[], int Left, int Right ) { int Center = (Left+Right) / 2; if ( A[Left] > A[Center] ) Swap( &A[Left], &A[Center] ); if ( A[Left] > A[Right] ) Swap( &A[Left], &A[Right] ); if ( A[Center] > A[Right] ) Swap( &A[Center], &A[Right] ); /* 此时A[Left] <= A[Center] <= A[Right] */ Swap( &A[Center], &A[Right-1] ); /* 将基准Pivot藏到右边*/ /* 只需要考虑A[Left+1] … A[Right-2] */ return A[Right-1]; /* 返回基准Pivot */ } void Qsort( ElementType A[], int Left, int Right ) { /* 核心递归函数 */ int Pivot, Cutoff, Low, High; if ( Cutoff <= Right-Left ) { /* 如果序列元素充分多，进入快排 */ Pivot = Median3( A, Left, Right ); /* 选基准 */ Low = Left; High = Right-1; while (1) { /*将序列中比基准小的移到基准左边，大的移到右边*/ while ( A[++Low] < Pivot ) ; while ( A[--High] > Pivot ) ; if ( Low < High ) Swap( &A[Low], &A[High] ); else break; } Swap( &A[Low], &A[Right-1] ); /* 将基准换到正确的位置 */ Qsort( A, Left, Low-1 ); /* 递归解决左边 */ Qsort( A, Low+1, Right ); /* 递归解决右边 */ } else InsertionSort( A+Left, Right-Left+1 ); /* 元素太少，用简单排序 */ } void QuickSort( ElementType A[], int N ) { /* 统一接口 */ Qsort( A, 0, N-1 ); }

10.2 表排序

应用情况：待排元素是庞大的结构，比如是一本书，A不是整数，而是一个结构体。所以移动一本书的时候，时间耗费就会很大。因此表排序实际不是移动元素，而是移动指向待排元素的指针。

10.2.1 算法概述

间接排序：定义一个指针数组作为“表”。

10.2.2 物理排序

10.2.3 复杂度分析

10.3 基数排序

前面我们讲的那些排序算法，它们仅仅是基于元素大小来比较位置的。但是无论怎么样，它们都会有最坏的情况。那么有没有更快的线性时间的算法呢？（引出桶排序）

10.3.1 桶排序

10.3.2 基数排序（桶排序的升级版）

C 语言实现：基数排序 - 次位优先

/* 基数排序 - 次位优先 */ /* 假设元素最多有MaxDigit个关键字，基数全是同样的Radix */ #define MaxDigit 4 #define Radix 10 /* 桶元素结点 */ typedef struct Node *PtrToNode; struct Node { int key; PtrToNode next; }; /* 桶头结点 */ struct HeadNode { PtrToNode head, tail; }; typedef struct HeadNode Bucket[Radix]; int GetDigit ( int X, int D ) { /* 默认次位D=1, 主位D<=MaxDigit */ int d, i; for (i=1; i<=D; i++) { d = X % Radix; X /= Radix; } return d; } void LSDRadixSort( ElementType A[], int N ) { /* 基数排序 - 次位优先 */ int D, Di, i; Bucket B; PtrToNode tmp, p, List = NULL; for (i=0; i<Radix; i++) /* 初始化每个桶为空链表 */ B[i].head = B[i].tail = NULL; for (i=0; i<N; i++) { /* 将原始序列逆序存入初始链表List */ tmp = (PtrToNode)malloc(sizeof(struct Node)); tmp->key = A[i]; tmp->next = List; List = tmp; } /* 下面开始排序 */ for (D=1; D<=MaxDigit; D++) { /* 对数据的每一位循环处理 */ /* 下面是分配的过程 */ p = List; while (p) { Di = GetDigit(p->key, D); /* 获得当前元素的当前位数字 */ /* 从List中摘除 */ tmp = p; p = p->next; /* 插入B[Di]号桶尾 */ tmp->next = NULL; if (B[Di].head == NULL) B[Di].head = B[Di].tail = tmp; else { B[Di].tail->next = tmp; B[Di].tail = tmp; } } /* 下面是收集的过程 */ List = NULL; for (Di=Radix-1; Di>=0; Di--) { /* 将每个桶的元素顺序收集入List */ if (B[Di].head) { /* 如果桶不为空 */ /* 整桶插入List表头 */ B[Di].tail->next = List; List = B[Di].head; B[Di].head = B[Di].tail = NULL; /* 清空桶 */ } } } /* 将List倒入A[]并释放空间 */ for (i=0; i<N; i++) { tmp = List; List = List->next; A[i] = tmp->key; free(tmp); } }

C 语言实现：基数排序 - 主位优先

/* 基数排序 - 主位优先 */ /* 假设元素最多有MaxDigit个关键字，基数全是同样的Radix */ #define MaxDigit 4 #define Radix 10 /* 桶元素结点 */ typedef struct Node *PtrToNode; struct Node{ int key; PtrToNode next; }; /* 桶头结点 */ struct HeadNode { PtrToNode head, tail; }; typedef struct HeadNode Bucket[Radix]; int GetDigit ( int X, int D ) { /* 默认次位D=1, 主位D<=MaxDigit */ int d, i; for (i=1; i<=D; i++) { d = X%Radix; X /= Radix; } return d; } void MSD( ElementType A[], int L, int R, int D ) { /* 核心递归函数: 对A[L]...A[R]的第D位数进行排序 */ int Di, i, j; Bucket B; PtrToNode tmp, p, List = NULL; if (D==0) return; /* 递归终止条件 */ for (i=0; i<Radix; i++) /* 初始化每个桶为空链表 */ B[i].head = B[i].tail = NULL; for (i=L; i<=R; i++) { /* 将原始序列逆序存入初始链表List */ tmp = (PtrToNode)malloc(sizeof(struct Node)); tmp->key = A[i]; tmp->next = List; List = tmp; } /* 下面是分配的过程 */ p = List; while (p) { Di = GetDigit(p->key, D); /* 获得当前元素的当前位数字 */ /* 从List中摘除 */ tmp = p; p = p->next; /* 插入B[Di]号桶 */ if (B[Di].head == NULL) B[Di].tail = tmp; tmp->next = B[Di].head; B[Di].head = tmp; } /* 下面是收集的过程 */ i = j = L; /* i, j记录当前要处理的A[]的左右端下标 */ for (Di=0; Di<Radix; Di++) { /* 对于每个桶 */ if (B[Di].head) { /* 将非空的桶整桶倒入A[], 递归排序 */ p = B[Di].head; while (p) { tmp = p; p = p->next; A[j++] = tmp->key; free(tmp); } /* 递归对该桶数据排序, 位数减1 */ MSD(A, i, j-1, D-1); i = j; /* 为下一个桶对应的A[]左端 */ } } } void MSDRadixSort( ElementType A[], int N ) { /* 统一接口 */ MSD(A, 0, N-1, MaxDigit); }

10.3.3 多关键字的排序

10.4 排序算法的比较