希尔排序是一种插入排序法，它出自D.L.Shell，因此而得名。Shell排序又称作缩小增量排序。

希尔排序基本思想

算法步骤

算法分析(增量序列的选择 Shell排序的时间性能优于直接插入排序 稳定性 算法讨论)

shell排序算法总结(Latest Snippet Version: 1.01 Incerpj-Sedgewick 算法，1985 年发表。 Sedgewick 算法，1986 年发表。 Tokuda(徳田尚之)算法。发表于 1992 年。 Lazarus-Frank 算法，1960 年发表。 Hibbard 算法，1963 年发表。 Papernov-Stasevich 算法, 1965年发表 Pratt 算法，1971 年发表 Sedgewick 算法, 1982 年发表 Latest Snippet Version: 1.0 改进的冒泡排序算法 堆排序算法 两路归并排序算法 两路归并过程 快速排序算法 基数排序算法)

希尔排序基本思想

先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插人排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。

该方法实质上是一种分组插入方法。

算法步骤

Step1 将n个元素个数列分为5个小组，在每个小组内按直接插入法排序；

step2 在第i步，分组个数取 di+1 =（di +1）/2 {9，5，3，2，1}；相临两组之间的对应元素进行比较，如果ai>aj，则交换它们的位置；

Step3 当dK = 1的循环过程完成后，排序过程结束。

希尔排序举例：设有字符数列"f d a c b e"，执行Shell排序：

算法分析

增量序列的选择

Shell排序的执行时间依赖于增量序列。

好的增量序列的共同特征：

① 最后一个增量必须为1；

② 应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。

有人通过大量的实验，给出了目前较好的结果：当n较大时，比较和移动的次数约在n到1.6n之间。

Shell排序的时间性能优于直接插入排序

希尔排序的时间性能优于直接插入排序的原因：

①当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。

②当n值较小时，n和n的差别也较小，即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度0(n^2)差别不大。

③在希尔排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量di逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经按di-1作为距离排过序，使文件较接近于有序状态，所以新的一趟排序过程也较快。

因此，希尔排序在效率上较直接插人排序有较大的改进。

稳定性

希尔排序是不稳定的。参见上述实例，该例中两个相同关键字49在排序前后的相对次序发生了变化。

算法讨论

Shell排序算法的时间复杂度分析比较复杂，实际所需的时间取决于各次排序时增量的个数和增量的取值。研究证明，若增量的取值比较合理，Shell排序算法的时间复杂度约为O（n（ldn）2）。由于Shell排序算法是按增量分组进行的排序，所以Shell排序算法是一种不稳定的排序算法。

shell排序算法总结

Latest Snippet Version: 1.01

/*

* Shell 排序算法在 1959 年由 D. Shell 发明。

* 也称为递减增量排序算法，各种实现在如何进行递减上有所不同。

* 不稳定，不需要辅助空间。

*/

/*

* Gonnet 算法，发表于 1991 年。

*/

int shellsortGo(int p[],int n)

{

int op=0;

int h,i,j,temp;

for(h=n; h>1; ) {

h=(h<5)?1:(h*5-1)/11;

for (i=h; i<n; i++) {

temp=p[i];

for (j=i-h; j>=0 && p[j]>temp; j-=h) {

p[j+h]=p[j];

op++;

}

p[j+h]=temp;

op++;

}

}

return op;

}

Incerpj-Sedgewick 算法，1985 年发表。

int shellsortIS(int p[],int n)

