四大排序算法

1、冒泡排序（Bubble Sort），是一種計(jì)算機(jī)科學(xué)領(lǐng)域的較簡單的排序算法。它重復(fù)地走訪過要排序的數(shù)列，一次比較兩個(gè)元素，如果他們的順序錯(cuò)誤就把他們交換過來。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說該數(shù)列已經(jīng)排序完成。這個(gè)算法的名字由來是因?yàn)樵酱蟮脑貢?jīng)由交換慢慢“浮”到數(shù)列的頂端，故名。冒泡排序算法的運(yùn)作如下：（從后往前）比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)。對每一對相鄰元素作同樣的工作，從開始第一對到結(jié)尾的最后一對。在這一點(diǎn)，最后的元素應(yīng)該會是最大的數(shù)。針對所有的元素重復(fù)以上的步驟，除了最后一個(gè)。持續(xù)每次對越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對數(shù)字需

2、要比較。冒泡排序就是把小的元素往前調(diào)或者把大的元素往后調(diào)。比較是相鄰的兩個(gè)元素比較，交換也發(fā)生在這兩個(gè)元素之間。所以，如果兩個(gè)元素相等，我想你是不會再無聊地把他們倆交換一下的；如果兩個(gè)相等的元素沒有相鄰，那么即使通過前面的兩兩交換把兩個(gè)相鄰起來，這時(shí)候也不會交換，所以相同元素的前后順序并沒有改變，所以冒泡排序是一種穩(wěn)定排序算法。選擇排序（Select Sort）每一趟從待排序的數(shù)據(jù)元素中選出最小（或最大）的一個(gè)元素，順序放在已排好序的數(shù)列的最后，直到全部待排序的數(shù)據(jù)元素排完。選擇排序是不穩(wěn)定的排序方法。選擇排序是給每個(gè)位置選擇當(dāng)前元素最小的，比如給第一個(gè)位置選擇最小的，在剩余元素里面給第二個(gè)元

3、素選擇第二小的，依次類推，直到第n-1個(gè)元素，第n個(gè)元素不用選擇了，因?yàn)橹皇Ｏ滤粋€(gè)最大的元素了。那么，在一趟選擇，如果一個(gè)元素比當(dāng)前元素小，而該小的元素又出現(xiàn)在一個(gè)和當(dāng)前元素相等的元素后面，那么交換后穩(wěn)定性就被破壞了。比較拗口，舉個(gè)例子，序列5 8 5 2 9，我們知道第一遍選擇第1個(gè)元素5會和2交換，那么原序列中2個(gè)5的相對前后順序就被破壞了，所以選擇排序不是一個(gè)穩(wěn)定的排序算法。插入排序（Insert Sort）有一個(gè)已經(jīng)有序的數(shù)據(jù)序列，要求在這個(gè)已經(jīng)排好的數(shù)據(jù)序列中插入一個(gè)數(shù)，但要求插入后此數(shù)據(jù)序列仍然有序，這個(gè)時(shí)候就要用到一種新的排序方法插入排序法,插入排序的基本操作就是將一個(gè)數(shù)據(jù)插入

4、到已經(jīng)排好序的有序數(shù)據(jù)中，從而得到一個(gè)新的、個(gè)數(shù)加一的有序數(shù)據(jù)，算法適用于少量數(shù)據(jù)的排序。是穩(wěn)定的排序方法。插入算法把要排序的數(shù)組分成兩部分：第一部分包含了這個(gè)數(shù)組的所有元素，但將最后一個(gè)元素除外，而第二部分就只包含這一個(gè)元素。在第一部分排序后，再把這個(gè)最后元素插入到此刻已是有序的第一部分里的位置包括：直接插入排序，二分插入排序（又稱折半插入排序），鏈表插入排序，希爾排序（又稱縮小增量排序）。屬于穩(wěn)定排序的一種（通俗地講，就是兩個(gè)相等的數(shù)不會交換位置） 。一般來說，插入排序都采用in-place在數(shù)組上實(shí)現(xiàn)。具體算法描述如下： 從第一個(gè)元素開始，該元素可以認(rèn)為已經(jīng)被排序 取出下一個(gè)元素，在已經(jīng)

5、排序的元素序列中從后向前掃描 如果該元素（已排序）大于新元素，將該元素移到下一位置 重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置 將新元素插入到下一位置中 重復(fù)步驟25如果比較操作的代價(jià)比交換操作大的話，可以采用二分查找法來減少比較操作的數(shù)目。該算法可以認(rèn)為是插入排序的一個(gè)變種，稱為二分查找排序。插入排序是在一個(gè)已經(jīng)有序的小序列的基礎(chǔ)上，一次插入一個(gè)元素。當(dāng)然，剛開始這個(gè)有序的小序列只有1個(gè)元素，就是第一個(gè)元素。比較是從有序序列的末尾開始，也就是想要插入的元素和已經(jīng)有序的最大者開始比起，如果比它大則直接插入在其后面，否則一直往前找直到找到它該插入的位置。如果碰見一個(gè)和插入元素相等的

6、，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后順序沒有改變，從原無序序列出去的順序就是排好序后的順序，所以插入排序是穩(wěn)定的。快速排序（Quicksort）是對冒泡排序的一種改進(jìn)。由C. A. R. Hoare在1962年提出。它的基本思想是：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。設(shè)要排序的數(shù)組是A0AN-1，首先任意選取一個(gè)數(shù)據(jù)（通常選用數(shù)組的第一個(gè)數(shù)）作為關(guān)鍵數(shù)據(jù)，然后將所有比它小的數(shù)都放到它前面，所有比它大的數(shù)都放到它后面，這個(gè)過程稱為一趟快速排序。值得注意的是，快速排序不是一種穩(wěn)定的排序算法，也就是說，多個(gè)相同的值的相對位置也許會在算法結(jié)束時(shí)產(chǎn)生變動。一趟快速排序的算法是：1）設(shè)置兩個(gè)變量i、j，排序開始的時(shí)候：i=0，j=N-1；2）以第一個(gè)數(shù)組元素作為關(guān)鍵數(shù)據(jù)，賦值給key，即key=A0；3）從j開始向前搜索，即由后開始向前搜索(j-)，找到第一個(gè)小于key的值A(chǔ)j，將Aj賦給Ai；4）從i開始向后搜索，即由前開始向后搜索(i+)，找到第一個(gè)大于key的Ai，將Ai賦給Aj；5）重復(fù)第3、4步，直到i=j； (3,4步中，沒找到符合條件的值，即3中Aj不小