當前位置:首頁 » 操作系統 » 基礎排序演算法

基礎排序演算法

發布時間: 2023-12-09 06:10:02

Ⅰ 八大演算法

演算法中比較常用的有八種演算法,基本演算法的題,都是依靠這些基礎演算法或者結合使用出題的,所以要學會基礎演算法,才有可能去更好的掌握演算法題。

插入排序,又叫直接插入排序。實際中,我們玩撲克牌的時候,就用了插入排序的思想。

基本思想:在待排序的元素中,假設前n-1個元素已有序,現將第n個元素插入到前面已經排好的序列中,使得前n個元素有序。按照此法對所有元素進行插入,直到整個序列有序。但我們並不能確定待排元素中究竟哪一部分是有序的,所以我們一開始只能認為第一個元素是有序的,依次將其後面的元素插入到這個有序序列中來,直到整個序列有序為止。

希爾排序,又稱縮小增量法。其基本思想是:

 1>先選定一個小於N的整數gap作為第一增量,然後將所有距離為gap的元素分在同一組,並對每一組的元素進行直接插入排序。然後再取一個比第一增量小的整數作為第二增量,重復上述操作…

    2>當增量的大小減到1時,就相當於整個序列被分到一組,進行一次直接插入排序,排序完成。

選擇排序,即每次從待排序列中選出一個最小值,然後放在序列的起始位置,直到全部待排數據排完即可。

如何進行堆排序呢?

步驟如下:

 1、將堆頂數據與堆的最後一個數據交換,然後對根位置進行一次堆的向下調整,但是調整時被交換到最後的那個最大的數不參與向下調整。

 2、完成步驟1後,這棵樹除最後一個數之外,其餘數又成一個大堆,然後又將堆頂數據與堆的最後一個數據交換,這樣一來,第二大的數就被放到了倒數第二個位置上,然後該數又不參與堆的向下調整…反復執行下去,直到堆中只有一個數據時便結束。此時該序列就是一個升序。

冒泡排序,該排序的命名非常形象,即一個個將氣泡冒出。冒泡排序一趟冒出一個最大(或最小)值。

快速排序是公認的排序之王,快速排序是Hoare於1962年提出的一種二叉樹結構的交換排序演算法,其基本思想為:

 任取待排序元素序列中的某元素作為基準值,按照該基準值將待排序列分為兩子序列,左子序列中所有元素均小於基準值,右子序列中所有元素均大於基準值,然後左右序列重復該過程,直到所有元素都排列在相應位置上為止。

歸並排序是採用分治法的一個非常典型的應用。其基本思想是:將已有序的子序合並,從而得到完全有序的序列,即先使每個子序有序,再使子序列段間有序。

計數排序,又叫非比較排序。顧名思義,該演算法不是通過比較數據的大小來進行排序的,而是通過統計數組中相同元素出現的次數,然後通過統計的結果將序列回收到原來的序列中。

Ⅱ 基本排序演算法原理

演算法原理:每次對相鄰的兩個元素進行比較,若前者大於後者則進行交換,如此一趟下來最後一趟的就是最大元素,重復以上的步驟,除了已經確定的元素 。

演算法原理:每次對相鄰的兩個元素進行比較,若前者大於後者則進行交換,如此一趟下來最後一趟的就是最大元素,重復以上的步驟,除了已經確定的元素

演算法步驟

1)  設置兩個變數i、j,排序開始的時候:i=0,j=n-1;

2)第一個數組值作為比較值,首先保存到temp中,即temp=A[0];

3)然後j-- ,向前搜索,找到小於temp後,因為s[i]的值保存在temp中,所以直接賦值,s[i]=s[j]

4)然後i++,向後搜索,找到大於temp後,因為s[j]的值保存在第2步的s[i]中,所以直接賦值,s[j]=s[i],然後j--,避免死循環

5)重復第3、4步,直到i=j,最後將temp值返回s[i]中

6)  然後採用「二分」的思想,以i為分界線,拆分成兩個數組 s[0,i-1]、s[i+1,n-1]又開始排序

排序圖解

演算法原理:從第一個元素開始,左邊視為已排序數組,右邊視為待排序數組,從左往右依次取元素,插入左側已排序數組,對插入新元素的左側數組重新生成有序數組 。需要注意的是,在往有序數組插入一個新元素的過程中,我們可以採用按 順序循環 比較,也可以通過 折半查找法 來找到新元素的位置,兩種方式的效率 取決於數組的數據量

演算法原理:希爾排序也是利用插入排序的思想來排序。希爾排序通過將比較的全部元素分為幾個區域來提升插入排序的性能。這樣可以讓一個元素可以一次性地朝最終位置前進一大步。然後演算法再取越來越小的步長進行排序,演算法的最後一步就是普通的插入排序,但是到了這步,需排序的數據幾乎是已排好的了,插入效率比較高。

排序圖解

選擇排序(Selection sort)是一種簡單直觀的排序演算法。它的工作原理如下。首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然後,再從剩餘未排序元素中繼續尋找最小(大)元素,然後放到已排序序列的末尾。以此類推,直到所有元素均排序完畢。選擇排序的主要優點與數據移動有關。如果某個元素位於正確的最終位置上,則它不會被移動。選擇排序每次交換一對元素,它們當中至少有一個將被移到其最終位置上,因此對n個元素的表進行排序總共進行至多n-1次交換。在所有的完全依靠交換去移動元素的排序方法中,選擇排序屬於非常好的一種。

