PHP 정렬 알고리즘 Quick Sort(Quick Sort) 및 최적화

이 글에서는 주로 PHP 정렬 알고리즘인 Quick Sort(퀵 정렬)와 그에 따른 최적화 알고리즘을 소개하며, PHP Quick Sort의 원리와 구현 방법을 예제 형식으로 분석하고, 다양한 최적화 기법과 동작 시 주의사항을 분석합니다.

이 문서에서는 PHP 정렬 알고리즘인 Quick Sort(Quick Sort)와 해당 최적화 알고리즘을 예제와 함께 설명합니다. 참조를 위해 모든 사람과 공유하세요. 세부 사항은 다음과 같습니다.

기본 아이디어:

Quicksort는 버블 정렬을 개선한 것입니다. 그의 기본 아이디어는 정렬할 레코드를 한 번의 정렬을 통해 두 개의 독립적인 부분으로 나누는 것입니다. 그러면 레코드의 두 부분이 빠르게 개별적으로 정렬될 수 있습니다. 전체 정렬 프로세스는 전체 시퀀스를 정렬하는 목적을 달성하기 위해 재귀적으로 수행될 수 있습니다.

기본 알고리즘 단계:

예:

지금 정렬할 레코드가 다음과 같다고 가정합니다.

6 2 7 3 8 9

첫 번째 단계는 변수 $low를 지정하는 것입니다. $high는 마지막 레코드를 가리키며, $pivot는 정렬할 레코드의 첫 번째 요소(반드시 첫 번째 요소일 필요는 없음)에 대한 피벗으로 지정됩니다. 여기서는

$low = 0;
$high = 5;
$pivot = 6;

두 번째입니다. $pivot보다 작은 모든 숫자를 $pivot의 왼쪽으로 이동하여 $high부터 시작하여 오른쪽에서 왼쪽으로 보면서 $high 변수의 값을 지속적으로 감소시키면서 6보다 작은 숫자를 찾을 수 있습니다. 첫 번째 첨자 3의 데이터가 6보다 작으므로 데이터 3은 첨자 0의 위치($low가 가리키는 위치)로 이동하고, 첨자 0의 데이터 6은 첨자 3으로 이동하고, 첫 번째 비교가 완료되었습니다:

3 2 7 6 8 9

//这时候,$high 减小为 3
$low = 0;
$high = 3;
$pivot = 6;

세 번째 단계는 두 번째 비교를 시작하는 것입니다. 이번에는 $pivot보다 큰 것을 찾고 앞에서부터 살펴봅니다. 뒤쪽에. 변수 $low를 증가시키고 아래 첨자 2의 데이터가 $pivot보다 큰 첫 번째 데이터임을 확인하므로 아래 첨자 2($low가 가리키는 위치)에 데이터 7을 사용하고 아래 첨자 3($low가 가리키는 위치)에 데이터 7을 사용합니다. at by $high) 6개의 데이터가 교환되고 데이터 상태는 다음과 같은 테이블이 됩니다.

3 2 6 7 8 9

//这时候,$high 减小为 3
$low = 2;
$high = 3;
$pivot = 6;

두 번째와 세 번째 단계를 완료하는 것을 사이클 완료라고 합니다. .

네 번째 단계(즉, 다음 주기 시작)는 두 번째 단계의 과정을 모방합니다.

다섯 번째 단계는 세 번째 단계의 과정을 따라하는 것입니다.

두 번째 루프를 실행한 후 데이터 상태는 다음과 같습니다.

3 2 6 7 8 9

//这时候,$high 减小为 3
$low = 2;
$high = 2;
$pivot = 6;

이 단계에서 $low 및 $high "만남"을 발견했습니다. 아래첨자 2를 가리킨다. 이로써 첫 번째 비교가 끝났습니다. 결과는 다음과 같습니다. $pivot(=6) 왼쪽에 있는 모든 숫자는 그보다 작고, $pivot 오른쪽에 있는 모든 숫자는 그보다 큽니다.

그런 다음 데이터 {3, 2} 및 {7, 8, 9}를 $pivot 양쪽에 그룹화하고 더 이상 그룹화가 불가능할 때까지 위의 프로세스를 각각 수행합니다.

참고: 빠른 정렬의 첫 번째 단계는 최종 결과를 직접 얻지 않으며 k보다 크고 k보다 작은 숫자만 k의 양쪽으로 나눕니다. 최종 결과를 얻으려면 첨자 2의 양쪽에 있는 배열에 대해 이 단계를 다시 수행한 다음 배열이 더 이상 분해될 수 없을 때까지(단 하나의 데이터만) 배열을 분해하여 올바른 결과를 얻어야 합니다.