{

int op=0;

int h,i,j,t,temp;

int incs[16] = { /* a1=3,a2=7,a3=16,a4=41,a5=101 */

1391376, /* a1*a2*a3*a4*a5 */

463792, /* a2*a3*a4*a5 */

198768, /* a1*a3*a4*a5 */

86961, /* a1*a2*a4*a5 */

33936, /* a1*a2*a3*a5 */

13776, /* a1*a2*a3*a4 */

4592, /* a2*a3*a4 */

1968, /* a1*a3*a4 */

861, /* a1*a2*a4 */

336, /* a1*a2*a3 */

112, /* a2*a3 */

48, /* a1*a3 */

21, /* a1*a2 */

7, /* a2 */

3, /* a1 */

1

};

for(t=0; t<16; t++) {

h=incs[t];

for (i=h; i<n; i++) {

temp=p[i];

for (j=i-h; j>=0 && p[j]>temp; j-=h) {

p[j+h]=p[j];

op++;

}

p[j+h]=temp;

op++;

}

}

return op;

}

Sedgewick 算法，1986 年发表。

op++;

}

p[j+h]=temp;

op++;

}

}

return op;

}

Tokuda(徳田尚之)算法。发表于 1992 年。

h=incs[t];

if (h>n*4/9)

continue;

for (i=h; i<n; i++) {

temp=p[i];

for (j=i-h; j>=0 && p[j]>temp; j-=h) {

p[j+h]=p[j];

op++;

}

p[j+h]=temp;

op++;

}

}

return op;

}

/*******************************************/

/* 下面几个算法有研究价值 */

/*******************************************/

/*

* D. Shell 最初的算法。

*/

int shellsortSh(int p[],int n)

{

int op=0;

int h,i,j,temp;

for(h=n/2; h>0; h=h/2) {

for (i=h; i<n; i++) {

temp=p[i];

for (j=i-h; j>=0 && p[j]>temp; j-=h) {

p[j+h]=p[j];

op++;

}

p[j+h]=temp;

op++;

}

}

return op;

}

Lazarus-Frank 算法，1960 年发表。

/*

* 原为在必要时加 1 使所有增量都为奇数, 现修正为减 1。

*/

int shellsortLF(int p[],int n)

{

int op=0;

int h,i,j,temp;

for(h=n/2; h>0; h=h/2) {

if (h%2==0)

h--;

for (i=h; i<n; i++) {

temp=p[i];

for (j=i-h; j>=0 && p[j]>temp; j-=h) {

p[j+h]=p[j];

op++;

}

p[j+h]=temp;

op++;

}

}

return op;

}

/*--------------------------------------*/

/*

Hibbard 算法，1963 年发表。

* 1965 年 Papernov-Stasevich 给出了数学证明。

*/

int shellsortHb(int p[],int n)

{

int op=0;

int h,i,j,temp;

for(h=1; h<=n/4; h=h*2+1);

for( ; h>0; h=(h-1)/2) {

/* h = 1, 3, 7, 15, 31 ... 2^i-1 */

for (i=h; i<n; i++) {

temp=p[i];

for (j=i-h; j>=0 && p[j]>temp; j-=h) {

p[j+h]=p[j];

op++;

}

p[j+h]=temp;

op++;

}

}

return op;

}

/*

*

Papernov-Stasevich 算法, 1965年发表

*/

int shellsortPS(int p[],int n)

{

int op=0;

int h,i,j,temp;

for(h=2; h<=n/4; h=h*2-1);

for( ; h>1; ) {

h=(h==3)?1:(h+1)/2;

/* h = 1, 3, 5, 9, 17, 33 ... 2^i+1 */

for (i=h; i<n; i++) {

temp=p[i];

for (j=i-h; j>=0 && p[j]>temp; j-=h) {

p[j+h]=p[j];

op++;

}

p[j+h]=temp;

op++;

}

}

return op;

}

/*

* Knuth 算法，他建议在 n<1000 时使用。

*/

int shellsortKn(int p[],int n)

{

int op=0;

int h,i,j,temp;

for(h=1; h<=n/9; h=h*3+1);

for( ; h>0; h=h/3) {

/* h = 1, 4, 13, 40, 121, 364... 3*h+1 */

for (i=h; i<n; i++) {

temp=p[i];

for (j=i-h; j>=0 && p[j]>temp; j-=h) {

p[j+h]=p[j];

op++;

}

p[j+h]=temp;

op++;

}

}

return op;

}

