【正文】 不滿足堆的性質(zhì)。簡單選擇排序的示例：操作方法：第一趟，從n 個記錄中找出關(guān)鍵碼最小的記錄與第一個記錄交換；第二趟，從第二個記錄開始的n1 個記錄中再選出關(guān)鍵碼最小的記錄與第二個記錄交換；以此類推.....第i 趟，則從第i 個記錄開始的ni+1 個記錄中選出關(guān)鍵碼最小的記錄與第i 個記錄交換，直到整個序列按關(guān)鍵碼有序。 即：先將序列的第1個記錄看成是一個有序的子序列，然后從第2個記錄逐個進(jìn)行插入，直至整個序列有序?yàn)橹?。二?實(shí)驗(yàn)步驟 各種內(nèi)部排序算法的比較：1. 八種排序算法的復(fù)雜度分析（時間與空間）。所以，相等元素的前后順序沒有改變，從原無序序列出去的順序就是排好序后的順序，所以插入排序是穩(wěn)定的。由堆的定義可以看出，堆頂元素（即第一個元素）必為最小項(xiàng)（小頂堆）。如圖：再討論對n 個元素初始建堆的過程。但若初始序列按關(guān)鍵碼有序或基本有序時，快排序反而蛻化為冒泡排序。 我不是很清楚他們的時間復(fù)雜度，也真的不知道他們到底誰快誰慢，因?yàn)闀系耐茖?dǎo)我確實(shí)只是小小了解，并沒有消化。 ：n*n的時間復(fù)雜度，穩(wěn)定排序，原地排序。 ，選擇排序，冒泡排序的比較，他們的時間復(fù)雜度都是n*n。雖然堆排序在使用的中沒有快速排序廣泛，但是他的數(shù)據(jù)結(jié)構(gòu)和思想真的很不錯，而且用它來實(shí)現(xiàn)優(yōu)先隊(duì)列，效率沒得說。堆排序堆已經(jīng)排好的數(shù)據(jù)交換上比快速多。只要選擇一下，不就可以了。我得到的收獲很大，總結(jié)一下各自排序的收獲： 冒泡：好實(shí)現(xiàn)，速度不慢，使用于輕量級的數(shù)據(jù)排序。 ，堆排序，合并排序，希爾排序的比較，他們的時間復(fù)雜的都是n*log(n)，我認(rèn)為在使用上快速排序最廣泛，他原地排序，雖然不穩(wěn)定，可是很多情況下排序根本就不在意他是否穩(wěn)定。他的思想是利用的堆這種數(shù)據(jù)結(jié)構(gòu)，堆可以看成一個完全二叉樹，所以在排序中比較的次數(shù)可以做到很少。選擇排序就是冒泡的基本思想，從小的定位，一個一個選擇，直到選擇結(jié)束。我覺得他的思想很不錯，分治，而且還是原地排序，省去和很多的空間浪費(fèi)?；鶖?shù)排序基于分別排序，分別收集，所以是穩(wěn)定的。另一部分記錄的2）將根結(jié)點(diǎn)與左、右子樹中較小元素的進(jìn)行交換。3. 選擇排序—簡單選擇排序（Simple Selection Sort） 基本思想： 在要排序的一組數(shù)中，選出最?。ɑ蛘咦畲螅┑囊粋€數(shù)與第1個位置的數(shù)交換；然后在剩下的數(shù)當(dāng)中再找最小（或者最大）的與第2個位置的數(shù)交換，依次類推，直到第n1個元素（倒數(shù)第二個數(shù)）和第n個元素（最后一個數(shù)）比較為止。1. 插入排序直接插入排序（Straight lnsertion Sort） 基本思想： 將一個記錄插入到已排序好的有序表中，從而得到一個新，記錄數(shù)增1的有序表。2. 八種排序算法的C語言編程實(shí)現(xiàn)。 希爾排序 (4)線性階(O(n))排序 基數(shù)排序，此外還有桶、箱排序。 時效分析： 時間復(fù)雜度：O（n^2）2. 插入排序—希爾排序（Shell`s Sort）希爾排序是1959 提出來的，相對直接排序有較大的改進(jìn)。若以一維數(shù)組存儲一個堆，則堆對應(yīng)一棵完全二叉樹，且所有非葉結(jié)點(diǎn)的值均不大于(或不小于)其子女的值，根結(jié)點(diǎn)（堆頂元素）的值是最小(或最大)的。建堆方法：對初始序列建堆的過程，就是一個反復(fù)進(jìn)行篩選的過程。算法的實(shí)現(xiàn)：從算法描述來看，堆排序需要兩個過程，一是建立堆，二是堆頂與堆的最后一個元素交換位置。為改進(jìn)之，通常以“三者取中法”來選取基準(zhǔn)記錄，即將排序區(qū)間的兩個端點(diǎn)與中點(diǎn)三個記錄關(guān)鍵碼居中的調(diào)整為支點(diǎn)記錄。