選擇排序

選擇排序是指在排序過程序中，依次從待排序的記錄序列中選擇出關(guān)鍵字值最小的記錄、關(guān)鍵字值次小的記錄、……，并分別將它們定位到序列左側(cè)的第1個(gè)位置、第二個(gè)位置、……，最后剩下一個(gè)關(guān)鍵字值最大的記錄位于序列的最后一個(gè)位置，從而使待排序的記錄序列成為按關(guān)鍵字值由小到大排列的的有序序列。簡(jiǎn)單選擇排序1.簡(jiǎn)單選擇排序的基本思想

每一趟在n-i+1(i=1,2,3,...,n-1)個(gè)記錄中選取關(guān)鍵字最小的記錄作為有序序列中的第i個(gè)記錄。它的具體實(shí)現(xiàn)過程為：(1)將整個(gè)記錄序列劃分為有序區(qū)域和無序區(qū)域，有序區(qū)域位于最左端，無序區(qū)域位于右端，初始狀態(tài)有序區(qū)域?yàn)榭?，無序區(qū)域含有待排序的所有n個(gè)記錄。(2)設(shè)置一個(gè)整型變量index，用于記錄在一趟的比較過程中，當(dāng)前關(guān)鍵字值最小的記錄位置。開始將它設(shè)定為當(dāng)前無序區(qū)域的第一個(gè)位置，即假設(shè)這個(gè)位置的關(guān)鍵字最小，然后用它與無序區(qū)域中其他記錄進(jìn)行比較，若發(fā)現(xiàn)有比它的關(guān)鍵字還小的記錄，就將index改為這個(gè)新的最小記錄位置，隨后再用a[index].key與后面的記錄進(jìn)行比較，并根據(jù)比較結(jié)果，隨時(shí)修改index的值，一趟結(jié)束后index中保留的就是本趟選擇的關(guān)鍵字最小的記錄位置。(3)將index位置的記錄交換到無序區(qū)域的第一個(gè)位置，使得有序區(qū)域擴(kuò)展了一個(gè)記錄，而無序區(qū)域減少了一個(gè)記錄。不斷重復(fù)(2)、(3)，直到無序區(qū)域剩下一個(gè)記錄為止。此時(shí)所有的記錄已經(jīng)按關(guān)鍵字從小到大的順序排列就位。

簡(jiǎn)單選擇排序算法簡(jiǎn)單選擇排序的整體結(jié)構(gòu)應(yīng)該為：for(i=1;i<n;i){

第i趟簡(jiǎn)單選擇排序；}

下面我們進(jìn)一步分析一下“第i趟簡(jiǎn)單選擇排序”的算法實(shí)現(xiàn)。（1）初始化：假設(shè)無序區(qū)域中的第一個(gè)記錄為關(guān)鍵字值最小的元素，即將index=i;

下面我們進(jìn)一步分析一下“第i趟簡(jiǎn)單選擇排序”的算法實(shí)現(xiàn)。（2）搜索無序區(qū)域中關(guān)鍵字值最小的記錄位置：

for(j=i+1;j<=n;j++) if(a[j].key<a.[index].ke)index=j;

下面我們進(jìn)一步分析一下“第i趟簡(jiǎn)單選擇排序”的算法實(shí)現(xiàn)。（3）將無序區(qū)域中關(guān)鍵字最小的記錄與無序區(qū)域的第一個(gè)記錄進(jìn)行交換，使得有序區(qū)域由原來的i-1個(gè)記錄擴(kuò)展到i個(gè)記錄。

完整算法voidselecsort(DataTypea,intn){for(i=1;i<n;i++) //對(duì)n個(gè)記錄進(jìn)行n-1趟的簡(jiǎn)單選擇排序

{index=i; //初始化第i趟簡(jiǎn)單選擇排序的最小記錄指針

for(j=i+1;j<=n;j++) //搜索關(guān)鍵字最小的記錄位置

if(a[j].key<a[i].key)index=j;if(index!=i){temp=a[i];a[i]=a[index];a[index]=temp; }}}簡(jiǎn)單選擇排序算法簡(jiǎn)單，但是速度較慢，并且是一種不穩(wěn)定的排序方法.，但在排序過程中只需要一個(gè)用來交換記錄的暫存單元。堆排序1.堆排序的基本思想:堆排序是另一種基于選擇的排序方法。下面我們先介紹一下什么是堆？然后再介紹如何利用堆進(jìn)行排序。

2.堆定義：

由n個(gè)元素組成的序列{k1，k2，……，kn-1，kn}，當(dāng)且僅當(dāng)滿足如下關(guān)系時(shí)，稱之為堆。例如序列（47，35，27，26，18，7，13，19）滿足：

若將堆看成是一棵以k1為根的完全二叉樹，則這棵完全二叉樹中的每個(gè)非終端結(jié)點(diǎn)的值均不大于（或不小于）其左、右孩子結(jié)點(diǎn)的值。由此可以看出，若一棵完全二叉樹是堆，則根結(jié)點(diǎn)一定是這n個(gè)結(jié)點(diǎn)中的最小者或最大者。下面給出兩個(gè)堆的示例。下面我們討論一下如何利用堆進(jìn)行排序？從堆的定義可以看出，若將堆用一棵完全二叉樹表示，則根結(jié)點(diǎn)是當(dāng)前堆中所有結(jié)點(diǎn)的最小者（或最大者）。堆排序的基本思想是：首先將待排序的記錄序列構(gòu)造一個(gè)堆，此時(shí)，選出了堆中所有記錄的最小者或最大者，然后將它從堆中移走，并將剩余的記錄再調(diào)整成堆，這樣又找出了次小（或次大）的記錄，以此類推，直到堆中只有一個(gè)記錄為止，每個(gè)記錄出堆的順序就是一個(gè)有序序列。堆排序的篩選算法：voidsift(DataTypea,intk,intm){i=k;；j=2*i；temp=a[i]；

while(j<=m)//{if(j<m&&a[j].key<a[j+1].key)j++;if(a[i].key>a[j].key)break；

else{a[i]=a[j]；i=j；j=2*i；}}a[i]=temp；}堆排序完整的算法:voidheapsort(DataTypea,intn){h=n/2;//最后一個(gè)非終端結(jié)點(diǎn)的編號(hào)

for(i=h;i>=1;i--)//初建堆。從最后一個(gè)非終端結(jié)點(diǎn)至根結(jié)點(diǎn)

sift(a,i,n);for(i=n;i>1;i--)//重復(fù)執(zhí)行移走堆頂結(jié)點(diǎn)及重建堆的操作

{temp=a[1];a[1]=a[i];a[i]=temp;sift(a,1,i-1);}}

在堆排序中，除建初堆以外，其余調(diào)整堆的過程最多需要比較樹深次，因此，與