/*--------------------------------------*/

/*

*

Pratt 算法，1971 年发表

* 原为 h=2^p*3^q 现修正为 7^p*8^q。

*/

int shellsortPr(int p[],int n)

{

int op=0;

int h,i,j,t,temp;

int incs[28] = {

262144, 229376, 200704, 175616, 153664, 134456,

117649, 32768, 28672, 25088, 21952, 19208, 16807,

4096, 3584, 3136, 2744, 2401, 512, 448, 392, 343,

64, 56, 49, 8, 7, 1

};

for(t=0; t<28; t++) {

h=incs[t];

for (i=h; i<n; i++) {

temp=p[i];

for (j=i-h; j>=0 && p[j]>temp; j-=h) {

p[j+h]=p[j];

op++;

}

p[j+h]=temp;

op++;

}

}

return op;

}

/*

*

Sedgewick 算法, 1982 年发表

*/

int shellsortSe82(int p[],int n)

{

int op=0;

int h,i,j,t,temp;

for (t=1; t*t<=n/4; t+=t);

for (h=n/4; t>0; t/=2, h=t*t-(3*t)/2+1) {

/* h = 1, 8, 23, 77, 281, 1073, 4193, 16577,

* 65921, 262913, 1050113... 4^i+3*2^(i-1)+1 */

for (i=h; i<n; i++) {

temp=p[i];

for (j=i-h; j>=0 && p[j]>temp; j-=h) {

p[j+h]=p[j];

op++;

}

p[j+h]=temp;

op++;

}

}

return op;

}

两分法查找例程

==============================================

Latest Snippet Version: 1.0

int binarysearch(int p[],int n,

int value, /* 查找值 */

int *m) /* 返回的是第一个大于等于查找值的元素

* 位置和小于查找值的元素个数 */

{

int op=0;

int i=0; /* 头指针前面的元素小于查找值 */

int j=n-1; /* 尾指针和它后面的元素大于等于查找值 */

int k; /* 中间指针 */

if (n==0) { /* 空列表 */

*m=0;

return 0;

}

while (i<j) {

k=(i+j)/2;

if (p[k]<value)

i=k+1;

else

j=k;

op++;

}

/* 头尾指针指向同一个位置 */

if (p>=value) /* 此位置上元素大于等于查找值 */

*m=i;

else /* 全部元素都小于查找值 */

*m=n;

op++;

return op;

}

简单的排序算法，冒泡，选择，插入，梳子

==============================================

Latest Snippet Version: 1.01

int selectsort(int p[], int n);

int insertsort(int p[],int n);

int bubblesort(int p[],int n);

int combsort(int p[], int n);

int bubblesort(int p[], int n)

{

int op=0;

int i, j;

int temp;

int flag=1;

for (j=n-1; flag>0 && j>0; j--) {

flag=0;

for (i=j; i>0; i--) {

if (p>p) {

temp=p;

p=p;

p=temp;

flag=1;

}

op++;

}

}

return op;

}

int selectsort(int p[], int n)

{

int op=0;

int i, j, max;

int temp;

for (j=n-1; j>0; j--) {

max=j;

temp=p[j];

for(i=j-1; i>=0; i--) {

if (p>temp) {

max=i;

temp=p;

}

op++;

}

p[max]=p[j];

p[j]=temp;

op++;

}

return op;

}

int insertsort(int p[],int n)

{

int op=0;

int i,j,temp;

for (j=1; j<n; j++) {

temp=p[j];

for(i=j-1; i>=0 && p>temp; i--) {

p=p;

op++;

}

p=temp;

op++;

}

return op;

}

改进的冒泡排序算法

/*

* 改进的冒泡排序算法，性能接近堆排序。

* 在 1991 年由 S. Lacey 和 R. Box 发明。

* 据说在特定的重复性输入下有可能衰退成冒泡排序。

*/

int combsort(int p[], int n)

