一个原创的排序算法(2007-04-19更新)

 

一个原创的排序算法

作者：寒蝉退士

最近的更新：2007-04-19，上次编辑：2004-02-17

这个排序算法名字叫做稳定排序算法，是我在2003年独力完成的，至于是否为首创就无从得知了。算法的特点是同归并排序算法一样是稳定的，需要同快速排序算法一样大小的辅助空间；复杂度为 lg(n)*lg(n)*n，是归并排序算法的 lg(n) 倍。目标应用是作为归并排序算法在内存不充足时的替代算法。

算法的设计目标

(1)是一个就地排序算法，就是说不需要与待排元素相同的辅助空间；与lg(n) 成正比的辅助空间是可以接受的，因为即使是排序 2⁶⁴ 个元素，也只需要 64 个单位的辅助空间。

(2)是一个稳定排序算法，就是说键值相同的元素之间的相对位置保持不变。稳定性的意义在于可以用它对多个键进行复合排序，比如数据库模式/表 schm(dm1,dm2)，我们执行查询 select * from schm order by dm1,dm2。可以先按 dm2 字段排序，再按 dm1 排序，结果的元组是按 dm1 次序排列，dm1 字段相同的元组按 dm2 次序排列。如果排序算法不稳定就不能完成预期的效果，因为第二次排序会破坏第一次的结果。

归并排序算法(复杂度为 lg(n)*n)和基数排序算法(复杂度为 n)是稳定的，但需要与待排元素相同的辅助空间的。快速排序算法和堆排序算法(复杂度是 lg(n)*n)是就地的，但它们都是不稳定的。我这里设计的算法是一个折衷的方案。曾经有人尝试就地归并排序算法的结果是实现了 lg(n)*n 复杂度，但却是不稳定的，并且速度不如堆排序算法，所以没有很大的意义。

算法的原理

算法的原型是:

void stablesort(int p[],int n)
{
	int m=n/2;

	if (n>1) {
		stablesort(p,m);
		stablesort(p+m,n-m);
		combine(p,m,n);
	}
}

