三種簡單排序方法

1、三種簡單排序方法數(shù) 據(jù) 結(jié) 構(gòu)排序1.1 簡單選擇排序簡單選擇排序的作法是：第一趟掃描所有數(shù)據(jù)，選擇其中最小的一個與第一個數(shù)據(jù)互換；第二趟從第二個數(shù)據(jù)開始向后掃描，選擇最小的與第二個數(shù)據(jù)互換；依次進(jìn)行下去，進(jìn)行了(n-1)趟掃描以后就完成了整個排序過程。在每一趟掃描數(shù)據(jù)時，用一個整型變量跟蹤當(dāng)前最小數(shù)據(jù)的位置，然后，第i趟掃描只需將該位置的數(shù)據(jù)與第i個數(shù)據(jù)交換即可。這樣掃描n-1次，處理數(shù)據(jù)的個數(shù)從n每次逐漸減1，每次掃描結(jié)束時才可能有一次交換數(shù)據(jù)的操作。 排序圖7.1 簡單選擇排序排序簡單選擇排序分析簡單選擇排序在(n-1)趟掃描中共需進(jìn)行n(n-1)/2次比較，最壞情況下的互換次數(shù)為(n-

2、1)，整個算法的時間復(fù)雜性為O(n2)。簡單選擇排序簡單并且容易實現(xiàn)，適宜于n較小的情況。簡單選擇排序是不穩(wěn)定的排序算法。排序簡單選擇排序算法void selectsort (sqlist r, int n) int i, j, min; for (i=1;i=n-1;i+) min=i; /*用min指出每一趟在無序區(qū)范圍內(nèi)的最小元素*/ 排序簡單選擇排序算法續(xù) for (j=i+1;j=n-1;j+) if (rj.key rmin.key) min=j; r0 = ri; /* r0用于暫時存放元素*/ ri = rmin; rmin =r0; 排序1.2 冒泡排序冒泡排序是一種簡單而且

3、容易理解的排序方法，它和氣泡從水中不斷往上冒的情況有些類似。其基本思想是對存放原始數(shù)據(jù)的數(shù)組，按從后往前的方向進(jìn)行多次掃描，每次掃描稱為一趟（pass）。當(dāng)發(fā)現(xiàn)相鄰兩個數(shù)據(jù)的次序與排序要求的“遞增次序”不符合時，即將這兩個數(shù)據(jù)進(jìn)行互換。這樣，較小的數(shù)據(jù)就會逐單元向前移動，好象氣泡向上浮起一樣。排序圖7.2 冒泡排序過程排序需掃描的趟數(shù)視原始數(shù)據(jù)最初的排列次序的不同而不同，最壞的情況要進(jìn)行（n-1）趟掃描，一般常常少于(n-1)趟即可完成?？梢栽O(shè)置一個標(biāo)志flag用來指示掃描中有沒有進(jìn)行數(shù)據(jù)交換，每趟掃描開始前將其置1。當(dāng)這趟掃描至少出現(xiàn)一次互換時，將其置0。如某趟掃描后flag仍為1，說明此趟

4、掃描已無數(shù)據(jù)互換，則排序結(jié)束，不必再繼續(xù)掃描了。排序冒泡排序算法void bubblesort(sqlist r, int n) int i,j,flag; for(i=1;i=n-1;i+) flag=1; for( j=i;j=n-1;j+) if (rj+1.key rj.key) 排序冒泡排序算法續(xù) flag=0; r0=rj; /* r0用于暫時存放元素*/ rj=rj+1; rj+1=r0; if (flag=1) return; 排序冒泡排序算法分析冒泡排序算法的優(yōu)點是比較容易理解，且當(dāng)原始數(shù)據(jù)大體符合要求的次序時，運算速度較快。但它不是高效率的算法，在最壞的情況下，如果輸入數(shù)據(jù)

5、的次序與排序要求的次序完全相反，冒泡排序需要進(jìn)行n(n-1)/2次比較和n(n-1)3/2次移動，其數(shù)量級均為O(n2)。對于有相同關(guān)鍵字記錄的情況，冒泡排序是穩(wěn)定的。排序1.3 直接插入排序直接插入排序的基本思想是：從數(shù)組的第二個單元開始，依次從原始數(shù)據(jù)中取出數(shù)據(jù)，并將其插入到數(shù)組中該單元之前的已排好序的序列中合適的位置處。直接插入算法需要經(jīng)過（n-1）趟插入過程。如果數(shù)據(jù)恰好應(yīng)插入到序列的最后端，則不需移動數(shù)據(jù)，可節(jié)省時間，所以若原始數(shù)據(jù)大體有序，此算法可以有較快的運算速度。排序圖7.3 簡單插入排序排序簡單插入排序算法void insertsort (sqlist r, int n) int i,j; for( i=2; i=n; i+) r0=ri; /* r0用于暫時存放待插入的元素*/ j= i-1; /* j為待比較元素下標(biāo)，初始時指向待插入元素前一個單元*/ 排序簡單插入排序算法續(xù) while (r0.keyrj.key) rj+1=rj;