{

int op=0;

int i;

int temp;

int gap=n;

int flag=1;

while (gap>1 || flag!=0) {

flag=0;

gap=(gap==9||gap==10)?11:gap*10/13;

if (gap==0)

gap=1;

for (i=n-1; i-gap>=0; i--) {

if (p>p) {

temp=p;

p=p;

p=temp;

flag=1;

}

op++;

}

}

return op;

}

堆排序算法

====================================

Latest Snippet Version: 1.02

int heapsort(int p[],int n);

/*

* 堆排序算法在 1964 年由 J. Williams 发明。

* 不稳定，不需要辅助空间。

*/

int siftup(int p[],int i,int n);

int insert(int p[], int n);

int heapsort(int p[],int n)

{

int op=0;

int i,temp;

/* 自底向上建造堆 */

for (i=n/2-1; i>=0; i--)

op+=siftup(p,i,n);

/* 自顶向下建造堆 */

/* for (i=2;i<=n;i++)

* op+=insert(p,i); */

/* 交换堆顶与堆底的元素，筛选操作把目前处在堆顶的元素

* 插入到变小了堆中，同时从堆中选出新的最大元素到堆顶 */

for (i=n-1; i>0; i--) {

temp=p[0];

p[0]=p;

p=temp;

op++;

op+=siftup(p,0,i);

}

return op;

}

/*

* 筛选例程

*/

int siftup(int p[],

int i, /* 堆顶的位置 */

int n) /* 列表的长度 */

{

int op=0;

int j,temp;

temp=p; /* 要插入的元素已经在根节点位置上，保存它的值 */

/* 要比较的节点位置是当前根节点的左子节，并且它在列表范围内 */

while ((j=i*2+1)<n) {

op+=2;

/* 要比较的左子节点有对应的右子节点，左子节点小于右子节点 */

if (j+1<n && p[j]<p[j+1])

j++; /* 要比较的节点位置是当前根节点的右子节点 */

if (p[j]<=temp) /* 当前做比较的子节点的值小于等于要插入的值 */

break; /* 停止下移 */

p=p[j]; /* 做比较的子节点的值上移到当前根节点 */

i=j; /* 当前根节点下移到做比较的子节点的位置上 */

}

p=temp; /* 插入要插入的值 */

op++;

return op;

}

/*

* 插入例程，把列表的最后一个元素插入到它前面的堆中

*/

int insert(int p[], int n)

{

int op=0;

int i=n-1,j;

int temp;

temp=p;

for (; i>0; i=j) {

op++;

j=(i-1)/2;

if (p[j]>=temp)

break;

p=p[j];

}

p=temp;

op++;

return op;

}

就地归并排序算法的未做优化实现

==========================================

Latest Snippet Version: 1.03

int imergesort(int p[], int n);

extern int insertsort(int p[], int n);

extern int binarysearch(int p[],int n, int v, int *m);

static int exchange(int src[],int dest[],int n);

static int swapMergeSort(int p[], int swap[], int n, int flag);

static int swapMerge(int work[], int swap[], int m, int n,int flag);

static int replaceMerge(int p[],int m, int q, int n);

#define IN 1

#define OUT 0

/*

* in-place 归并排序算法的始作俑者和优化实现请参见：

* 不稳定，不需要辅助空间。余之实现意图说明标志性的方法而未做任何优化。

*/

int imergesort(int p[], int n)

{

int op=0;

int i;

int k=n; /* 在头部的未排序的元素数目 */

int m=0; /* 在尾部的已排序的元素数目 */

i=k/2;

/* 用列表的前半部分做交换空间，

* 对列表的后半部分做归并排序。*/

op+=swapMergeSort(&p[n-i],p,i,IN);

m+=i;

k-=i;

while(k>4) {

i=k/2;

/* 用未排序子列表的后半部分做交换空间，

* 对未排序子列表的前半部分做归并排序*/

op+=swapMergeSort(p,&p,i,IN);

/* 把新排序出来的子列表与早先排序出来

* 的子列表做不对称归并，它们之间的未

* 排序空间被置换到列表头部。*/

op+=replaceMerge(p,i,n-m,m);

/* 列表的头部是未排序的，而尾部是已排序的 */

m+=i;

k-=i;

}

/* 最后的剩下的几个元素直接插入到已排序的列表中 */

op+=insertsort(p,n);

return op; /* 返回操作数 */

}

