本文總結(jié)了一下常用的7種排序方法，并用php語言實現(xiàn)。
1、直接插入排序
/* * 直接插入排序,插入排序的思想是：當前插入位置之前的元素有序， * 若插入當前位置的元素比有序元素最后一個元素大，則什么也不做， * 否則在有序序列中找到插入的位置，并插入 */function insertSort($arr) { $len = count($arr); for($i = 1; $i < $len; $i++) { if($arr[$i-1] > $arr[i]) { for($j = $i - 1;$j >= 0; $j-- ) { $tmp = $arr[$j+1]; if($tmp < $arr[$j]) { $arr[$j+1] = $arr[$j]; $arr[$j] = $tmp; }else{ break; } } } } return $arr;} 2、冒泡排序
/* 冒泡排序,冒泡排序思想：進行 n-1 趟冒泡排序， 每趟兩兩比較調(diào)整最大值到數(shù)組（子數(shù)組）末尾*/function bubbleSort($arr) { $len = count($arr); for($i = 1; $i < $len; $i++) { for($j = 0; $j < $len-$i; $j++) { if($arr[$j] > $arr[$j+1]) { $tmp = $arr[$j+1]; $arr[$j+1] = $arr[$j]; $arr[$j] = $tmp; } } } return $arr;} 3、簡單選擇排序
/* 簡單選擇排序, 簡單排序思想：從數(shù)組第一個元素開始依次確定從小到大的元素*/function selectSort($arr) { $len = count($arr); for($i = 0; $i < $len; $i++) { $k = $i; for($j = $i+1; $j < $len; $j++) { if($arr[$k] > $arr[$j]) { $k = $j; } } if($k != $i) { $tmp = $arr[$i]; $arr[$i] = $arr[$k]; $arr[$k] = $tmp; } } return $arr;} 4、希爾排序
/* 希爾排序,希爾排序原理：將數(shù)組按指定步長分隔成若干子序列，然后分別對子序列進行排序（在這是直接）*/function shellSort($arr) { $len = count($arr); $k = floor($len/2); while($k > 0) { for($i = 0; $i < $k; $i++) { for($j = $i; $j < $len, ($j + $k) < $len; $j = $j + $k) { if($arr[$j] > $arr[$j+$k]) { $tmp = $arr[$j+$k]; $arr[$j+$k] = $arr[$j]; $arr[$j] = $tmp; } } } $k = floor($k/2); } return $arr;} 5、快速排序
/* * 快速排序,快排思想：通過一趟排序?qū)⒋诺挠涗浄譃閮蓚€獨立的部分，其中一部分的記錄的關(guān)鍵字均不大于 * 另一部分記錄的關(guān)鍵字，然后再分別對這兩部分記錄繼續(xù)進行快速排序，以達到整個序列有序，具體做法需要 * 每趟排序設(shè)置一個標準關(guān)鍵字和分別指向頭一個記錄的關(guān)鍵字和最后一個記錄的關(guān)鍵字的指針。 * quickSort($arr, 0, count($arr) -1); */function quickSort(&$arr,$low,$high) { if($low < $high) { $i = $low; $j = $high; $primary = $arr[$low]; while($i < $j) { while($i < $j && $arr[$j] >= $primary) { $j--; } if($i < $j) { $arr[$i++] = $arr[$j]; } while($i < $j && $arr[$i] <= $primary) { $i++; } if($i < $j) { $arr[$j--] = $arr[$i]; } } $arr[$i] = $primary; quickSort($arr, $low, $i-1); quickSort($arr, $i+1, $high); }} 6、堆排序
/* 堆排序*/// 調(diào)整子堆的為大根堆的過程，$s為子堆的根的位置，$m為堆最后一個元素位置function heapAdjust(&$arr, $s, $m) { $tmp = $arr[$s]; // 在調(diào)整為大根堆的過程中可能會影響左子堆或右子堆 // for循環(huán)的作用是要保證子堆也是大根堆 for($j = 2*$s + 1; $j <= $m; $j = 2*$j + 1) { // 找到根節(jié)點的左右孩子中的最大者，然后用這個最大者與根節(jié)點比較， // 若大則進行調(diào)整，否則符合大根堆的 特點跳出循環(huán) if($j < $m && $arr[$j] < $arr[$j+1]) { $j++; } if($tmp >= $arr[$j] ) { break; } $arr[$s] = $arr[$j]; $s = $j; } $arr[$s] = $tmp;}// 堆排序function heapSort($arr) { $len = count($arr); // 依次從子堆開始調(diào)整堆為大根堆 for($i = floor($len/2-1); $i >= 0; $i--) { heapAdjust($arr, $i, $len-1); } // 依次把根節(jié)點調(diào)換至最后一個位置，再次調(diào)整堆為大根堆，找到次最大值， // 依次類推得到一個有序數(shù)組 for($n = $len-1; $n > 0; $n--) { $tmp = $arr[$n]; $arr[$n] = $arr[0]; $arr[0] = $tmp; heapAdjust($arr, 0, $n-1); } return $arr;} 7、歸并排序
/* 歸并排序,這里實現(xiàn)的是兩路歸并*/// 分別將有序的$arr1[s..m]、$arr2[m+1..n]歸并為有序的$arr2[s..n]function Merge(&$arr1, &$arr2, $s, $m, $n) { for($k = $s,$i = $s, $j = $m+1; $i <= $m && $j <= $n; $k++) { if($arr1[$i]<$arr1[$j]) { $arr2[$k] = $arr1[$i++]; }else { $arr2[$k] = $arr1[$j++]; } } if($i <= $m) { for(; $i <= $m; $i++) { $arr2[$k++] = $arr1[$i]; } } else if($j <= $n) { for(; $j <= $n; $j++) { $arr2[$k++] = $arr1[$j]; } }}// 遞歸形式的兩路歸并function MSort(&$arr1, &$arr2, $s, $t) { if($s == $t) { $arr2[$s] = $arr1[$s]; }else { $m = floor(($s+$t)/2); $tmp_arr = array(); MSort($arr1, $tmp_arr, $s, $m); MSort($arr1, $tmp_arr, $m+1, $t); Merge($tmp_arr, $arr2, $s, $m, $t); }}// 對一位數(shù)組$arr[0..n-1]中的元素進行兩路歸并function mergeSort($arr) { $len = count($arr); MSort($arr, $arr, 0, $len-1); return $arr;} 使用經(jīng)驗
若排序的記錄數(shù)目n較小時，可以采用直接插入排序和簡單選擇排序，當記錄本身信息量較大時，用簡單選擇排序方法較好。
若待排序記錄按關(guān)鍵字基本有序，適合采用直接插入排序和冒泡排序。
若n值較大時，可以采用快速排序、堆排序和歸并排序。另外快速排序被認為是內(nèi)部排序方法中最好的方法。
以上就是本文的全部內(nèi)容，希望對大家的學習有所幫助。
