基本思想：每一趟（如第i趟）在后面n-i+1（i=1，2...n-1）個(gè)待排序元素中選取關(guān)鍵字最小的元素，作為有序子序列的第i個(gè)元素，直到第n-1趟排完。

簡(jiǎn)單選擇排序

void SelectSort(ElemType A[], int n)
{
    for(i=0;i<n-1;++i){
        min=i; //記錄小最小元素的位置
        for(j=i+1;j<n;++j)
            if(A[j]<A[min])  min=j;
        if(min!=i)  swap(A[i], A[min]);
    }
}

空間效率 O(1)
時(shí)間效率 O(n^2)
不穩(wěn)定
第i個(gè)元素和當(dāng)前最小元素交換時(shí)，可能會(huì)改變第i個(gè)元素與其相同關(guān)鍵字元素的相對(duì)位置（本來(lái)在前面的被換到后面去了）

堆排序

void BuildMaxHeap(ElemType A[], int len){
    for(int i=len/2;i>0;i--)
        AdjustDown(A, i, len);
}

void AdjustDown(ElemType A[], int k, int len)
{
    A[0]=A[k]; //A[0]用來(lái)暫存
    for(i=2*k;i<=len;i*=2){
        if(i<len&&A[i]<A[i+1])
            ++i;
        if(A[0]>=A[i]) break;
        else{
            A[k]=A[i];
            k=i;
        }
    }
    A[k]=A[0];
}

O(n)
基本思想：在排序過(guò)程中，將序列視為一棵完全二叉樹(shù)的順序存儲(chǔ)，首先將L[1...n]個(gè)元素建成初始大頂堆，在一次輸出堆頂元素

void HeapSort(ElemType A[], int len)
{
    BuildMaxHeap(A, len);
    for(i=len;i>1;--i){
        Swap(A[i], A[1]);    //輸出堆頂元素（和堆底元素交換）
        AdjustDown(A, 1, i-1);
    }
}

空間效率O(1)
時(shí)間效率O(nlog2n)
不穩(wěn)定
進(jìn)行篩選時(shí)，有可能把本來(lái)排在前面的先調(diào)到堆頂，先輸出，那就被調(diào)到后面去了。