/*

* 前提：0 -> m-1 和 q -> q+n-1 是两个有序列表，

* 中间从 m -> q-1 是大小为 q-m 的未排序的空间。

* 要求 q>=2*m，即中间的未排序空间大于等于左面的列表。

* 结果：归并出从 q-m 开始的大小是 m+n 的有序列表，

* 0 到 q-m-1 是被置换出来的大小是 q-m 的未排序的空间。

*/

static int replaceMerge(int p[], /* 要归并的列表即左列表的头位置 */

int m, /* 左列表的长度 */

int q, /* 右列表的头位置 */

int n) /* 右列表的长度 */

{

int op=0;

int i=0,j=0,t=0;

int w, r;

int *left=p;

int *right=&p[q];

int *dest=&p[q-m];

while (i<m && j<n) {

if ((w=(n-j)/(m-i))==0)

w=1;

/* 把选择的左列表元素与右列表的 w 个元素中的最大值做比较 */

if (left>=right[j+w-1]) {

/* 选择的左列表元素大于等于右列表的 m 个元素。*/

op+=exchange(&right[j],&dest[t],w);

t+=w;

j+=w;

} else {

/* 以选择的左列表元素作为查找值在右列表的 w 个元素中找到小于

* 查找值的元素个数 */

op+=binarysearch(&right[j],w,left,&r);

if (r!=0) {

op+=exchange(&right[j],&dest[t],r);

t+=r;

j+=r;

}

op+=exchange(&left,&dest[t++],1);

}

}

if (i<m)

op+=exchange(&left,&dest[t],m-i);

return op;

}

/*

* 交换过程，操作数量是 2*n+1 而不是 3*n，但不保持目标列表的

* 原有次序，故只能用在有序列表与无序列表之间的交换。

*/

static int exchange(int src[],int dest[],int n)

{

int i,temp;

if (n==0)

return 0;

temp=dest[0];

for(i=0;i<n-1;i++) {

dest=src;

src=dest;

}

dest=src;

src=temp;

return 2*n+1;

}

static int swapMergeSort(int work[], int swap[], int n, int flag)

{

int op=0;

int temp;

if (n>1) {

int m=n/2;

op+=swapMergeSort(work,swap,m,flag^1);

op+=swapMergeSort(work+m,swap+m,n-m,flag^1);

op+=swapMerge(work,swap,m,n,flag);

}

else if (flag == OUT) {/* n==1 */

temp=swap[0];

swap[0]=work[0];

work[0]=temp;

}

return op;

}

static int swapMerge(int work[], int swap[], int m, int n, int flag)

{

int *src, *dest;

int i=0, j=m, t=0;

int temp;

if (flag==OUT) {

src="/work";

dest=swap;

} else { /* flag==IN */

src="/swap";

dest=work;

}

temp=dest[t];

while (i<m && j<n)

if (src <= src[j]) {

dest[t++] = src;

src = dest[t];

} else {

dest[t++] = src[j];

src[j++] = dest[t];

}

while (i<m) {

dest[t++] = src;

if (t<n)

src = dest[t];

else

src = temp;

}

while (j<n) {

dest[t++] = src[j];

if (t<n)

src[j++] = dest[t];

else

src[j++] = temp;

}

return 2*n+1;

}

两路归并排序算法

========================================

Latest Snippet Version: 1.04

#i nclude <stdlib.h>

int mergesort(int p[], int n);

extern int insertsort(int p[], int n);

static int merge(int work[], int swap[], int m, int n, int flag);

int mergeSort(int p[], int n);

static int merge_sort(int p[], int swap[], int n, int flag);