알고리즘 구현:

//交换函数
function swap(array &$arr,$a,$b){
  $temp = $arr[$a];
  $arr[$a] = $arr[$b];
  $arr[$b] = $temp;
}
//主函数：
function QuickSort(array &$arr){
  $low = 0;
  $high = count($arr) - 1;
  QSort($arr,$low,$high);
}

기본 함수에서 빠른 정렬의 첫 번째 단계는 전체 배열을 정렬하므로 시작점은 $low=0,$high=count( $arr)-1. $low=0,$high=count($arr)-1。

然后 QSort()

그러면 QSort() 함수는 재귀 호출 프로세스이므로 캡슐화됩니다.

function QSort(array &$arr,$low,$high){
  //当 $low >= $high 时表示不能再进行分组，已经能够得出正确结果了
  if($low < $high){
    $pivot = Partition($arr,$low,$high); //将$arr[$low...$high]一分为二，算出枢轴值
    QSort($arr,$low,$pivot - 1); //对低子表（$pivot左边的记录）进行递归排序
    QSort($arr,$pivot + 1,$high); //对高子表（$pivot右边的记录）进行递归排序
  }
}

위의 QSort() 함수에서 Partition() 함수를 볼 수 있습니다. 첫 번째 키워드를 선택하는 등 키워드 중 하나를 선택하는 기능이기 때문에 전체 코드의 핵심입니다. 그런 다음 왼쪽의 값이 그것보다 작고 오른쪽의 값이 그것보다 커지도록 특정 위치에 배치하려고 최선을 다합니다. 이러한 키워드를 피벗(Pivot)이라고 부릅니다.

코드로 직접 이동:

//选取数组当中的一个关键字，使得它处于数组某个位置时，左边的值比它小，右边的值比它大，该关键字叫做枢轴
//使枢轴记录到位，并返回其所在位置
function Partition(array &$arr,$low,$high){
  $pivot = $arr[$low];  //选取子数组第一个元素作为枢轴
  while($low < $high){ //从数组的两端交替向中间扫描（当 $low 和 $high 碰头时结束循环）
    while($low < $high && $arr[$high] >= $pivot){
      $high --;
    }
    swap($arr,$low,$high); //终于遇到一个比$pivot小的数，将其放到数组低端
    while($low < $high && $arr[$low] <= $pivot){
      $low ++;
    }
    swap($arr,$low,$high); //终于遇到一个比$pivot大的数，将其放到数组高端
  }
  return $low;  //返回high也行，毕竟最后low和high都是停留在pivot下标处
}

전체 결합 코드는 다음과 같습니다.

function swap(array &$arr,$a,$b){
  $temp = $arr[$a];
  $arr[$a] = $arr[$b];
  $arr[$b] = $temp;
}
function Partition(array &$arr,$low,$high){
  $pivot = $arr[$low];  //选取子数组第一个元素作为枢轴
  while($low < $high){ //从数组的两端交替向中间扫描
    while($low < $high && $arr[$high] >= $pivot){
      $high --;
    }
    swap($arr,$low,$high); //终于遇到一个比$pivot小的数，将其放到数组低端
    while($low < $high && $arr[$low] <= $pivot){
      $low ++;
    }
    swap($arr,$low,$high); //终于遇到一个比$pivot大的数，将其放到数组高端
  }
  return $low;  //返回high也行，毕竟最后low和high都是停留在pivot下标处
}
function QSort(array &$arr,$low,$high){
  if($low < $high){
    $pivot = Partition($arr,$low,$high); //将$arr[$low...$high]一分为二，算出枢轴值
    QSort($arr,$low,$pivot - 1);  //对低子表进行递归排序
    QSort($arr,$pivot + 1,$high); //对高子表进行递归排序
  }
}
function QuickSort(array &$arr){
  $low = 0;
  $high = count($arr) - 1;
  QSort($arr,$low,$high);
}

알고리즘을 호출합니다.

$arr = array(9,1,5,8,3,7,4,6,2);
QuickSort($arr);
var_dump($arr);

실행 결과:

르레 ee

복잡도 분석:

최적의 상황, 즉 숫자 축이 전체 배열의 중간 값으로 선택되면 배열이 매번 두 부분으로 나누어집니다. 따라서 최적의 경우 시간 복잡도는 O(nlogn)입니다(힙 정렬 및 병합 정렬과 동일). 🎜

