10大排序算法对比

冒泡排序
算法描述
冒泡排序是一种交换排序，它的基本思想是：对待排序记录从后往前（逆序）进行多遍扫描，当发现相邻两条记录的次序与排序要求的规则不符时，就将这两个记录进行交换。这样，值较小的记录将逐渐从后面向前移动，就像气泡在水中向上浮一样。
实现步骤
假设需要排序的记录有n 个，其值保存在数组A 中，使用冒泡排序法，需对数组A进行n-1 次扫描，完成排序操作。具体过程如下：
1. 将A[n-1] 与A[n] 进行比较,若A[n] < A[n-1] ，则交换两元系的位置。
2. 修改数组下标，使需要比较的两个元素为A[n-1] 和A[n-2] ，重复步骤(1)，对这两个元素进行比较。重复这个过程，直到对A[1] 和A[0] 进行比较完为止。完成第1 遍扫描。
3. 经过第1 遍扫描后，最小的元素已经像气泡一样“浮”到最上面，即位于元素A[0] 中了。接下来重复前面的步骤，进行第2 遍扫描，只是扫描结束位置到A[2] 与A[1] 进行比较完为止（因为A[0]中已经是最小的数据，不用再进行比较）。
4. 通过n-1 遍扫描，前n-1 个数都已经排序完成，最后一个元素A[n] 肯定就是最大的数了。至此，完成排序操作。

图片
代码实现
复制
/**
* 冒泡排序
* @param array $arr
*/
function bubbleSort(array &$arr) : void{
  $length = count($arr);
  // 外层循环，从数组首部开始，每完成一次循环，可确定$arr[$i] 位置的元素
  for ($i = 0; $i < $length; $i++){
    // 内层循环，$j 从后往前循环
    for ($j = $length - 1; $j > $i; $j--) {
      // 若前面的值大于后面的值，则互换位置
      if ($arr[$j] < $arr[$j - 1]) {
        // 互换数组两个位置的值
        [$arr[$j], $arr[$j - 1]] = [$arr[$j - 1], $arr[$j]];
      }
    }
  }
}
希尔排序
算法描述
希尔排序可以说是插入排序的一种变种。无论是插入排序还是冒泡排序，如果数组的最大值刚好是在第一位，要将它挪到正确的位置就需要 n - 1 次移动。
实现步骤
希尔排序的思想是采用插入排序的方法，先让数组中任意间隔为 h 的元素有序，刚开始 h 的大小可以是 h = n / 2,接着让 h = n / 4，让 h 一直缩小，当 h = 1 时，也就是此时数组中任意间隔为1的元素有序，此时的数组就是有序的了。

代码实现
复制
function shell_sort(array $arr){
      // 将$arr按升序排列
      $len = count($arr);
      $f = 3;// 定义因子
      $h = 1;// 最小为1
      while ($h < $len/$f){
          $h = $f*$h + 1; // 1, 4, 13, 40, 121, 364, 1093, ...
      }
      while ($h >= 1){  // 将数组变为h有序
          for ($i = $h; $i < $len; $i++){  // 将a[i]插入到a[i-h], a[i-2*h], a[i-3*h]... 之中 （算法的关键
              for ($j = $i; $j >= $h;  $j -= $h){
                  if ($arr[$j] < $arr[$j-$h]){
                      $temp = $arr[$j];
                      $arr[$j] = $arr[$j-$h];
                      $arr[$j-$h] = $temp;
                  }
                  //print_r($arr);echo '
'; // 打开这行注释，可以看到每一步被替换的情形
              }
          }
          $h = intval($h/$f);
      }
      return $arr;
  }

选择排序
算法描述
选择排序是通过n-i 次关键字间的比较，从n-i+1 个记录中选出关键字最小的记录，并和第i ( 1  $arr[$j]) {
                // 互换数组两个位置的值
                [$arr[$j], $arr[$i]] = [$arr[$i], $arr[$j]];
            }
        }
     }
}

插入排序
算法描述
插入排序是通过构建有序序列，从未排序数据中选择一个元素，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在从后向前扫描过程中，需要把已排序元素逐个向后移动，为最新元素提供插入空间。
实现步骤
1. 对于第1 个元素，因为没有比较，将其作为已经有序的序列。
2. 从数组中获取下一个元素，在已经排序的元素序列中从后向前扫描，并进行判断。
3. 若排序序列的元素大于新元素，则将该元素向后移动一位。
4. 重复步骤(3)，直到在已排序的元素中找到小于或者等于新元素的元素，将新元素插入到该元素的后面。
5. 重复步骤(2) ~ (4)，直到完成排序。

图片
代码实现
复制
/**
* 插入排序
* @param array $arr
*/
function insertionSort(array &$arr) : void{
    $length = count($arr);
    // 从数组首部开始排序，每完成一次循环，可确定一个元素的位置
    for ($i = 0; $i < $length - 1; $i++) {
        // 内层循环从$i + 1 个元素开始，一位一位向前比较
        // 若前面的值比自己大，则替换，直到前面的值比自己小了，停止循环
        for ($j = $i + 1; $j > 0; $j--) {
            if ($arr[$j] >= $arr[$j - 1]) {
                break;
            }
            [[$arr[$j], $arr[$j - 1]]] = [[$arr[$j - 1], $arr[$j]]];
        }
     }
}
/**
* 插入排序- 方法2
* @param array $arr
*/
function insertionSort2(array &$arr) : void{
    $length = count($arr);
    // 从数组首部开始排序，每完成一次循环，可确定一个元素的位置
    for ($i = 0; $i < $length - 1; $i++) {
        // 从第二个元素开始，选择固定位置的值作为基准值
        $currentVal = $arr[$i + 1];
        // 初始键位于选定值的前一个位置
        $preIdx = $i;
        // 拿基准值一步一步向前比较，直到基准值比前面的值小，则两值互换位置
        while ($preIdx >= 0 && $currentVal < $arr[$preIdx]) {
            $arr[$preIdx + 1] = $arr[$preIdx];
            $arr[$preIdx] = $currentVal;
            $preIdx--;
        }
    }
}

快速排序
算法描述
快速排序是通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的。
实现步骤
快速排序使用分治策略来把待排序数据序列分为两个子序列，具体步骤如下：
1. 从数列中挑出一个元素，以该元素为“基准”。
2. 扫描一遍数列，将所有比“基准”小的元素排在基准前面，所有比“基准”大的元素排在基准后面。
3. 通过递归，将各子序列划分为更小的序列，直到把小于基准值元素的子数列和大于基谁值元素的子数列排序。




贴主:wecode于2024_09_01 13:27:47编辑