/*

* 归并排序算法在 1938 年由 IBM 发明并在电动整理机上实现。

* 在 1945 年由 J. von Neumann 首次在 EDVAC 计算机上实现。

* 稳定，需要与序列同等大小的辅助空间。这里实现的是两路归并算法。

*/

#define IN 1

#define OUT 0

#define M 8 /* 启始路段长度 */

int mergesort(int p[], int n)

{

int op=0;

int * work=p;

int * swap;

int i,j,m;

int flag=OUT; /* 对换标志 */

if (n<=16)

return insertsort(work,n);

swap=(int*)calloc(n,sizeof(int));

if (swap==NULL)

return 0;

/* i 是经过插入排序的元素个数和未排序元素的开始位置 */

for(i=0;i+M<=n;i+=M)

op+=insertsort(work+i,M);

if (i<n)

op+=insertsort(work+i,n-i);

for(i=M; i<n; i<<=1,flag^=1) { /* i 为路段长度 */

m=i<<1; /* m 为路段长度乘以归并的路数 */

/* j 是已经归并路段的元素个数和未归并路段元素的开始位置 */

for(j=0;j+m<=n;j+=m)

op+=merge(work+j,swap+j,i,m,flag);

if (j+i<n)

op+=merge(work+j,swap+j,i,n-j,flag);

else if (j<n)

op+=merge(work+j,swap+j,n-j,n-j,flag);

}

if (flag==IN)

op+=merge(work,swap,n,n,flag);

free(swap);

return op;

}

/*

*

两路归并过程

*/

static int merge(int work[], /* 工作空间，就是要归并的列表 */

int swap[], /* 交换空间，不小于工作空间 */

int m, /* 前半部分列表长度和后半部分列表的开始位置 */

int n, /* 列表总长度 */

int flag) /* 换入换出标志 */

{

int *src, *dest;

int i=0, j=m, t=0;

if (flag==OUT) {

src="/work";

dest=swap;

} else { /* flag==IN */

src="/swap";

dest=work;

}

while (i<m && j<n)

if (src <= src[j])

dest[t++] = src;

else

dest[t++] = src[j++];

while (i<m)

dest[t++] = src;

while (j<n)

dest[t++] = src[j++];

return n;

}

/**************************************/

/* 下面是递归原型实现，留做参考 */

/**************************************/

int mergeSort(int p[], int n)

{

int op;

int * temp;

temp=(int*)calloc(n,sizeof(int));

if (temp==NULL)

return 0;

op=merge_sort(p,temp,n,IN);

free(temp);

return op;

}

static int merge_sort(int work[], int swap[], int n, int flag)

{

int op=0;

if (n>1) {

int m=n/2;

op+=merge_sort(work,swap,m,flag^1);

op+=merge_sort(work+m,swap+m,n-m,flag^1);

op+=merge(work,swap,m,n,flag);

}

else if (flag == OUT) /* n==1 */

swap[0]=work[0];

return op;

}

快速排序算法

=============================================

Latest Snippet Version: 1.10

int quicksort(int p[],int n);

extern int insertsort(int p[], int n);

static int partition(int p[],int n,int *m);

int quickSort(int p[],int n);

static int quick_sort(int p[],int n);

/*

* 快速排序算法在 1962 年由 C. Hoare 发明。

* 不稳定，需要与 lg(n) 成比例的辅助空间。

*/

static struct stackframe { /* 栈帧 */

int * list;

int length;

};

static struct stackframe sp[64]; /* 栈指针 */

static unsigned int randx; /* 伪随机数 */

#define M 16

int quicksort(int p[],int n)

