php语言的7种基本的排序方法

时间:2021-05-26

本文总结了一下常用的7种排序方法,并用php语言实现。

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、冒泡排序

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、简单选择排序

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、希尔排序

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、快速排序

/* * 快速排序,快排思想:通过一趟排序将待排的记录分为两个独立的部分,其中一部分的记录的关键字均不大于 * 另一部分记录的关键字,然后再分别对这两部分记录继续进行快速排序,以达到整个序列有序,具体做法需要 * 每趟排序设置一个标准关键字和分别指向头一个记录的关键字和最后一个记录的关键字的指针。 * 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、堆排序

// 调整子堆的为大根堆的过程,$s为子堆的根的位置,$m为堆最后一个元素位置function heapAdjust(&$arr, $s, $m) { $tmp = $arr[$s]; // 在调整为大根堆的过程中可能会影响左子堆或右子堆 // for循环的作用是要保证子堆也是大根堆 for($j = 2*$s + 1; $j <= $m; $j = 2*$j + 1) { // 找到根节点的左右孩子中的最大者,然后用这个最大者与根节点比较, // 若大则进行调整,否则符合大根堆的 特点跳出循环 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); // 依次从子堆开始调整堆为大根堆 for($i = floor($len/2-1); $i >= 0; $i--) { heapAdjust($arr, $i, $len-1); } // 依次把根节点调换至最后一个位置,再次调整堆为大根堆,找到次最大值, // 依次类推得到一个有序数组 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、归并排序

// 分别将有序的$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); }}// 对一位数组$arr[0..n-1]中的元素进行两路归并function mergeSort($arr) { $len = count($arr); MSort($arr, $arr, 0, $len-1); return $arr;}

使用经验

  • 若排序的记录数目n较小时,可以采用直接插入排序和简单选择排序,当记录本身信息量较大时,用简单选择排序方法较好。
  • 若待排序记录按关键字基本有序,适合采用直接插入排序和冒泡排序。
  • 若n值较大时,可以采用快速排序、堆排序和归并排序。另外快速排序被认为是内部排序方法中最好的方法。
  • 以上就是本文的全部内容,希望对大家的学习有所帮助。

    声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。

    相关文章