歸並排序,顧名思義就是一種 「遞歸合並」 的排序方法(這個理解很重要)。對於一個數列,我們把它進行二分處理,依次遞歸下去,然後將小范圍的數進行排序,最後將其合並在一起。就實現了歸並排序。

這實際上是運用了 分治思想 ,顯然,想要把一個數列排好序,最終達到的目的就是它的任何一部分都是有序的。這樣的話,我們可以考慮分別把數列分成N多個部分,讓每個部分分別有序,然後再將其統一,變成所有的東西都有序。這樣就實現了排序。這個想法就叫分治思想。

排序圖解

排序圖解

Ⅲ 排序法的排序法的基本步驟

排序法是根據一些特定的標准(例如工作的復雜程度、對組織的貢獻大小等對各個職位的相對價值)進行整體比較,進而將職位按照相對價值的高低排列出一個次序。其基本步驟是:
1、對排序的標准達成共識。雖然排序法是對崗位的整體價值進行評價而排序,但也需要參與評估的人員對什麼樣的「整體價值」更高達成共識,如責任更大,知識技能更高,工作更加復雜,環境因素惡劣等。
2、選定參與排序的職位。如果公司較小可以選取全部職位進行排序。
3、評定人員根據事先確定評判標准,對公司同類崗位的重要性逐一作出評判,最重要的排在第一位,次要的、再次要的順次往下排列。
4、將經過所有評定人員評定的每個崗位的結果加以匯總,得到序號和。然後將序號和除以評定人數,得到每一崗位的平均序數。最後,按平均序數的大小,由小到大評定出各崗位的相對價值的次序。

Ⅳ vb三種基本排序演算法

三種基本排序演算法(與哪種編程語言無關):
冒泡排序演算法、選擇排序演算法、插入排序演算法

Ⅳ 幾種排序演算法的比較

一、八大排序演算法的總體比較

4.3、堆的插入:

每次插入都是將新數據放在數組最後。可以發現從這個新數據的父結點到根結點必然為一個有序的數列,然後將這個新數據插入到這個有序數據中

(1)用大根堆排序的基本思想

先將初始數組建成一個大根堆,此對為初始的無序區;

再將最大的元素和無序區的最後一個記錄交換,由此得到新的無序區和有序區,且滿足<=的值;

由於交換後新的根可能違反堆性質,故將當前無序區調整為堆。然後再次將其中最大的元素和該區間的最後一個記錄交換,由此得到新的無序區和有序區,且仍滿足關系的值<=的值,同樣要將其調整為堆;

..........

直到無序區只有一個元素為止;

4.4:應用

尋找M個數中的前K個最小的數並保持有序;

時間復雜度:O(K)[創建K個元素最大堆的時間復雜度] +(M-K)*log(K)[對剩餘M-K個數據進行比較並每次對最大堆進行從新最大堆化]

5.希爾排序

(1)基本思想

先將整個待排序元素序列分割成若乾子序列(由相隔某個「增量」的元素組成的)分別進行直接插入排序,然後依次縮減增量再進行排序,待整個序列中的元素基本有序(增量足夠小)時,再對全體元素進行一次直接插入排序(因為直接插入排序在元素基本有序的情況下,效率很高);

(2)適用場景

比較在希爾排序中是最主要的操作,而不是交換。用已知最好的步長序列的希爾排序比直接插入排序要快,甚至在小數組中比快速排序和堆排序還快,但在涉及大量數據時希爾排序還是不如快排;

6.歸並排序

(1)基本思想

首先將初始序列的n個記錄看成是n個有序的子序列,每個子序列的長度為1,然後兩兩歸並,得到n/2個長度為2的有序子序列,在此基礎上,再對長度為2的有序子序列進行兩兩歸並,得到若干個長度為4的有序子序列,以此類推,直到得到一個長度為n的有序序列為止;

(2)適用場景

若n較大,並且要求排序穩定,則可以選擇歸並排序;

7.簡單選擇排序

(1)基本思想

第一趟:從第一個記錄開始,將後面n-1個記錄進行比較,找到其中最小的記錄和第一個記錄進行交換;

第二趟:從第二個記錄開始,將後面n-2個記錄進行比較,找到其中最小的記錄和第2個記錄進行交換;

...........

第i趟:從第i個記錄開始,將後面n-i個記錄進行比較,找到其中最小的記錄和第i個記錄進行交換;

以此類推,經過n-1趟比較,將n-1個記錄排到位,剩下一個最大記錄直接排在最後;

熱點內容
與編譯系統相同的軟體 發布:2024-02-29 17:22:53 瀏覽:415
超解壓鴨的視頻 發布:2024-02-29 17:11:49 瀏覽:554
c語言刪標點 發布:2024-02-29 17:11:49 瀏覽:807
安卓怎麼抽簽 發布:2024-02-29 17:03:11 瀏覽:427
買單反相機要有什麼配置 發布:2024-02-29 16:48:32 瀏覽:194
語義分析階段在編譯過程中的作用 發布:2024-02-29 16:01:33 瀏覽:290
現代悅納哪個配置有手環 發布:2024-02-29 15:57:24 瀏覽:636
存儲卡FC 發布:2024-02-29 15:39:54 瀏覽:582
win2008建ftp 發布:2024-02-29 15:31:17 瀏覽:856
大數據生成腳本 發布:2024-02-29 15:25:55 瀏覽:630