程序員必須知道的8大排序和3大查找

1、程序員必須知道的8大排序和3大查找現(xiàn)在我們分析一下8種排序算法的穩(wěn)定性。（請網(wǎng)友結(jié)合前面的排序基本思想來理解排序的穩(wěn)定性（8種排序的基本思想己 經(jīng)在前面說過，這里不再贅述）不然可能有些模糊）（1）直接插入排序：一般插入排序，比較是從有序序列的最后一個元索開始， 如果比它大則直接插入在其后面，否則一直往前比。如杲找到一個和插入元素相 等的，那么就插入到這個相等元素的后而。插入排序是穩(wěn)定的。（2）希爾排序：希爾排序是按照不同步長對元素進行插入排序，一次插入排序 是穩(wěn)定的，不會改變相同元索的相對順序，但在不同的插入排序過程中，相同的 元素可能在各自的插入排序中移動，穩(wěn)定性就會被破壞，所以希爾排序不穩(wěn)

2、定。（3）簡單選擇排序：在一趟選擇，如果當前元素比一個元素小，而該小的元素 又出現(xiàn)在一個和當前元素相等的元素后而，那么交換后穩(wěn)定性就被破壞了。光說 可能有點模糊，來看個小實例：858410,笫一遍掃描，笫1個元素8會和4交 換，那么原序列屮2個8的相對前后順序和原序列不一致了，所以選擇排序不穩(wěn) 定。（4）堆排序：堆排序的過程是從第n/2開始和其了節(jié)點共3個值選擇最大（大 頂堆）或者最?。ㄐ№敹眩?，這3個元素z間的選擇當然不會破壞穩(wěn)定性。但當為n /2-1, n/2-2,這些父節(jié)點選擇元素時，有可能第n/2個父節(jié)點交換把后面一 個元素交換過去了，而第n/2-1個父節(jié)點把后面一個相同的元素沒有交換

3、，所以 堆排序并不穩(wěn)定。（5）冒泡排序：由前而的內(nèi)容可知，冒泡排序是相鄰的兩個元素比較，交換也 發(fā)生在這兩個元索之間，如果兩個元索相等，不用交換。所以冒泡排序穩(wěn)定。（6）快速排序：在中樞元素和序列中一個元素交換的時候，很有可能把前面的 元素的穩(wěn)定性打亂。還是看一個小實例：6 4 4 5 4 7 8 9,第一趟排序，屮樞 元索6和第三個4交換就會把元索4的原序列破壞，所以快速排序不穩(wěn)定。（7）歸并排序：在分解的了列中，有1個或2個元素時，1個元素不會交換，2 個元素如果大小相等也不會交換。在序列合并的過程屮，如果兩個當前元素相等 時，我們把處在前面的序列的元素保存在結(jié)果序列的前面，所以，歸并排序

4、也是 穩(wěn)定的。（8）基數(shù)排序：是按照低位先排序，然后收集；再按照高位排序，然后再收集； 依次類推，直到最高位。有時候有些屬性是有優(yōu)先級順序的，先按低優(yōu)先級排序， 再按高優(yōu)先級排序，最后的次序就是高優(yōu)先級高的在前，高優(yōu)先級相同的低優(yōu) 先級高的在前?；鶖?shù)排序基于分別排序，分別收集，所以是穩(wěn)定的。8種排序的分類，穩(wěn)定性，吋間復雜度和空間復雜度總結(jié):h性 定 穩(wěn)7 n2 0(n20(xllz00(0(n20(xnz定 穩(wěn) 不選擇n2)x17(n20(序 排 堆xlfz定 穩(wěn) 不n2)0(7 n2 z(x o0 o定 穩(wěn) 不2 o (nl 0(n)0(x17 rd) l+r d(nrd0(注:琴教排序的

5、復雜度中,r代表關鍵字的基數(shù),d代表長度,n代表關鍵字的個數(shù)。常見查找1順序表的查找所謂順序表，特點是相鄰記錄的物理位置也是相鄰的。1）順序查找算法思路：給定一個key值，在表屮順序?qū)Ρ龋舸嬖趉二key,則查找成功, 返回記錄序號，或者成功1,失敗返回0；2）折半杳找對于有序的順序存儲表來說，可以用這個方法挺高查找效率。算法思路：1給定值key,逐步確定待查記錄所在區(qū)間，每次將搜索空間減少一半，直到查 找成功或者失敗為止。2設兩個指針（或者游標）low, high,分別表示頭和尾,初始時1 ow = 1, high =n 令 mid = （low+high）/2;3將mid指向的值與key值

6、比較如果mickkey,則說明要找的值應該往high靠近, 令low二二"mid+1；比較如果mid二key,則說明要找的值應該往low靠近，令 high = high-1；當key = mid所指向的值或者low=high不滿足時返回。/key, 則說明要找的值應該往high靠近，令low 簡單代碼舉例:1 include <stdio.h>2 itincludc <stdlib. h>33 define maxsize 104 ttdefine true 15 define false 076 intbin_search(int *list, intlen

7、, int key);9loint main (intarge, char *argv)1112 int list maxsize=1,3, 5, 7,9,11,13,15, 17, 19;13 int key = 18;14 printf (z，%dnz，,bin_search(list,maxsize,key);15 return 0;161718intsqserch(int *list, intlen, int key)/順序查找1920 inti;21 i 二 len;22 whilc(listi != key &&i>=0)i-;23 return i;2425

8、26intbin search(int *list, intlen, int key)/折半查找27 28 int low = 0, hight = len-1, mid;29 while(low <= hight)30 mid 二(1ow + hight) / 2;31 if(listmid二二 key)32 return true;33 if (listmid < key) 34 low = mid + 1;35 36 else37 hight = mid -1;38 39 40 return false;4142</stdlib. h></stdio. h&

9、gt;快速排序一趟快速排序的算法是：1) 設置兩個變量i、j,排序開始的吋候:i二0, j二n-1；2) 以第一個數(shù)組元索作為關鍵數(shù)據(jù)，賦值給key,即key=a0；3) 從j開始向前搜索,即由后開始向前搜索(j),找到第一個小于key的值 aj,將 aj和 ai互換;4) 從i開始向后搜索，即由前開始向后搜索(i+),找到第一個大于key的ai, 將ai和aj互換；5) 重復第3、4步，直到i=j； (3, 4步中，沒找到符合條件的值，即3中aj 不小于key, 4中ai不大于key的時候改變j、i的值，使得j=j-l, i=i+l,直 至找到為止。找到符合條件的值，進行交換的時候i, j指

10、針位置不變。另外, i二二j這一過程一定正好是i+或j完成的時候，此時令循環(huán)結(jié)束)。#i nclude<iostream>using namespace std;void qsort(int a, int low, int high)if(low>=high) rcturn;int first=low;int last=high;int key=afirst ;/*用字表的第一個記錄作為樞軸*/while(first<last)while(first<last&&alast>=key) -last;afirst=alast ;/*將比第一個小的移到低端*/while (first<last&&afirst二key) +first;a last二a first ;/*將比第一個大的移到高端*/a f irst =key; / *樞軸記錄到位*/qsort (a, 1ow, first-1);qsort (a, f irst+1, high);int main ()int a = 57, 6& 59, 52, 72, 2& 96, 33,