柚子快報激活碼778899分享：算法 C語言：排序（1）

http://yzkb.51969.com/

目錄

一、排序的概念及應(yīng)用

排序的概念

排序的運用

?二、常見排序算法

插入排序

基本思想

直接插入排序

希爾排序( 縮小增量排序 )

選擇排序

基本思想

堆排序

一、排序的概念及應(yīng)用

排序的概念

排序：所謂排序，就是使一串記錄，按照其中的某個或某些關(guān)鍵字的大小，遞增或遞減的排列起來的操作。

穩(wěn)定性：假定在待排序的記錄序列中，存在多個具有相同的關(guān)鍵字的記錄，若經(jīng)過排序，這些記錄的相對次 序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，則稱這種排 序算法是穩(wěn)定的；否則稱為不穩(wěn)定的。

內(nèi)部排序：數(shù)據(jù)元素全部放在內(nèi)存中的排序。

外部排序：數(shù)據(jù)元素太多不能同時放在內(nèi)存中，根據(jù)排序過程的要求不斷地在內(nèi)外存之間移動數(shù)據(jù)的排序。

排序的運用

? ? ?類似于淘寶、京東這種商品排列就是用到了排序算法。

?二、常見排序算法

插入排序

基本思想

? ? 直接插入排序是一種簡單的插入排序法，其基本思想是：把待排序的記錄按其關(guān)鍵碼值的大小逐個插入到一個已經(jīng)排好序的有序序列中，直到所有的記錄插入完為 止，得到一個新的有序序列 。

?實際中我們玩撲克牌時，就用了插入排序的思想

?

直接插入排序

? ? 當(dāng)插入第i(i>=1)個元素時，前面的array[0],array[1],…,array[i-1]已經(jīng)排好序，此時用array[i]的排序碼與 array[i-1],array[i-2],…的排序碼順序進行比較，找到插入位置即將array[i]插入，原來位置上的元素順序后移

直接插入排序的特性總結(jié)：

1. 元素集合越接近有序，直接插入排序算法的時間效率越高

2. 時間復(fù)雜度：O(N^2)

3. 空間復(fù)雜度：O(1)，它是一種穩(wěn)定的排序算法

4. 穩(wěn)定性：穩(wěn)定 ?

希爾排序( 縮小增量排序 )

? ? 希爾排序法又稱縮小增量法，希爾排序法的基本思想是：先選定一個整數(shù)，把待排序文件中所有記錄分成個 組，所有距離為的記錄分在同一組內(nèi)，并對每一組內(nèi)的記錄進行排序。然后，取，重復(fù)上述分組和排序的工 作。當(dāng)?shù)竭_=1時，所有記錄在統(tǒng)一組內(nèi)排好序。

希爾排序的特性總結(jié)：

1. 希爾排序是對直接插入排序的優(yōu)化。

2. 當(dāng)gap > 1時都是預(yù)排序，目的是讓數(shù)組更接近于有序。當(dāng)gap == 1時，數(shù)組已經(jīng)接近有序的了，這樣就 會很快。這樣整體而言，可以達到優(yōu)化的效果。我們實現(xiàn)后可以進行性能測試的對比。

3. 希爾排序的時間復(fù)雜度不好計算，因為gap的取值方法很多，導(dǎo)致很難去計算，因此在好些樹中給出的 希爾排序的時間復(fù)雜度都不固定

4. 穩(wěn)定性：不穩(wěn)定

選擇排序

基本思想

? 每一次從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€元素，存放在序列的起始位置，直到全部待排序的數(shù)據(jù)元素排完 。

直接選擇排序

在元素集合array[i]--array[n-1]中選擇關(guān)鍵碼最大(小)的數(shù)據(jù)元素

若它不是這組元素中的最后一個(第一個)元素，則將它與這組元素中的最后一個（第一個）元素交換

在剩余的array[i]--array[n-2]（array[i+1]--array[n-1]）集合中，重復(fù)上述步驟，直到集合剩余1個元素

?直接選擇排序的特性總結(jié)：

1. 直接選擇排序思考非常好理解，但是效率不是很好。實際中很少使用

2. 時間復(fù)雜度：O(N^2)

3. 空間復(fù)雜度：O(1)

4. 穩(wěn)定性：不穩(wěn)定

堆排序

? ? 堆排序(Heapsort)是指利用堆積樹（堆）這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計的一種排序算法，它是選擇排序的一種，它是 通過堆來進行選擇數(shù)據(jù)，需要注意的是排升序要建大堆，排降序建小堆。

?直接選擇排序的特性總結(jié)：

1. 堆排序使用堆來選數(shù)，效率就高了很多。

2. 時間復(fù)雜度：O(N*logN)

3. 空間復(fù)雜度：O(1)

4. 穩(wěn)定性：不穩(wěn)定

? ? ? ?本篇內(nèi)容就先到這里，后續(xù)會繼續(xù)寫關(guān)于排序的內(nèi)容，希望對各位有幫助，如果有錯歡迎指出。

柚子快報激活碼778899分享：算法 C語言：排序（1）

http://yzkb.51969.com/

精彩鏈接