static void combine(int p[],
			int m,	/* 前半部分列表长度和后半部分列表的开始位置 */
			int n)
{
	int i,j,temp;
		
	/* 两部分列表之间交换元素 */ 
	for(i=0; i=0;j--) {
		temp=p[m-i+j];
		p[m-i+j]=p[m+j];
		p[m+j]=temp;
	}
	/* 对前后两部分列表分别进行排序 */
	if(i>0 && i0 && i
	

这里的 combine() 函数的复杂度类似于快速排序算法，是 lg(n)*n，由此决定了这个算法的运行时间上限是归并排序算法的 lg(n) 倍。算法的平均运行时间是个数学问题，本文不予计较。

下面解释一下核心的 combine() 中交换操作：

	/* 两部分列表之间交换元素 */ 
	for(i=0; i=0;j--) {
		temp=p[m-i+j];
		p[m-i+j]=p[m+j];
		p[m+j]=temp;
	}

开始计数
 0       m-1       m        n-1
+----------+      +-----------+
| <======< |      | <=======< |
+----------+      +-----------+
          ^        ^
          |  <-->  |
          +-(比较)-+
          a        b

计数之后         
 0       m-1       m        n-1
+----------+      +-----------+
| <======< |      | <=======< |
+----------+      +-----------+
       ^              ^
       |  <-------->  |
       +----(比较)----+
       a              b

开始交换         
 0       m-1       m        n-1
+----------+      +-----------+
| <======< |      | <=======< |
+----------+      +-----------+
          ^           ^
       <- |        <- |
          +--(交换)---+
                     

交换之后        
 0       m-1       m        n-1
+----------+      +-----------+
| <==< |<=<|      |<=<| <===< |
+----------+      +-----------+
             

前提条件是前后两个列表都是有序的，第一个循环统计前后两部分之间需要交换的元素的数目， 前面的列表的最后一个元素是前面列表中最大的，用 a 指针指向它，后面的列表的第一个元素是后面列表的最小的，用 b 指针指向它。比较二个指针指向的元素的大小，如果 *a 大于 *b 则这两个元素需要交换，计数增一，前移 a 指针，后移 b 指针，继续比较，直到  *a 不大于 *b 计数结束。计数之后，第二个循环把前面列表的从后向前数的指定个数元素与后面列表的从前向后数的指定个数的元素进行对换，这样就形成了四个有序列表。

稳定性的证明:

 0       m-1       m        n-1
+----------+      +-----------+
|     x1   |      |  x2       |
+----------+      +-----------+
      | a  |      |b |

x1 和 x2是键值相同的元素， x1 是前面列表中有这个键值的最后一个元素，x2 是后面列表中有这个键值的第一个元素。a 是前面列表中 x1 后面大于它的元素的个数。b 是后面列表中 x2 前面小于它的元素的个数。如果 a 等于 b 则 x1 和 x2 不在对换的范围内，x1 和 x2 之间的相对位置不变。如果 a 大于 b 则 x1 必然小于等于相对应的比较元素，所以 x1 不在对换的范围内，x1 和 x2 之间的相对位置不变；同理 a 小于 b 时 x1 和 x2 之间的相对位置不变。

交换之后接着采用类似于快速排序算法的分治策略，两个相邻的列表一组继续 combine()。最终结束于两个元素的combine()，直接交换不再做进一步递归调用。

在 combine() 两个大小相差悬殊的列表的时候，算法有可能递归很深而占用大量的辅助空间，但不会象快速排序算法那样造成复杂度激增，在具体实现中必须限制 combine() 递归的深度，如果不加限制就谈不上就地排序算法了。在 combine() 的递归深度达到 lg(n) 或者符合指定条件的时候，直接进行插入排序而不再继续交换和分治。

算法实现

具体实现如下：

int stablesort(int p[],int n);
extern int insertsort(int p[],int n);
static int combine(int p[],int m,int n);

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

/*
 * 稳定排序算法的复杂度是 lg(n)*lg(n)*n，需要 lg(n) 的辅助空间。
 * 可用做归并排序算法在内存不充足时的替代算法。
 */
int stablesort(int p[],int n)
{
    int op=0;
    int i,j,m;

    if (n<=16)
        return insertsort(p,n);

    /* i 是经过插入排序的元素个数和未排序元素的开始位置 */
    for(i=0;i+M<=n;i+=M)
        op+=insertsort(p+i,M);
    if (i<n)
        op+=insertsort(p+i,n-i);
    for(i=M; i<n; i<<=1) { /* i 为路段长度 */
        m=i<<1; /* m 为路段长度乘以归并的路数 */
        /* j 是已经归并路段的元素个数和未归并路段元素的开始位置 */
        for(j=0;j+m<=n;j+=m)
            op+=combine(p+j,i,m);
        if (j+i<n)
            op+=combine(p+j,i,n-j);
    }
    return op;
}

static int combine(int p[],
            int m,    /* 前半部分列表长度和后半部分列表的开始位置 */
            int n ) /* 列表的长度 */
{
    int op=0;
    int i,j,temp;
        
    /* 两部分列表之间交换元素 */
    for(i=0; i<m && i<n-m && p[m+i]<p[m-1-i]; i++);
    for(j=i-1;j>=0;j--) {
        temp=p[m-i+j];
        p[m-i+j]=p[m+j];
        p[m+j]=temp;
    }
    if (i==0)
        return 0;
    op+=i;

    /* 对前后两部分列表分别进行排序 */
    if(i<m)
        if (i<M || m-i<M)
            op+=insertsort(p,m);
        else
            op+=combine(p,m-i,m);
    if(i<n-m)
        if (i<M || n-m-i<M)
            op+=insertsort(p+m,n-m);
        else
            op+=combine(p+m,i,n-m);
    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[i]>temp; i--) {
            p[i+1]=p[i];
            op++;
        }
        p[i+1]=temp;
        op++;
    }
    return op;
}