各種排序算法總結(jié)

1、各種排序算法總結(jié)排序算法是最基本最常用的算法，不同的排序算法在不同的場(chǎng)景或應(yīng)用中會(huì)有不同的表現(xiàn)，我們需要對(duì)各種排序算法熟練才能將它們應(yīng)用到實(shí)際當(dāng)中，才能更好地發(fā)揮它們的優(yōu)勢(shì)。今天，來(lái)總結(jié)下各種排序算法。下面這個(gè)表格總結(jié)了各種排序算法的復(fù)雜度與穩(wěn)定性：各種排序算法復(fù)雜度比較.png冒泡排序冒泡排序可謂是最經(jīng)典的排序算法了，它是基于比較的排序算法，時(shí)間復(fù)雜度為O(n2)，其優(yōu)點(diǎn)是實(shí)現(xiàn)簡(jiǎn)單，n較小時(shí)性能較好。· 算法原理相鄰的數(shù)據(jù)進(jìn)行兩兩比較，小數(shù)放在前面，大數(shù)放在后面，這樣一趟下來(lái)，最小的數(shù)就被排在了第一位，第二趟也是如此，如此類推，直到所有的數(shù)據(jù)排序完成· c+代碼實(shí)現(xiàn)1.

2、void bubble_sort(int arr, int len) 2.  3.       for (int i = 0; i < len - 1; i+) 4.        5.          

3、; for (int j = len - 1; j >= i; j-) 6.            7.               if (arrj < arrj - 

4、;1) 8.                9.                   int temp = arrj; 10.        

5、0;          arrj = arrj - 1; 11.                   arrj - 1 = temp; 12.       &#

6、160;        13.            14.        15.  選擇排序· 算法原理先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最?。ù螅┰兀缓蠓诺揭雅判蛐蛄械哪┪?。以此類推，直到所有元素均排序完畢。 · c+代碼實(shí)現(xiàn)1. void

7、 select_sort(int arr, int len) 2.    3.       for (int i = 0; i < len; i+) 4.        5.           

8、;int index = i; 6.           for (int j = i + 1; j < len; j+) 7.            8.       &#

9、160;       if (arrj < arrindex) 9.                   index = j; 10.            11.

10、           if (index != i) 12.            13.               int temp = arri; 14. 

11、0;             arri = arrindex; 15.               arrindex = temp;  16.          

12、0; 17.        18.    插入排序· 算法原理將數(shù)據(jù)分為兩部分，有序部分與無(wú)序部分，一開(kāi)始有序部分包含第1個(gè)元素，依次將無(wú)序的元素插入到有序部分，直到所有元素有序。插入排序又分為直接插入排序、二分插入排序、鏈表插入等，這里只討論直接插入排序。它是穩(wěn)定的排序算法，時(shí)間復(fù)雜度為O(n2) · c+代碼實(shí)現(xiàn)1. void insert_sort(int arr, int len) 2.  

13、0; 3.       for (int i = 1; i < len; i +) 4.        5.           int j = i - 1; 6.   &#

14、160;       int k = arri; 7.           while (j > -1 && k < arrj ) 8.            9

15、.               arrj + 1 = arrj; 10.               j -; 11.            

16、;12.           arrj + 1 = k; 13.        14.    快速排序· 算法原理快速排序是目前在實(shí)踐中非常高效的一種排序算法，它不是穩(wěn)定的排序算法，平均時(shí)間復(fù)雜度為O(nlogn)，最差情況下復(fù)雜度為O(n2)。它的基本思想是：通過(guò)一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部

17、分的所有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過(guò)程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。 · c+代碼實(shí)現(xiàn)1. void quick_sort(int arr, int left, int right) 2.  3.   if (left < right) 4.    5.       int i 

18、= left, j = right, target = arrleft; 6.       while (i < j) 7.        8.           while (i < j &am

19、p;& arrj > target) 9.               j-; 10.           if (i < j) 11.          &#

20、160;    arri+ = arrj; 12.  13.           while (i < j && arri < target) 14.              &#

21、160;i+; 15.           if (i < j) 16.               arrj = arri; 17.        18.     

22、;  arri = target; 19.       quick_sort(arr, left, i - 1); 20.       quick_sort(arr, i + 1, right); 21.    22.  歸并排序· 算法原理歸并排序具體工作原理如下（假設(shè)序列共有

23、n個(gè)元素）：o 將序列每相鄰兩個(gè)數(shù)字進(jìn)行歸并操作（merge)，形成floor(n/2)個(gè)序列，排序后每個(gè)序列包含兩個(gè)元素 o 將上述序列再次歸并，形成floor(n/4)個(gè)序列，每個(gè)序列包含四個(gè)元素 o 重復(fù)步驟2，直到所有元素排序完畢歸并排序是穩(wěn)定的排序算法，其時(shí)間復(fù)雜度為O(nlogn)，如果是使用鏈表的實(shí)現(xiàn)的話，空間復(fù)雜度可以達(dá)到O(1)，但如果是使用數(shù)組來(lái)存儲(chǔ)數(shù)據(jù)的話，在歸并的過(guò)程中，需要臨時(shí)空間來(lái)存儲(chǔ)歸并好的數(shù)據(jù)，所以空間復(fù)雜度為O(n)· c+代碼實(shí)現(xiàn)1. void merge(int arr, int temp_arr,

24、0;int start_index, int mid_index, int end_index) 2.   3.      int i = start_index, j = mid_index + 1; 4.      int k = 0; 5.    