{

int op=0;

int i,k;

int *h,l;

int m; /* 基准值的位置 */

struct stackframe *fp; /* 帧指针*/

struct stackframe *stp; /* 栈顶指针 */

if (n<=16)

return insertsort(p,n);

randx=p[0]%7875;

for (i=0,k=n; k>0; k>>=1,i++); /* i=[lg(n)] */

stp=sp+i;

fp=sp;

fp->list=p;

fp->length=n;

while (fp>=sp) {

h=fp->list;

l=fp->length;

/* 采用 D. Musser 的限定划分深度的建议 */

while (l>M && fp<=stp) {

op+=partition(h,l,&m);

fp->list=h+m+1;

fp->length=l-m-1;

fp++;

l=m;

}

fp--;

}

op+=insertsort(p,n);

return op;

}

/*

* 基准值选择采用 C. Hoare 建议的随机选择策略。

*/

static int partition(int p[],int n,

int *m ) /* 返回的基准值的位置 */

{

int i=0; /* 头指针 */

int j=n-1; /* 尾指针 */

int pivot; /* 基准值 */

int k;

if (n<=1)

return 0;

randx=(randx*421+1663)%7875; /* 线性同余伪随机数 */

k=randx%n;

/* 随机选择某个位置的元素作为基准值并保存它，

* 接着把头指针指向的元素复制到这个位置上 */

pivot=p[k];

p[k]=p;

/* p 已被交换到 p[k]，可以覆盖 */

while (i<j) { /* 头指针先于尾指针 */

while (i<j && p[j]>=pivot) /* 尾指针指向的元素大于基准值 */

j--; /* 前移尾指针 */

if (i<j)

p=p[j]; /* 替换当前p内容为p[j]的内容, 后移头指针 */

/* p[j] 已被交换可以覆盖 */

while (i<j && p<=pivot) /* 头指针指向的元素小于基准值 */

i++; /* 后移头指针 */

if (i<j)

p[j--]=p; /* 替换当前p[j]内容为p的内容, 前移尾指针 */

/* p 已被交换可以覆盖 */

}

/* 如果最后一次交换的是 p[j]，则 i 指针会移动成 i=j */

p=pivot; /* 把保存的基准值保存到当前位置上 */

*m=i; /* 返回基准值当前的位置 */

return n;

}

/**************************************/

/* 下面是递归原型实现，留做参考 */

/**************************************/

int quickSort(int p[],int n)

{

if (n<=16)

return insertsort(p,n);

randx=p[0]%7875;

return quick_sort(p,n);

}

static int quick_sort(int p[],int n)

{

int op=0;

int m;

if (n>1) {

op+=partition(p,n,&m);

op+=quick_sort(p,m);

op+=quick_sort(p+m+1,n-m-1);

}

return op;

}

基数排序算法

=================================================

Latest Snippet Version: 1.0

#i nclude <stdlib.h>

int radixsort(int p[], int n);

int distribute(int *src, int *dest, int n, int idx);

/*

* 基数排序算法的最早书面记述在 1923 年由 IBM 发表。当时实

* 现在电动排序机上。在 1954 年由 H. Seward 在计算机上实现。

* 稳定，需要与序列同等大小的辅助空间。

*/

int radixsort(int p[], int n)

{

int * swap;

swap=(int *)calloc(n,sizeof(int));

if (swap==NULL)

return 0;

/* 如果处理器不是小端字节序，而是大端字节序，

* 则下标应是 3,2,1,0 */

distribute(p, swap, n, 0);

distribute(swap, p, n, 1);

distribute(p, swap, n, 2);

distribute(swap, p, n, 3);

free(swap);

return 4*(2*n+512);

}

#define radix(x,y) (((unsigned char *)&(x))[(y)])

static int count[256];

/*

* 字节分布例程

*/

int distribute(int *src, int *dest, int n, int idx)

{

int i;

int index[256];

for (i=0; i<256; i++)

count=0;

/* 统计每个基数的元素数目 */

for (i=0; i<n; i++)

count[radix(src,idx)]++;

/* 计算与每个基数相对应的堆的位置索引 */

for (index[0]=0, i=1; i<256; i++)

index=index+count;

/* 把源列表中的元素分布到各个堆中 */

for (i=0; i<n; i++)

dest,idx)]++]=src;

return 2*n+512;

}