選擇類(lèi)排序

基本思想選擇排序的主要操作是選擇主要思想：第i趟在n-i+1（i=1,2,…,n-1）個(gè)記錄中選取關(guān)鍵碼最小的記錄作為有序序列中的第i個(gè)記錄。由于選擇排序方法每一趟總是從無(wú)序區(qū)中選出全局最?。ɑ蜃畲螅┑年P(guān)鍵字記錄，所以適合于從大量的記錄中選擇一部分排序記錄的問(wèn)題。介紹兩種選擇類(lèi)排序：簡(jiǎn)單選擇排序堆排序1.簡(jiǎn)單選擇排序需解決的關(guān)鍵問(wèn)題?⑴如何在待排序序列中選出關(guān)鍵碼最小的記錄？⑵如何確定待排序序列中關(guān)鍵碼最小的記錄在有序序列中的位置？1.簡(jiǎn)單選擇排序簡(jiǎn)單選擇排序示例0821i=22128i=12516490808i=321082849212849162516251.簡(jiǎn)單選擇排序簡(jiǎn)單選擇排序示例i=4i=5492108281625254921081628252849210816282528無(wú)序區(qū)只有一個(gè)記錄1.簡(jiǎn)單選擇排序212825164908kkk08問(wèn)題1：如何在無(wú)序區(qū)中選出關(guān)鍵碼最小的記錄？解決方法：設(shè)置一個(gè)整型變量k，用于記錄在一趟比較的過(guò)程中關(guān)鍵碼最小的記錄位置。算法描述：k=i; for(j=i+1;j<n;j++)if(r[j]<r[k])k=j;1.簡(jiǎn)單選擇排序問(wèn)題2：如何確定最小記錄的最終位置？解決方法：第i趟簡(jiǎn)單選擇排序的待排序區(qū)間是r[i]~r[n]，則r[i]是無(wú)序區(qū)第一個(gè)記錄，所以，將k所記載的關(guān)鍵碼最小的記錄與r[i]交換。算法描述：if(k!=i)r[i]←→r[k];1.簡(jiǎn)單選擇排序1.簡(jiǎn)單選擇排序算法性能分析最壞情況：3(n-1)次移動(dòng)次數(shù)：最好情況（正序）：0次空間性能：需一個(gè)輔助空間。穩(wěn)定性：是一種不穩(wěn)定的排序算法。比較次數(shù)：)()1(21211nOnninni=-=-?-=）（簡(jiǎn)單選擇排序的時(shí)間復(fù)雜度為O(n2)。2.堆排序簡(jiǎn)單選擇排序的改進(jìn)改進(jìn)的著眼點(diǎn)：如何減少關(guān)鍵碼間的比較次數(shù)。若能利用每趟比較后的結(jié)果，也就是在找出鍵值最小記錄的同時(shí)，也找出鍵值較小的記錄，則可減少后面的選擇中所用的比較次數(shù)，從而提高整個(gè)排序過(guò)程的效率。2.堆排序堆是具有下列性質(zhì)的完全二叉樹(shù)：每個(gè)結(jié)點(diǎn)的值都小于或等于其左右孩子結(jié)點(diǎn)的值（稱(chēng)為小根堆），或每個(gè)結(jié)點(diǎn)的值都大于或等于其左右孩子結(jié)點(diǎn)的值（稱(chēng)為大根堆）。18203236452538504028小根堆的根結(jié)點(diǎn)是所有結(jié)點(diǎn)的最小者。較小結(jié)點(diǎn)靠近根結(jié)點(diǎn)，但不絕對(duì)。2.堆排序堆是具有下列性質(zhì)的完全二叉樹(shù)：每個(gè)結(jié)點(diǎn)的值都小于或等于其左右孩子結(jié)點(diǎn)的值（稱(chēng)為小根堆），或每個(gè)結(jié)點(diǎn)的值都大于或等于其左右孩子結(jié)點(diǎn)的值（稱(chēng)為大根堆）。50384540283632201828大根堆的根結(jié)點(diǎn)是所有結(jié)點(diǎn)的最大者。較大結(jié)點(diǎn)靠近根結(jié)點(diǎn)，但不絕對(duì)。2.堆排序堆和序列的關(guān)系將堆用順序存儲(chǔ)結(jié)構(gòu)來(lái)存儲(chǔ)，則堆對(duì)應(yīng)一組序列。503845402836322018285038453236402820182812345678910采用順序存儲(chǔ)2.堆排序基本思想：首先將待排序的記錄序列構(gòu)造成一個(gè)堆，此時(shí)，選出了堆中所有記錄的最大者，然后將它從堆中移走，并將剩余的記錄再調(diào)整成堆，這樣又找出了次小的記錄，以此類(lèi)推，直到堆中只有一個(gè)記錄。需解決的關(guān)鍵問(wèn)題?（1）如何由一個(gè)無(wú)序序列建成一個(gè)堆（即初始建堆）？（2）當(dāng)堆頂記錄移走后，如何調(diào)整剩余記錄，使之成為一個(gè)新的堆（即重建堆）？2.堆排序算法描述：for(i=n/2;i>=1;i--)

sift(r,i,n);

最后一個(gè)結(jié)點(diǎn)（葉子）的序號(hào)是n，則最后一個(gè)分支結(jié)點(diǎn)即為結(jié)點(diǎn)n的雙親，其序號(hào)是n/2。問(wèn)題1：如何由一個(gè)無(wú)序序列建成一個(gè)堆？2.堆排序2.堆排序2.堆排序2.堆排序2.堆排序問(wèn)題2：去掉堆頂后，如何調(diào)整（重新建堆）？第i次處理堆頂是將堆頂記錄r[1]與序列中第n-i+1個(gè)記錄r[n-i+1]交換。r[1]←→r[n-i+1];2.堆排序問(wèn)題2：去掉堆頂后，如何調(diào)整（重新建堆）？r[1]←→r[n-i+1];sift(r,1,n-i);2.堆排序算法性能分析第1個(gè)for循環(huán)是初始建堆，需要O(n)時(shí)間；第2個(gè)for循環(huán)是輸出堆頂重建堆，共需要取n-1次堆頂記錄，第i次取堆頂記錄重建堆需要O(log2i)時(shí)間，需要O(nlog2n)時(shí)間；因此整個(gè)時(shí)間復(fù)雜度為O(nlog2n)，這是堆排序的最好、最壞和平均的時(shí)間代價(jià)。在堆排序算法中，只需要一個(gè)用做記錄交換的暫存單元。堆排序是一種不穩(wěn)定的排序方法。Topk問(wèn)題當(dāng)n巨大時(shí)，問(wèn)題進(jìn)一步演化為在海量數(shù)據(jù)中查找有限k條最大的記錄。先讀取k條記錄建立一個(gè)有k個(gè)元素的小頂堆；然后依次讀取剩余的n-k條記錄，每讀取一條記錄就與堆頂元素比較，如果大于堆頂元素則替換堆頂，并重新調(diào)整成堆；當(dāng)記錄讀取完后，堆中的k條記錄就是所求的最大記錄，總時(shí)間復(fù)雜度為O(k+(n-k)log2n)=O(nlog2k)。