关于列表的排序算法

• 插入排序(insertionsort)
  算法的思路可简要描述为：始终将整个序列视作并切分为两部分：有序的前缀，无序的后缀；通过迭代，反复地将后缀的首元素转移至前缀中
  //对起始位置p的n个元素就行排序

void insertionsort(ListNode p,int n){
for (int r = 0; r < n; r++) {
 insertAfter(search(p->data, r, p), p->data); 
 p = p->succ;
 remove(p->pred);
}
}

复杂度是O(n^2),是稳定算法

• 选择排序
  该算法也将序列划分为无序前缀和有序后缀两部分,此外，还要求前缀不大于后后缀。如此，每次只需从前缀中选出最大者，并作为最小元素转移至后缀中，即可使有序部分的范围不断扩张。
  //对起始于位置p的n个元素排序

void selectionSort(ListNode p,int n){
ListNode header=p.pred,ListNode trailer=p;
for(int r=0,r<n,r++){
trailer=trailer.succ;
}//待排序区间为(header,trailer)
while(1<n){
ListNode max=selectMax(header.succ,n);//找出最大者
insertBefore(trailer,remove(max));//作为有序区间的首元素
trailer=trailer.pred;
n--;
}
}
//从位置p起始的n个元素中查找最大的元素
ListNode selectMax(ListNode p,int n){
ListNode max=p;
for(ListNode curr=p;1<n;n--){
if((curr=curr.succ).data>=max){
max=curr;
}
return max;
}

该算法复杂度为O(n^2),从selectMax方法着手,可整体优化为O(nlogn)

• 归并排序
  1.二路归并算法
  //有序列表的归并:当前列表自p起的n个元素,与列表L中自q起的m个元素归并

void merge(ListNode p,int n,List T,ListNode q,int m){
ListNode pp=p.pred;
while(m>0){
if((n>0)&&(p.data<=q.data)){
  if(q==(p=(p.succ))){
break;
n--;
}
  }
else{
insertBefore(p,L.remove((q=q.succ).pred));
m--;
}
p = pp->succ;
}

2.分治策略

void mergeSort(ListNode p, int n) { 
if (n < 2)
 return; //若待排序范围已足够小，则直接返回；
int m = n >> 1; //以中点为界
ListNode q = p; 
for (int i = 0; i < m; i++) 
q = q->succ; //均分列表
 mergeSort(p, m);
 mergeSort(q, n - m); //对前、后子列表分删排序
 merge(p, m, *this, q, n - m); //归并
}

总体算法复杂度是O(nlogn)