最坏的情况下，待排序的序列是正序或逆序的，那么在选择枢轴的时候只能选到边缘数据，每次划分得到的比上一次划分少一个记录，另一个划分为空，这样的情况的最终时间复杂度为 O(n^2).

综合最优与最差情况，平均的时间复杂度是 O(nlogn).

快速排序是一种不稳定排序方法。

由于快速排序是个比较高级的排序，而且被列为20世纪十大算法之一。。。。如此牛掰的算法，我们还有什么理由不去学他呢！

尽管这个算法已经很牛掰了，但是上面的算法程序依然有改进的地方，下面具体讨论一下

快速排序算法优化

优化一：优化选取枢轴：

在前面的复杂度分析的过程中，我们看到最坏的情况无非就是当我们选中的枢轴是整个序列的边缘值。比如这么一个序列：

9   1   5   8   3   7   4   6   2

按照习惯我们选择数组的第一个元素作为枢轴，则 $pivot = 9，在一次循环下来后划分为{1，5，8，3，7，4，6，2} 和{ }（空序列），也就是每一次划分只得到少一个记录的子序列，而另一个子序列为空。最终时间复杂度为 O(n^2)。最优的情况是当我们选中的枢轴是整个序列的中间值。但是我们不能每次都去遍历数组拿到最优值吧？那么就有了一下解决方法：

1、随机选取：随机选取 $low 到 $high 之间的数值，但是这样的做法有些撞大运的感觉了，万一没撞成功呢，那上面的问题还是没有解决。

2、三数取中法：取三个关键字先进行排序，取出中间数作为枢轴。这三个数一般取最左端、最右端和中间三个数，也可以随机取三个数。这样的取法得到的枢轴为中间数的可能性就大大提高了。由于整个序列是无序的，随机选择三个数和从左中右端取出三个数其实就是同一回事。而且随机数生成器本身还会带来时间的开销，因此随机生成不予考虑。

出于这个想法，我们修改 Partition() 函数：

function Partition(array &$arr,$low,$high){
  $mid = floor($low + ($high - $low) / 2);  //计算数组中间的元素的下标
  if($arr[$low] > $arr[$high]){
    swap($arr,$low,$high);
  }
  if($arr[$mid] > $arr[$high]){
    swap($arr,$mid,$high);
  }
  if($arr[$low] < $arr[$mid]){
    swap($arr,$low,$mid);
  }
  //经过上面三步之后，$arr[$low]已经成为整个序列左中右端三个关键字的中间值
  $pivot = $arr[$low];
  while($low < $high){  //从数组的两端交替向中间扫描（当 $low 和 $high 碰头时结束循环）
    while($low < $high && $arr[$high] >= $pivot){
      $high --;
    }
    swap($arr,$low,$high); //终于遇到一个比$pivot小的数，将其放到数组低端
    while($low < $high && $arr[$low] <= $pivot){
      $low ++;
    }
    swap($arr,$low,$high); //终于遇到一个比$pivot大的数，将其放到数组高端
  }
  return $low;  //返回high也行，毕竟最后low和high都是停留在pivot下标处
}

三数取中法对于小数组有很大可能能沟得出比较理想的 $pivot，但是对于大数组就未必了，因此还有个办法是九数取中法。。。。。。

优化二：优化不必要的交换：

现在假如有个待排序的序列如下：

5   1   9   3   7   4   8   6   2

根据三数取中法我们取 5 7 2 中的 5 作为枢轴。

当你按照快速排序算法走一个循环，你会发现 5 的下标变换顺序是这样的：0 -> 8 -> 2 -> 5 -> 4，但是它的最终目标就是 4 的位置，当中的交换其实是不需要的。

根据这个思想，我们改进我们的 Partition() 函数:

function Partition(array &$arr,$low,$high){
  $mid = floor($low + ($high - $low) / 2);  //计算数组中间的元素的下标
  if($arr[$low] > $arr[$high]){
    swap($arr,$low,$high);
  }
  if($arr[$mid] > $arr[$high]){
    swap($arr,$mid,$high);
  }
  if($arr[$low] < $arr[$mid]){
    swap($arr,$low,$mid);
  }
  //经过上面三步之后，$arr[$low]已经成为整个序列左中右端三个关键字的中间值
  $pivot = $arr[$low];
  $temp = $pivot;
  while($low < $high){  //从数组的两端交替向中间扫描（当 $low 和 $high 碰头时结束循环）
    while($low < $high && $arr[$high] >= $pivot){
      $high --;
    }
    //swap($arr,$low,$high); //终于遇到一个比$pivot小的数，将其放到数组低端
    $arr[$low] = $arr[$high];  //使用替换而不是交换的方式进行操作
    while($low < $high && $arr[$low] <= $pivot){
      $low ++;
    }
    //swap($arr,$low,$high); //终于遇到一个比$pivot大的数，将其放到数组高端
    $arr[$high] = $arr[$low];
  }
  $arr[$low] = $temp;  //将枢轴数值替换回 $arr[$low];
  return $low;  //返回high也行，毕竟最后low和high都是停留在pivot下标处
}

