PHP implements four commonly used sorting algorithms

PHP implements four commonly used sorting algorithms_PHP tutorial

WBOY

Release： 2016-07-13 10:33:26

Original

887 people have browsed it

Insertion Sort, Selection Sort, Bubble Sort and Quick Sort are the sorting algorithms we often use. The following are the basic ideas of these algorithms and the corresponding PHP implementation codes.

The basic idea of Insertion Sort is: each time a record to be sorted is inserted into the appropriate position in the previously sorted sub-file according to its key size, until all records are inserted.

//插入排序（一维数组）
function insert_sort($arr){
    $count = count($arr);
    for($i=1; $i<$count; $i++){
        $tmp = $arr[$i];
        $j = $i - 1;
        while($arr[$j] > $tmp){
            $arr[$j+1] = $arr[$j];
            $arr[$j] = $tmp;
            $j--;
         }
     }
    return $arr;
}

Copy after login

The basic idea of Selection Sort is: in each pass, the record with the smallest keyword is selected from the records to be sorted, and the order is placed at the end of the sorted sub-file until all records are sorted.

//选择排序（一维数组）
function select_sort($arr){
    $count = count($arr);
    for($i=0; $i<$count; $i++){
        $k = $i;
        for($j=$i+1; $j<$count; $j++){
            if ($arr[$k] > $arr[$j])
                $k = $j;
            if ($k != $i){
                $tmp = $arr[$i];
                $arr[$i] = $arr[$k];
                $arr[$k] = $tmp;
             }
         }
     }
    return $arr;
}

Copy after login

The basic idea of bubble sorting is: compare the keywords of the records to be sorted pairwise, and when it is found that the order of the two records is reversed, they are exchanged until there are no records in the reverse order.

//冒泡排序（一维数组）
function bubble_sort($array){
    $count = count($array);
    if ($count <= 0) return false;
    for($i=0; $i<$count; $i++){
        for($j=$count-1; $j>$i; $j--){
            if ($array[$j] < $array[$j-1]){
                $tmp = $array[$j];
                $array[$j] = $array[$j-1];
                $array[$j-1] = $tmp;
             }
         }
     }
    return $array;
}

Copy after login

Quick sort is essentially the same as bubble sort, and is an application of exchange sort. So the basic idea is the same as the bubble sort above.

//快速排序（一维数组） 
function quick_sort($array){
  if (count($array) <= 1) return $array; 
  $key = $array[0];
  $left_arr = array();
  $right_arr = array();
  for ($i=1; $i<count($array); $i++){
    if ($array[$i] <= $key)
      $left_arr[] = $array[$i];
    else
      $right_arr[] = $array[$i];
  }
  $left_arr = quick_sort($left_arr);
  $right_arr = quick_sort($right_arr); 
  return array_merge($left_arr, array($key), $right_arr);
}

Copy after login