排序算法講解

排序算法一、排序總述二、算法解讀

2.1冒泡排序2.2插入排序2.3希爾排序

2.4選擇排序1/14一排序總述排序算法分為兩大類1.非線性時(shí)間比較類排序：通過比較來決定元素間的相對(duì)次序，由于其時(shí)間復(fù)雜度不能突破O(nlogn)，因此稱為非線性時(shí)間比較類排序。2.線性時(shí)間非比較類排序：不通過比較來決定元素間的相對(duì)次序，它可以突破基于比較排序的時(shí)間下界，以線性時(shí)間運(yùn)行，因此稱為線性時(shí)間非比較類排序。各種算法見下頁(yè)，表中名詞解釋如下：1.穩(wěn)定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。2.不穩(wěn)定：如果a原本在b的前面，而a=b，排序之后a可能會(huì)出現(xiàn)在b的后面。3.時(shí)間復(fù)雜度：對(duì)排序數(shù)據(jù)的總的操作次數(shù)。反映當(dāng)n變化時(shí)，操作次數(shù)呈現(xiàn)什么規(guī)律。4.空間復(fù)雜度：是指算法執(zhí)行時(shí)所需存儲(chǔ)空間的度量，它也是數(shù)據(jù)規(guī)模n的函數(shù)。在倉(cāng)儲(chǔ)單元中也可理解為倉(cāng)位數(shù)。在倉(cāng)儲(chǔ)排序時(shí)，空間復(fù)雜度是主要的選擇依據(jù)，其次為時(shí)間復(fù)雜度。2/14一排序總述排序方法時(shí)間復(fù)雜度（平均）時(shí)間復(fù)雜度（最壞）時(shí)間復(fù)雜度（最好）空間復(fù)雜度穩(wěn)定性插入排序穩(wěn)定希爾排序不穩(wěn)定選擇排序穩(wěn)定堆排序不穩(wěn)定冒泡排序穩(wěn)定快速排序不穩(wěn)定歸并排序穩(wěn)定計(jì)數(shù)排序穩(wěn)定桶排序穩(wěn)定基數(shù)排序穩(wěn)定3/14二算法解讀2.1冒泡排序1.什么是冒泡？冒泡排序是一種簡(jiǎn)單的排序算法。它重復(fù)地走訪過要排序的數(shù)列，一次比較兩個(gè)元素，如果它們的順序錯(cuò)誤就把它們交換過來。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說該數(shù)列已經(jīng)排序完成。這個(gè)算法的名字由來是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端。2.算法描述①比較相鄰的元素。如果前者比后者大，就交換它們兩個(gè)；②對(duì)每一對(duì)相鄰元素作同樣的工作，從開始第一對(duì)到結(jié)尾的最后一對(duì)，這樣在最后的元素應(yīng)該會(huì)是最大的數(shù)；③針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)；④重復(fù)步驟①~③，直到排序完成。3.算法拓展在比較相鄰元素時(shí)，也可以將交換相鄰元素的條件變?yōu)椋呵罢弑群笳咝　＿@樣我們會(huì)得到一列由大到小排列的元素。4/142.1冒泡排序3.冒泡舉例361524361524361254316254136254136254136245132645123645第一輪第二輪5/142.1冒泡排序3.冒泡舉例123645123465123465123456第三輪第四輪（結(jié)束）6/14二算法解讀2.2插入排序1.什么是插入？插入排序的算法描述是一種簡(jiǎn)單直觀的排序算法。它的工作原理是通過構(gòu)建有序序列，對(duì)于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。2.算法描述一般來說，插入排序都采用in-place在數(shù)組上實(shí)現(xiàn)。具體算法描述如下：①?gòu)牡谝粋€(gè)元素開始，該元素可以認(rèn)為已經(jīng)被排序；②取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描；③如果該元素（已排序）大于新元素，將該元素移到下一位置；④重復(fù)步驟③，直到找到已排序的元素小于或者等于新元素的位置；⑤將新元素插入到該位置后；⑥重復(fù)步驟②~⑤。3.算法分析插入排序通常只需用到O(1)的額外空間的排序，因而在從后向前掃描過程中，需要反復(fù)把已排序元素逐步向后挪位，為最新元素提供插入空間。7/142.2插入排序315243652461361524136245135642123564123456黃色：已排序無色：待排序取出元素123456次數(shù)4.插入舉例8/14二算法解讀

9/142.3希爾排序4.希爾排序舉例361524t=3:361524361524321564361524（不變）321564（調(diào)換）321564（不變）10/141235641235643215642.3希爾排序4.希爾排序舉例t=2:（調(diào)換）（不變）（不變）123564123564123564（調(diào)換）12356412346511/141234652.3希爾排序4.希爾排序舉例t=1:（不變）（不變）123465123465123465123465（不變）123465123465（不變）123465123465（調(diào)換）12345612/14二算法解讀

13/142.4選擇排序3615241635242123564341234655黃色：有序區(qū)無色：無序區(qū)選出無序區(qū)中的最小元素12345次數(shù)4.選擇排序舉例1與無序區(qū)中的第1個(gè)數(shù)據(jù)