在上面的改进中，我们使用替换而不是交进行操作，由于在这当中少了多次的数据交换，因此在性能上也是有所提高的。

优化三：优化小数组的排序方案：

对于一个数学科学家、博士生导师，他可以攻克世界性的难题，可以培育最优秀的数学博士，当让他去教小学生“1 + 1 = 2”的算术课程，那还真未必比常年在小学里耕耘的数学老师教的好。换句话说，大材小用有时会变得反而不好用。

也就是说，快速排序对于比较大数组来说是一个很好的排序方案，但是假如数组非常小，那么快速排序算法反而不如直接插入排序来得更好（直接插入排序是简单排序中性能最好的）。其原因在于快速排序用到了递归操作，在大量数据排序的时候，这点性能影响相对于它的整体算法优势而言是可以忽略的，但如果数组只有几个记录需要排序时，这就成了大炮打蚊子的大问题。

因此我们需要修改一下我们的 QSort() 函数：

//规定数组长度阀值
#define MAX_LENGTH_INSERT_SORT 7
function QSort(array &$arr,$low,$high){
  //当 $low >= $high 时表示不能再进行分组，已经能够得出正确结果了
  if(($high - $low) > MAX_LENGTH_INSERT_SORT){
    $pivot = Partition($arr,$low,$high); //将$arr[$low...$high]一分为二，算出枢轴值
    QSort($arr,$low,$pivot - 1); //对低子表（$pivot左边的记录）进行递归排序
    QSort($arr,$pivot + 1,$high); //对高子表（$pivot右边的记录）进行递归排序
  }else{
    //直接插入排序
    InsertSort($arr);
  }
}

PS：上面的直接插入排序算法大家可以参考：《PHP排序算法之直接插入排序（Straight Insertion Sort）》

在这里我们增加一个判断，当 $high - $low 不大于一个常数时（有资料认为 7 比较合适，也有认为 50 比较合适，实际情况可以是适当调整），就用直接插入排序，这样就能保证最大化的利用这两种排序的优势来完成排序工作。

优化四：优化递归操作：

大家知道，递归对性能时有一定影响的，QSort()函数在其尾部有两次递归的操作，如果待排序的序列划分极端不平衡（就是我们在选择枢轴的时候不是中间值），那么递归的深度将趋近于 n，而不是平衡时的 log₂n，这就不仅仅是速度快慢的问题了。

我们也知道，递归是通过栈来实现的，栈的大小是很有限的，每次递归调用都会耗费一定的栈空间，函数的参数越多，每次递归耗费的空间也越多，因此如果能减少队规，将会大大提高性能。

听说，递归都可以改造成循环实现。我们在这里就是使用循环去优化递归。（关于递归与循环大家可以参考知乎里面的讨论 《所有递归都可以改写成循环吗？》）

我们对QSort() 函数尾部递归进行优化：

//规定数组长度阀值
#define MAX_LENGTH_INSERT_SORT 7
function QSort(array &$arr,$low,$high){
  //当 $low >= $high 时表示不能再进行分组，已经能够得出正确结果了
  if(($high - $low) > MAX_LENGTH_INSERT_SORT){
    while($low < $high){
      $pivot = Partition($arr,$low,$high); //将$arr[$low...$high]一分为二，算出枢轴值
      QSort($arr,$low,$pivot - 1); //对低子表（$pivot左边的记录）进行递归排序
      $low = $pivot + 1;
    }
  }else{
    //直接插入排序
    InsertSort($arr);
  }
}

在上面，我们使用循环替换递归，减少了之前一般的递归量。结果是一样的，但是采用循环而不是递归的方法可以缩减堆栈的深度，从而提高了整体性能。

相关推荐：

PHP排序算法之归并排序(Merging Sort)

PHP排序算法之冒泡排序(Bubble Sort)

PHP排序算法之简单选择排序(Simple Selection Sort)

위 내용은 PHP 정렬 알고리즘 Quick Sort(Quick Sort) 및 최적화의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!