1、前言

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

2、冒泡排序

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

示例：

3、選擇排序

選擇排序（Selection sort）是一種簡單直觀的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續(xù)尋找最小（大）元素，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。

示例：

4、插入排序

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

示例：

5、希爾排序

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

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

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

但插入排序一般來說是低效的，因為插入排序每次只能將數(shù)據(jù)移動一位

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

示例：

6、歸并排序

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

1、將劃分成兩個隊列直到不可再分為止

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

3、左隊列與右隊列合并

4、返回合并的隊列

示例：

7、快速排序

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

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

示例：

審核編輯：劉清