7種php基本排序實現方法

本文總結了一下常用的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、冒泡排序

/*
  冒泡排序,冒泡排序思想：進行 n-1 趟冒泡排序， 每趟兩兩比較調整最大值到數組（子數組）末尾
*/
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值較大時，可以采用快速排序、堆排序和歸並排序。另外快速排序被認為是內部排序方法中最好的方法。

以上就是本文的全部內容，希望對大家的學習有所幫助。