/*selection sort*/
//对列表中起始于位置p的连续n个元素做选择排序,valid(p) && rank(p) + n <= size

tamplate <typename T> void List<T>::selectionSort(Posi(T) p,int n){
    //待排区间(head,tail)
    Posi(T) head = p->pred;
    Posi(T) tail = p;
    for(int i=0; i<n; i++){     //head/tail可能是header/trailer.
        tail = tail->succ;      //(tail到trailer的succ了怎么办? 岂不是null了?)    
        /*改进方法:
        if(tail->succ != NULL){
            tail = tail->succ;
        }
        */
    }

    while(n>1){
        insertBefore(tail,remove( selectMax(head->succ,n) ));//insert要new,remove要delete
        tail = tail->pred;                                   //是通常基本操作的100倍
        n--;                                                 //改进(1):直接修改reference
    }                                                        //改进(2):修改succ/pred
}

/*selectMax*/

template <typename T>
Posi(T) List<T>::selectMax(Posi(T) p, int n){
    Posi(T) max = p;

    for(Posi(T) cur=p;n>1;n--){
        if( !lt((cur = cur->succ)->data,max->data) ) //not less than
            max = cur;                               //painter's algorithm
    }                                                //这里有一个trick, 要用>=,不用>
                                                     //selectMax()中对于多个相等的最大元素，选取其中位置最靠后者
    return max;
}

/*Insertion Sort*/
//对列表中起始于位置p的连续n个元素做插入排序

template<typename T>
void List<T>::insertSort(Posi(T) p,int n){
    for(int r=0;r<n;r++){       //r是已排序的元素个数
        insertAfter( search(p->data,r,p),p->data );     
        p = p->succ;
        remove(p->pred);        //转向下一节点
    }//O(r+1)
}//仅用O(1)辅助空间,就地算法(in-place algorithm)