- 插入排序(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)
