• 插入排序(insertionsort)
  算法的思路可簡(jiǎn)要描述為：始終將整個(gè)序列視作并切分為兩部分：有序的前綴，無(wú)序的后綴；通過(guò)迭代，反復(fù)地將后綴的首元素轉(zhuǎn)移至前綴中
  //對(duì)起始位置p的n個(gè)元素就行排序

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);
}
}

復(fù)雜度是O(n^2),是穩(wěn)定算法

• 選擇排序
  該算法也將序列劃分為無(wú)序前綴和有序后綴兩部分,此外，還要求前綴不大于后后綴。如此，每次只需從前綴中選出最大者，并作為最小元素轉(zhuǎn)移至后綴中，即可使有序部分的范圍不斷擴(kuò)張。
  //對(duì)起始于位置p的n個(gè)元素排序

void selectionSort(ListNode p,int n){
ListNode header=p.pred,ListNode trailer=p;
for(int r=0,r<n,r++){
trailer=trailer.succ;
}//待排序區(qū)間為(header,trailer)
while(1<n){
ListNode max=selectMax(header.succ,n);//找出最大者
insertBefore(trailer,remove(max));//作為有序區(qū)間的首元素
trailer=trailer.pred;
n--;
}
}
//從位置p起始的n個(gè)元素中查找最大的元素
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;
}

該算法復(fù)雜度為O(n^2),從selectMax方法著手,可整體優(yōu)化為O(nlogn)

• 歸并排序
  1.二路歸并算法
  //有序列表的歸并:當(dāng)前列表自p起的n個(gè)元素,與列表L中自q起的m個(gè)元素歸并

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; //以中點(diǎn)為界
ListNode q = p; 
for (int i = 0; i < m; i++) 
q = q->succ; //均分列表
 mergeSort(p, m);
 mergeSort(q, n - m); //對(duì)前、后子列表分刪排序
 merge(p, m, *this, q, n - m); //歸并
}

總體算法復(fù)雜度是O(nlogn)