数据结构与算法（一）——排序
生活随笔
收集整理的這篇文章主要介紹了
数据结构与算法（一）——排序
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
雖然之前學過數(shù)據(jù)結構，但是已時隔四年，大概四月份復習了一遍，但是很多概念也是一知半解，所以重新整理知識點和運行代碼的方式來鞏固知識。
引言
排序：是計算機程序設計中的一種重要操作，功能是將一個數(shù)據(jù)元素的任意序列重新排列成一個按關鍵字的有序序列。
根據(jù)待排序記錄的存儲器的不同可分為
各個排序算法的性能比較
冒泡排序
算法說明
冒泡排序是一種交換排序。那什么是交換排序呢？
交換排序：兩兩比較待排序的關鍵字，并交換不滿足次序要求的那對數(shù)，直到整個表都滿足次序要求為止。
基本思想：通過相鄰記錄兩兩比較交換的方式，找到每次迭代中數(shù)據(jù)的最大值，最終達到排序的目的。
算法描述：
- 首先將第一個記錄的關鍵字與第二個記錄的關鍵字進行比較，若為逆序（L.r[1].key>L.r[2].key），則將兩個記錄交換，然后比較第二個記錄和第三個記錄的關鍵字，依次類推，直到第n-1個記錄和第n個記錄進行比較為止。這是一趟排序。
- 然后進行第二趟排序，對前n-1個記錄進行同樣的操作。重復這樣的操作。
- 直到冒泡排序在一趟拍訊中沒有進行過交換記錄的操作為止。
這個算法的名字由來是因為越小的元素會經(jīng)由交換慢慢“浮”到數(shù)列的頂端，故名。
用例說明
代碼實現(xiàn)
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | <?php $list = array(49, 38, 65, 97, 76, 13, 27, 49); $res = BubbleSort($list); print_r($res); function BubbleSort($list) { $len = count($list); for ($i = 0; $i < $len; $i++) { for ($j = $len-1; $j > $i; $j--) { if ($list[$j-1] > $list[$j]) { swap($list, $j-1, $j); $bChange = true; } } } echo $k; return $list; } function swap(&$list, $i, $j) { $temp = $list[$i]; $list[$i] = $list[$j]; $list[$j] = $temp; } ?> |
輸出：
| 1 2 3 4 5 6 7 8 9 10 11 | Array ( [0] => 13 [1] => 27 [2] => 38 [3] => 49 [4] => 49 [5] => 65 [6] => 76 [7] => 97 ) |
快速排序
算法說明
快速排序是冒泡排序的改進，整個快速排序的過程是一個遞歸的過程。
基本思想：通過一趟排序將待排記錄分割成獨立兩部分，其中一部分記錄的關鍵字均比另一部分記錄的關鍵字小，則可分別對著兩部分記錄繼續(xù)記性排序，以達到整個序列有序。
算法描述：
- 一趟快速排序的步驟：
- 設兩個指針low和high，設樞軸記錄的關鍵字為pivotkey；
- 先從high所指向的位置向前搜索找到第一個小于pivotkey的記錄和樞軸記錄互相交換；
- 然后從low所指向的位置向后搜索找到第一個大于pivotkey的記錄和樞軸記錄互相交換；
- 重復前面兩步驟，知道low=high為止。
- 取當前的pivotkey記錄所在的位置（樞軸位置），將整個記錄分割為兩個子序列，分別進行快速排序；
- 直到待排序列中只有一個記錄為止。
用例說明
代碼實現(xiàn)
先將樞軸記錄暫存在r[0]的位置上，排序過程只作r[row]或者r[high]的單向移動，知道一趟排序結束后，再將樞軸記錄移至正確的位置上。
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 | #include<iostream> using namespace std; // 聲明快排函數(shù) void quickSort(int a[],int,int); int main() { int array[]={34,65,12,43,67,5,78,10,3,70},k; int len=sizeof(array)/sizeof(int); cout<<"The orginal arrayare:"<<endl; for(k=0;k<len;k++) cout<<array[k]<<","; cout<<endl; quickSort(array,0,len-1); cout<<"The sorted arrayare:"<<endl; for(k=0;k<len;k++) cout<<array[k]<<","; cout<<endl; system("pause"); return 0; } void quickSort(int s[], int l, int r) { if (l< r) { int i = l, j = r, x = s[l]; while (i < j) { while(i < j && s[j]>= x) // 從右向左找第一個小于x的數(shù) j--; if(i < j) s[i++] = s[j]; while(i < j && s[i]< x) // 從左向右找第一個大于等于x的數(shù) i++; if(i < j) s[j--] = s[i]; } s[i] = x; quickSort(s, l, i - 1); // 遞歸調(diào)用 quickSort(s, i + 1, r); } } |
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 | <?php $list = array(49, 38, 65, 97, 76, 13, 27, 49);//這個用例輸出的是null //$list = array(9, 1, 5, 8, 3, 7, 4, 6, 2);//這個用例測試結果是對的 $res = QuickSort($list); print_r($res); print_r($list); function QuickSort($list) { $len = count($list); Qsort($list, 0, $len-1); return $list; } function Qsort(&$list, $low, $high) { if ($low < $high) { $pivot = Partition($list, $low, $high); Qsort($list, $low, $pivot-1); Qsort($list, $pivot+1, $high); } } function Partition(&$list, $low, $high) { $pvalue = $list[$low]; while ($low < $high) { while ($low < $high && $list[$high] > $pvalue) { $high--; } swap($list, $low, $high); while ($low < $high && $list[$low] < $pvalue) { $low++; } swap($list, $low, $high); } return $low; } function swap(&$list, $i, $j) { $temp = $list[$i]; $list[$i] = $list[$j]; $list[$j] = $temp; } ?> |
直接插入排序
算法說明
直接插入排序是一種最簡單的排序方法，它的基本操作是將一個記錄儀插入到已排好序的有序表中，從而得到一個新的、記錄數(shù)增1的有序表。
算法描述：
- 先取代排序序列中的第一個記錄作為一個有序序列；
- 取第二個記錄，在這個有序序列依次查找比它小的最大關鍵字，將該記錄插入到查找的關鍵字位置后面；
- 取第i個記錄按同種方法插入到當前有序序列；
- 將最后一個記錄插入，即可完成排序。
用例說明
代碼實現(xiàn)
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | <?php $list = array(49, 38, 65, 97, 76, 13, 27, 49); $res = InsertionSort($list); print_r($res); function InsertionSort($list){ $len = count($list); for ($i = 1; $i < $len; $i++) { if ($list[$i] < $list[$i-1]) { $target = $list[$i]; for($j = $i-1; $j >= 0 && $list[$j] >= $target; $j--) { $list[$j+1] = $list[$j]; } $list[$j+1] = $target; } } return $list; } ?> |
希爾排序
算法說明
希爾排序又稱“縮小增量排序”，也屬于插入排序類方法，但時間效率更高。希爾排序的一個特點：子序列的構成不是簡單地“逐段分割”，而是將相隔某個“增量”的記錄組成一個子序列。
算法描述：
- 將整個待排序序列分割成若干個子序列
- 對每個子序列分別進行直接插入排序
- 待每個子序列中的記錄有序時，再縮小增量重新分割子序列，重復上一步操作，直到增量為1，進行最后一次排序后即完成排序。
這個算法，主要是通過增量劃分子序列，使序列基本有序，減小插入排序的復雜度。
需注意的是，到目前為止，尚未有人求得一種最好的增量序列，但是也有一些局部結論。增量序列可以用多種取法，但需注意：應使增量序列中的值沒有除1以外的公因數(shù)，并且最后一個增量值必須等于1。
用例說明
代碼實現(xiàn)
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | <?php $list = array(49, 38, 65, 97, 76, 13, 27, 49); $res = ShellSort($list); print_r($res); function ShellSort($list) { $len = count($list); $increment = $len; do { $increment = floor($increment/3) + 1; for ($i = $increment; $i < $len; $i++) { if ($list[$i] < $list[$i-$increment]) { $target = $list[$i]; for ($j = $i-$increment; $j >= 0 && $list[$j] > $target; $j -= $increment) { $list[$j+$increment] = $list[$j]; } $list[$j+$increment] = $target; } } }while($increment > 1); return $list; } ?> |
簡單選擇排序
算法說明
簡單選擇排序是一種選擇排序。每一趟在n-i+1（i=1,2,…,n-1）個記錄中選擇關鍵字最小的記錄作為有序序列的第i個記錄。
算法描述
- 先從n個記錄（待排序列）中找到最小的關鍵字，作為第一個記錄
- 隨后在剩下的n-1（n-i+1）子序列中再尋找最小關鍵字，作為第2（i）個記錄
- 依次類推，直到剩下最后的一個記錄（即最大關鍵字）為止。
用例說明
代碼實現(xiàn)
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | <?php $list = array(49, 38, 65, 97, 76, 13, 27, 49); $res = SelectionSort($list); print_r($res); function SelectionSort($list) { $len = count($list); for ($i = 0; $i < $len; $i++) { $min = $i; for ($j = $i; $j < $len; $j++) { if ($list[$min] > $list[$j]) { $min = $j; } } if ($min != $i) { swap($list, $min, $i); } } return $list; } function swap(&$list, $i, $j) { $temp = $list[$i]; $list[$i] = $list[$j]; $list[$j] = $temp; } ?> |
樹形選擇排序
算法說明
樹形選擇排序，又稱“錦標賽排序”，是一種按照錦標賽的思想進行選擇排序的方法，是對簡單選擇排序的一種改進。
算法描述
- 首先對n個記錄的關鍵字進行兩兩比較，選出較小者
- 然后在其[n/2]個較小者之間再進行兩兩比較，再選出較小者
- 如此重復，知道選出最小關鍵字的記錄為止
- 將最小關鍵字輸出，然后根據(jù)關系的可傳遞性，選出次小關鍵字，依次輸出，直到輸出所有的記錄。
用例說明
堆排序
堆：一棵順序存儲的完全二叉樹。
小頂堆：其中每個結點的關鍵字都不大于其孩子結點的關鍵字，這樣的堆稱為小頂堆（小根堆）。
大頂堆：其中每個結點的關鍵字都不小于其孩子結點的關鍵字，這樣的堆稱為大頂堆（大根堆）。
舉例來說
對于n個元素的序列{R0, R1, … , Rn}當且僅當滿足下列關系之一時，稱之為堆：
(1) Ri <= R2i+1 且 Ri <= R2i+2 (小頂堆)
(2) Ri >= R2i+1 且 Ri >= R2i+2 (大頂堆)
其中i=1,2,…,n/2向下取整
算法說明
- 根據(jù)初始數(shù)組去構造初始堆（構建一個完全二叉樹，保證所有的父結點都比它的孩子結點數(shù)值大）。
- 每次交換第一個和最后一個元素，輸出最后一個元素（最大值），然后把剩下元素重新調(diào)整為大頂堆。
- 當輸出完最后一個元素后，這個數(shù)組已經(jīng)是按照從小到大的順序排列了。
用例說明
代碼實現(xiàn)
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 | <?php $list = array(49, 38, 65, 97, 76, 13, 27, 49); $res = HeapSort($list); print_r($res); function HeapSort($list) { $len = count($list); for ($i = floor(($len-2)/2); $i >= 0; $i--) { createHeap($list, $i, $len-1); } for ($i = $len-1; $i >=0 ; $i--) { swap($list, $i, 0); createHeap($list, 0, $i-1); } return $list; } function createHeap(&$list, $i, $j) { $target = $list[$i]; for ($m=$i*2+1; $m <= $j ; $m = $m*2+1) { if ($m < $j && $list[$m] < $list[$m+1]) { $m++; } if ($target > $list[$m]) { break; } $list[$i] = $list[$m]; $i = $m; } $list[$i] = $target; } function swap(&$list, $i, $j) { $temp = $list[$i]; $list[$i] = $list[$j]; $list[$j] = $temp; } |
歸并排序
算法說明
歸并排序是將兩個或者兩個以上的有序表組合成一個新的有序表。
歸并排序是建立在歸并操作上的一種有效的排序算法，該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。
將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。
算法描述
- 將待排序序列R[0…n-1]看成是n個長度為1的有序序列，將相鄰的有序表成對歸并，得到n/2個長度為2的有序表；
- 將這些有序序列再次歸并，得到n/4個長度為4的有序序列
- 如此反復進行下去，最后得到一個長度為n的有序序列。
歸并排序其實要做兩件事：
（1）“分解”——將序列每次折半劃分。
（2）“合并”——將劃分后的序列段兩兩合并后排序。
用例說明
代碼實現(xiàn)
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 | <?php $list = array(49, 38, 65, 97, 76, 13, 27, 49); $res = MergeSort($list); print_r($res); function MergeSort(&$list) { $len = count($list); $res = array(); Msort($list, $res, 0, $len-1); return $res; } function MSort(&$list, &$res, $s, $t) { if ($s == $t) { $res[$s] = $list[$s]; }else{ $m = floor(($s + $t)/2); $temp = array(); //新建一個空數(shù)組 MSort($list, $temp, $s, $m); MSort($list, $temp, $m+1, $t); Merge($temp, $res, $s, $m, $t); } } function Merge(&$temp, &$res, $s, $m, $t) { for ($k = $s, $j = $m+1; $s <= $m && $j <= $t; $k++) { if ($temp[$s] < $temp[$j]) { $res[$k] = $temp[$s]; $s++; }else{ $res[$k] = $temp[$j]; $j++; } } if ($s <= $m) { for ($l = 0; $l <= $m-$s ; $l++) { $res[$k+$l] = $temp[$s+$l]; } } if ($j <= $t) { for ($l = 0; $l <= $t-$j ; $l++) { $res[$k+$l] = $temp[$j+$l]; } } } ?> |
基數(shù)排序
算法說明
代碼實現(xiàn)
參考：
總結
以上是生活随笔為你收集整理的数据结构与算法（一）——排序的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： [转] Cisco路由器DNS配置
- 下一篇： Java 集合类图(转)