熟練掌握常用的排序算法

1、前言

排序是數(shù)據(jù)處理中經(jīng)常運(yùn)用的一種重要運(yùn)算，排序的功能是將一個(gè)數(shù)據(jù)元素（記錄）的任意序列，重新排列成一個(gè)按照一個(gè)規(guī)則有序的序列。常用的排序算法我們要熟練掌握。

2、冒泡排序

冒泡排序（英語(yǔ)：Bubble Sort）是一種簡(jiǎn)單的排序算法。它重復(fù)地走訪過(guò)要排序的數(shù)列，一次比較兩個(gè)元素，如果他們的順序（如從大到小、首字母從A到Z）錯(cuò)誤就把他們交換過(guò)來(lái)。

示例：

3、選擇排序

選擇排序（Selection sort）是一種簡(jiǎn)單直觀的排序算法。它的工作原理如下。首先在未排序序列中找到最?。ù螅┰?，存放到排序序列的起始位置，然后，再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最?。ù螅┰?，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。

示例：

4、插入排序

插入排序（英語(yǔ)：Insertion Sort）是一種簡(jiǎn)單直觀的排序算法。它的工作原理是通過(guò)構(gòu)建有序序列，對(duì)于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。插入排序在實(shí)現(xiàn)上，通常采用in-place排序，因而在從后向前掃描過(guò)程中，需要反復(fù)把已排序元素逐步向后挪位，為最新元素提供插入空間。

示例：

5、希爾排序

希爾排序，也稱遞減增量排序算法，是插入排序的一種更高效的改進(jìn)版本。希爾排序是非穩(wěn)定排序算法。

希爾排序是基于插入排序的以下兩點(diǎn)性質(zhì)而提出改進(jìn)方法的：

插入排序在對(duì)幾乎已經(jīng)排好序的數(shù)據(jù)操作時(shí)，效率高，即可以達(dá)到線性排序的效率

但插入排序一般來(lái)說(shuō)是低效的，因?yàn)椴迦肱判蛎看沃荒軐?shù)據(jù)移動(dòng)一位

希爾排序先將待排記錄序列分割成為若干子序列分別進(jìn)行插入排序，待整個(gè)序列中的記錄"基本有序"時(shí)，再對(duì)全體記錄進(jìn)行一次直接插入排序。

示例：

6、歸并排序

歸并排序應(yīng)用的是分治的思想，將大隊(duì)列劃分成小隊(duì)列，然后小隊(duì)列內(nèi)排序，再將排好序的小隊(duì)列組合成大隊(duì)列，步驟：

1、將劃分成兩個(gè)隊(duì)列直到不可再分為止

2、小隊(duì)列內(nèi)排序

3、左隊(duì)列與右隊(duì)列合并

4、返回合并的隊(duì)列

示例：

7、快速排序

快速排序的基本思想是：通過(guò)一趟排序?qū)⒋庞涗浄指畛瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可分別對(duì)這兩部分記錄繼續(xù)進(jìn)行排序，已達(dá)到整個(gè)序列有序。一趟快速排序的具體過(guò)程可描述為：從待排序列中任意選取一個(gè)記錄(通常選取第一個(gè)記錄)作為基準(zhǔn)值，然后將記錄中關(guān)鍵字比它小的記錄都安置在它的位置之前，將記錄中關(guān)鍵字比它大的記錄都安置在它的位置之后。這樣，以該基準(zhǔn)值為分界線，將待排序列分成的兩個(gè)子序列。

一趟快速排序的具體做法為：設(shè)置兩個(gè)指針low和high分別指向待排序列的開(kāi)始和結(jié)尾，記錄下基準(zhǔn)值baseval(待排序列的第一個(gè)記錄)，然后先從high所指的位置向前搜索直到找到一個(gè)小于baseval的記錄并互相交換，接著從low所指向的位置向后搜索直到找到一個(gè)大于baseval的記錄并互相交換，重復(fù)這兩個(gè)步驟直到low=high為止

示例：

審核編輯：劉清