排序（Sorting）是计算机程序设计中的一个重要而且常用的操作，它的功能是将一个数据元素
的任意序列，重新排列成一个按关键字有序的序列。下面介绍最为常用的几种排序算法，并进行简单
地比较分析以及C语言例程。这些C例程都是笔者在学习和工作中慢慢积累起来的，应该说还是有些用
处的。（刘爱贵 / Aiguille.LIU）
1、快速排序算法
快速排序是目前公认的最好排序算法，是一种基于分治技术的重要排序算法，算法时间复杂度为
O(nlog2n)。
/* quicksort.c */
#define MAXSIZE 20
#define LENGTH 11
typedef int SqList;
SqList L[LENGTH]={-1,4,7,9,1,5,3,2,6,8,0};
/*分区函数*/
int Partition(SqList *L,int low,int high)
{
int pivotkey,temp;
L[0]=L[low];
pivotkey=L[low];
while(low<high)
{
while(low<high&&L[high]>=pivotkey)--high;
L[low]=L[high];
while(low<high&&L[low]<=pivotkey)++low;
L[high]=L[low];
}
L[low]=L[0];
return low;
}
void QSort(SqList *L,int low,int high)
{
int pivotkey;
if(low<high)
{
pivotkey=Partition(L,low,high);
QSort(L,low,pivotkey-1);
QSort(L,pivotkey+1,high);
}
}
void QuickSort(SqList *L)
{
QSort(L,1,LENGTH);
}
void Print(SqList *L)
{
int i;
for(i=1;i<LENGTH;++i)
printf("%4d",L[i]);
printf("\n");
}
main()
{
Print(L);
QuickSort(L);
Print(L);
}
2、堆排序算法
堆排序以堆数据结构为基石，是一种高效的排序算法。因为有堆这种数据结构以及它操作的高效
实现的特征，使得找到数列中最大的数字这样的操作只需要O(1)
的时间复杂度，维护需要logn的时间复杂度。堆排序的平均时间复杂度为O(nlogn)，比快速排序算
法稍差，但堆排序是在位的，不需要额外的存储空间。
/* heapsort.c */
#define LENGTH 9
typedef int HeapType;
int H[LENGTH]={-1,49,38,65,97,76,13,27,49};
void HeapAdjust(HeapType *H,int s,int m)
{
int rc,j;
rc=H[s];
for(j=s*2;j<=m;j*=2)
{
if((j<m)&&(H[j]>H[j+1]))++j;
if(!(rc>H[j]))break;
H[s]=H[j];
s=j;
}
H[s]=rc;
}
void HeapSort(HeapType *H)
{
int i,temp;
for(i=LENGTH/2;i>0;--i)
HeapAdjust(H,i,LENGTH);
for(i=LENGTH;i>1;--i)
{
temp=H[1];
H[1]=H[i];
H[i]=temp;
HeapAdjust(H,1,i-1);
}
}
void Print(HeapType *H)
{
int i;
for(i=1;i<LENGTH;++i)
printf("%8d",H[i]);
printf("\n");
}
main()
{
Print(H);
HeapSort(H);
Print(H);
getch();
clrscr();
}
3、双向冒泡排序算法
双向冒泡排序算法是对单向冒泡排序算法的改进，它是蛮力法在排序问题上的一个应用。直观上
来看，双向冒泡法先让重的气泡沉到底下，然后让轻的气泡浮上来，然后再让较大气泡沉下去，让较
轻气泡浮上来，依次反复，直到排序结束。单向冒泡法时间复杂度为O(n*n)，双向冒泡法略优，但
时间复杂度也为O (n*n)。
/* bi_bobblesort.c */
int data[10]={4,8,22,79,-2,0,100,13,12,-100};
void Bubble_Sort2(int a[],int n);
void Print(int a[],int n);
main()
{
Print(data,10);
Bubble_Sort2(data,10);
Print(data,10);
}
void Print(int a[],int n)
{
int i;
for(i=0;i<n;++i)
printf("%4d",a[i]);
printf("\n");
}
void Bubble_Sort2(int a[ ],int n)
{
int low=0,high=n-1;
int change=1;
int i,temp;
while(low<high&&change)
{
change=0;
for(i=low;i<high;i++)
if(a[i]>a[i+1])
{
/* a[i]<->a[i+1];*/
temp=a[i];
a[i]=a[i+1];
a[i+1]=temp;
change=1;
}
high--;
for(i=high;i>low;i--)
if(a[i]<a[i-1])
{
/* a[i]<->a[i-1]; */
temp=a[i];
a[i]=a[i-1];
a[i-1]=temp;
change=1;
}
low++;
}//while
}//Bubble_Sort2
4、希尔排序算法
希尔排序又称缩小增量排序，属于插入排序类方法，但在时间效率上比其他插入排序方法有较大
改进。它的基本思想是：先将整个待排序记录序列分割为若干子序列分别进行直接插入排序，待整个
序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。C语言实现及例子如下：
/* shellsort.c */
void shell_insert(int *l, int dk, int length)
{
int i, j, sentinel;
for (i=dk; i<length; ++i) {
if (l[i] < l[i-dk]) {
sentinel = l[i];
for (j=i-dk; j>=0 && sentinel<l[j]; j-=dk)
l[j+dk] = l[j];
l[j+dk] = sentinel;
}
}
}
void shell_sort(int *l, int dlta[], int t, int length)
{
int k;
for (k=0; k<t; ++k) {
shell_insert(l, dlta[k], length);
}
}
int main(int argc, char *argv[])
{
int a[10] = {49, 38, 65, 97, 76, 13, 27, 49, 55, 4};
int dlta[3] = {5, 3, 1};
shell_sort(a, dlta, 4, 10);
int i;
for (i=0; i<10; ++i)
printf("%4d", a[i]);
printf("\n");
}
5、计数排序算法
计数排序的基本思想是，对于每一个元素X，确定出小于X的元素个数，据此直接确定X的输出位
置。计数排序是稳定的排序算法，时间复杂度为O(n+k)，需要O(n)辅助存储空间。C语言实现及例子
如下：
/* countsort.c */
print_array(int *arr, int len)
{
int i;
for (i=0; i<len; i++)
printf("%4d", arr[i]);
printf("\n");
}
int main()
{
int i,j, length, k;
int A[8] = {2,5,3,0,2,3,0,3};
int B[8] = {0,0,0,0,0,0,0,0};
int C[6] = {0,0,0,0,0,0};
length = 8;
k = 6;
for (i=0; i<k; i++)
C[i] = 0;
for (j=0; j<length; j++)
C[A[j]]++;
for (i=1; i<k; i++)
C[i] = C[i] + C[i-1];
print_array(C, 6);
for (j=length-1; j>=0; j--) {
B[C[A[j]] - 1] = A[j];
C[A[j]]--;
}
print_array(A, length);
print_array(B, length);
}
6、基数排序算法
基数排序的基本思想是：借助“分配”和“收集”对单逻辑关键字进行排序的一种方法，时间复
杂度为O(d * (n + k))，空间复杂度为O(n +
rd)。借助d次计数排序可以实现基数排序，C语言实现和例子如下：
/* radixsort.c */
print_array(int *arr, int len)
{
int i;
for (i=0; i<len; i++)
printf("%4d", arr[i]);
printf("\n");
}
int radix(int x, int d)
{
int i, y = 1;
for (i=1; i<d; i++)
y *= 10;
y = (x/y) % 10;
return y;
}
int main()
{
int i, j, l, length, k, d;
int A[8] = {329,457,657,839,436,720,355,345};
int B[8] = {0,0,0,0,0,0,0,0};
int C[10] = {0,0,0,0,0,0,0,0,0,0};
length = 8;
k = 10;
d = 3;
print_array(A, length);
for (l=1; l<=d; l++) {
for (i=0; i<k; i++)
C[i] = 0;
for (j=0; j<length; j++)
C[radix(A[j],l)]++;
for (i=1; i<k; i++)
C[i] = C[i] + C[i-1];
for (j=length-1; j>=0; j--) {
B[C[radix(A[j],l)] - 1] = A[j];
C[radix(A[j],l)]--;
}
for (i=0; i<length; i++)
A[i] = B[i];
print_array(B, length);
}
}
7、外部排序－K路平衡归并排序算法
当输入数据大小大于内存时，需要对数据进行分段排序，然后进行归并，最终得到整个有序序列
。K路平衡归并排序算法，对K个归并有序数据段，利用“败者树”进行归并排序。其思想和体育比赛
类似（淘汰制，一个一个淘汰），败者淘汰，胜者参加下一轮比赛，最终得到冠军和排名序列。下面
给出了一个5路平衡归并排序的C语言实现的例子。
/* k_mergesort.c */
#define k 5
#define LEN 10
#define MAXKEY 1000
#define MINKEY -1000
typedef int LoserTree;
typedef int External;
int a[k][LEN]= {{5,15,25,35,45,55,65,75,85,95},
{7,17,27,37,47,57,67,77,87,97},
{6,16,26,36,46,56,66,76,86,96},
{3,13,23,33,43,53,63,73,83,93},
{4,14,24,34,44,54,64,74,84,94}
};
void input(External *b, int i)
{
int x = MAXKEY;
int j;
for (j=0; j<LEN; ++j) {
if(a[i][j]<MAXKEY){
x = a[i][j];
a[i][j] = MAXKEY;
break;
}
}
b[i] = x;
}
void output(int x)
{
printf("%4d", x);
}
void adjust(LoserTree *ls, External *b, int s)
{
int t = (s+k)/2;
int tmp;
while (t > 0) {
if (b[s] > b[ls[t]]) {
tmp = s;
s = ls[t];
ls[t] = tmp;
}
t = t/2;
}
ls[0] = s;
}
void create_losertree(LoserTree *ls, External *b)
{
int i;
b[k] = MINKEY;
for (i=0; i<k; ++i)
ls[i] = k;
for (i=k-1; i>=0; --i)
adjust(ls, b, i);
}
void k_merge(LoserTree *ls, External *b)
{
int i, q;
for (i=0; i<k; ++i)
input(b, i);
create_losertree(ls, b);
while (b[ls[0]] != MAXKEY) {
q = ls[0];
output(b[q]);
input(b, q);
adjust(ls, b, q);
}
}
int main(int argc, char *argv[])
{
int ls[k+1], b[k+1];
k_merge(ls, b);
printf("\n");
return 0;
}