- 插入排序(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),是穩(wěn)定算法
- 選擇排序
該算法也將序列劃分為無序前綴和有序后綴兩部分,此外矗晃，還要求前綴不大于后后綴看疙。如此，每次只需從前綴中選出最大者浦旱，并作為最小元素轉移至后綴中宇色，即可使有序部分的范圍不斷擴張。
//對起始于位置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;
}//待排序區(qū)間為(header,trailer)
while(1<n){
ListNode max=selectMax(header.succ,n);//找出最大者
insertBefore(trailer,remove(max));//作為有序區(qū)間的首元素
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方法著手,可整體優(yōu)化為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)
