静态链表插入排序(List Insertion Sort)算法是直接插入排序的一个变种。它的改进目的是减少在直接插入排序中的移动次数(当然这个改进并没有降低复杂度,仍为O(n^2)),因此在原输入数据的基础上附加了一个静态链表(为了减少空间的消耗,静态链表实际上就是用等长的下标数组link来模拟的,而不需要建立一个等长的动态链结构)。该算法的缺点是:虽然减少了移动次数,但是需要增加一个等长度的link数组,所以也是用空间换取时间的做法。
设输入数组为v[], 在按升序排好序的状态下,设静态链表link[]中某个位置i的元素值为x=v[i],那么link[i]存储的是该元素x的下一个比它大的元素y=v[j]的位置值j,即link[i]=j。每次插入一个新的元素z=v[i]到左边的sorted list中时,从左边排好序的子序列中的head位置开始比较(注意:在以下实现中,head并不一定指向第一个元素!),寻着link的下标值,直到找到某个元素的值v[curr]大于(为了保证算法的稳定性,必须是大于而不能大于等于)z为止,这时curr指针的上一个位置指针为next,要插入z到next和curr之间,只需要修改:next指向z,z指向curr。sorted list中最右边一个元素的指针值永远为-1,作为tail标志。
由于得到的静态链表没法像直接存储了key值的数组那样随机访问,因此List Insertion Sort的最后还需要根据link[]将v[]转换为升序的静态数组(这里的静态数组中元素是key值)。转换方法采用in-place方式,从而无需开辟而外的空间。具体做法也是从head开始寻着link的下标值,找到的key值与左边子数组最右边那个元素交换(这里子数组已经是升序的静态数组),例如,设左边子数组最右边的元素为i=2,v[i]=30,link[i]=5,找到的key值下标为curr=6,v[curr]=20,link[curr]=7,那么交换后v[i]=20,link[i]=6(注意不是7!),v[curr]=30,link[curr]=5,这里link[i]=6是告诉以后的操作“原来第2个位置的元素已经挪到了第6个位置“,同时别忘了记下交换之前的next = link[curr]=7指针,即作为下一个操作的key位置值curr。
Java版本的实现:
/** * * List Insertion Sort algorithm * (Adapted from http://en.wikipedia.org/wiki/Insertion_sort) * * * Copyright (c) 2011 ljs (http://blog.csdn.net/ljsspace/) * Licensed under GPL (http://www.opensource.org/licenses/gpl-license.php) * * @author ljs * 2011-07-20 * */ public class ListInsertionSort { public static void sort(int[] v){ int n = v.length; //step 1: link[] creation int[] link = new int[n]; int head=0; int next=0,curr=0; link[0] = -1; for(int i=1;i<n;i++){ if(v[head]>v[i]){ //case: head is changed to i link[i] = head; head = i; //change head }else{ //two stop cases: //curr == -1: when we reach the tail //v[curr] > v[i]: insert i before curr, next is the predecessor of curr //note: this loop executes at least once so 'next' always have valid value for (curr = head ; curr != -1 && v[curr] <= v[i]; curr = link[curr]) next =curr; //insert i between next and curr (also applicable to tail case when curr=-1) link[next] = i; link[i] = curr; } } //step 2: arrange v[] by link[] information: find curr and swap it with i curr = head; //to scan linked list, always start with head //note the difference: //in this step: between iterations, curr doesn't start with head at the beginning //the link creation step: between iterations, we always scan from curr=head to find the insert position for (int i=0 ;i<n;i++){ while(curr < i) curr = link [curr]; //look only those elements on the right side of current element next = link[curr]; //save for next iteration's start position if (curr != i) { //if curr==i, no need change since position i is done. int swap = v[i]; //swap key v[i] = v[curr]; v[curr] = swap; link[curr] = link[i]; //copy i's link link[i] = curr; //reset pointer link[i] for redirection } curr = next; //next iteration we start from 'next' } //link[] is now useless, let it be garbage collected. } public static void main(String[] args) { int[] v = {49,38,65,97,76,13,27,49}; ListInsertionSort.sort(v); for(int key:v){ System.out.format(" %d",key); } } }
C版本的实现:(对Wikipedia上的代码稍作修改:http://en.wikipedia.org/wiki/Insertion_sort)
#include <stdio.h> #include <stdlib.h> void ListinsertSort(int * v, int n) { int * link = (int *)malloc(sizeof(int)*n); int head =0; int next,cur,i; link[0] = -1; //generate sorted static list: after sorting, head may not be the first element for (i = 1 ; i < n; i++){ if (v[head] > v[i]){ link[i] = head; head = i; } else { for (cur = head ; cur != -1 && v[cur] <= v[i]; cur = link[cur]) next =cur; link[next] = i; link[i] = cur; } } cur = head; //start with head for ( i = 0 ;i < n;i++){ while(cur < i) cur = link [cur]; //look only those elements on the right side of current element next = link[cur]; //save for next iteration if (cur != i) { int swap = v[i]; //swap key v[i] = v[cur]; v[cur] = swap; link[cur] = link[i]; //swap link link[i] = cur; } cur = next; } free(link); } int main(void) { int i; int* v = (int *)malloc(sizeof(int)*5); v[0]=3;v[1]=2;v[2]=1;v[3]=0;v[4]=5; ListinsertSort(v, 5); for(i=0;i<5;i++){ printf(" %d",v[i]); } free(v); return 0; }