25、60; while (i < mid_index + 1 && j < end_index + 1) 6.       7.          if (arri > arrj) 8.      &

26、#160;       temp_arrk+ = arrj+; 9.          else 10.              temp_arrk+ = arri+; 11.      

27、 12.      while (i < mid_index + 1) 13.       14.          temp_arrk+ = arri+; 15.       16.     

28、 while (j < end_index + 1) 17.          temp_arrk+ = arrj+; 18.  19.      for (i = 0, j = start_index; j < end_index +&

29、#160;1; i +, j +) 20.          arrj = temp_arri; 21.   22.  23.  void merge_sort(int arr, int temp_arr, int start_index, int end_index) 24.  

30、0;25.      if (start_index < end_index) 26.       27.          int mid_index = (start_index + end_index) / 2; 28.     

31、;     merge_sort(arr, temp_arr, start_index, mid_index); 29.          merge_sort(arr, temp_arr, mid_index + 1, end_index); 30.          

32、;merge(arr, temp_arr, start_index, mid_index, end_index); 31.       32.   堆排序二叉堆二叉堆是完全二叉樹(shù)或者近似完全二叉樹(shù)，滿足兩個(gè)特性· 父結(jié)點(diǎn)的鍵值總是大于或等于(小于或等于)任何一個(gè)子節(jié)點(diǎn)的鍵值 · 每個(gè)結(jié)點(diǎn)的左子樹(shù)和右子樹(shù)都是一個(gè)二叉堆 當(dāng)父結(jié)點(diǎn)的鍵值總是大于或等于任何一個(gè)子節(jié)點(diǎn)的鍵值時(shí)為最大堆。當(dāng)父結(jié)點(diǎn)的鍵值總是小于或等于任何一個(gè)子節(jié)點(diǎn)的鍵值時(shí)為最小堆。一般二叉樹(shù)

33、簡(jiǎn)稱為堆。堆的存儲(chǔ)一般都是數(shù)組來(lái)存儲(chǔ)堆，i結(jié)點(diǎn)的父結(jié)點(diǎn)下標(biāo)就為(i 1) / 2。它的左右子結(jié)點(diǎn)下標(biāo)分別為2 * i + 1和2 * i + 2。如第0個(gè)結(jié)點(diǎn)左右子結(jié)點(diǎn)下標(biāo)分別為1和2。存儲(chǔ)結(jié)構(gòu)如圖所示：堆結(jié)構(gòu).png 堆排序原理堆排序的時(shí)間復(fù)雜度為O(nlogn)· 算法原理（以最大堆為例）o 先將初始數(shù)據(jù)R1.n建成一個(gè)最大堆，此堆為初始的無(wú)序區(qū) o 再將關(guān)鍵字最大的記錄R1（即堆頂）和無(wú)序區(qū)的最后一個(gè)記錄Rn交換，由此得到新的無(wú)序區(qū)R1.n-1和有序區(qū)Rn，且滿足R1.n-1.keysRn.key o 由于交換后新的根R1可能違反堆性質(zhì)，故應(yīng)將當(dāng)前無(wú)序區(qū)R1.n-1調(diào)

34、整為堆。 o 重復(fù)2、3步驟，直到無(wú)序區(qū)只有一個(gè)元素為止。 · c+代碼實(shí)現(xiàn)1. /* 2.  * 將數(shù)組arr構(gòu)建大根堆 3.  * param arr 待調(diào)整的數(shù)組 4.  * param i   待調(diào)整的數(shù)組元素的下標(biāo) 5.  * param len 數(shù)組的長(zhǎng)度 6.  */ 7. void heap_adjust(int arr,

35、 int i, int len) 8.  9.     int child; 10.     int temp; 11.  12.     for (; 2 * i + 1 < len; i = child) 13.   &

36、#160;  14.         child = 2 * i + 1;  / 子結(jié)點(diǎn)的位置 = 2 * 父結(jié)點(diǎn)的位置 + 1 15.         / 得到子結(jié)點(diǎn)中鍵值較大的結(jié)點(diǎn) 16.     

37、;    if (child < len - 1 && arrchild + 1 > arrchild) 17.             child +; 18.         / 

38、;如果較大的子結(jié)點(diǎn)大于父結(jié)點(diǎn)那么把較大的子結(jié)點(diǎn)往上移動(dòng)，替換它的父結(jié)點(diǎn) 19.         if (arri < arrchild) 20.          21.             temp = arri; 2

39、2.             arri = arrchild; 23.             arrchild = temp; 24.          25.         else 26.             break; 27.      28.  29.  30. /* 31.  * 堆排序算法 32.  */ 33. void hea