집 > 기사 > 백엔드 개발 > PHP는 몇 가지 일반적인 정렬 알고리즘을 구현합니다.

PHP는 몇 가지 일반적인 정렬 알고리즘을 구현합니다.

小云云원래의: 2018-03-10 13:34:426960검색

교환 정렬: 교환 정렬의 기본 아이디어는 두 레코드의 키 값을 비교하는 것입니다. 두 레코드의 키 값이 역순이면 두 레코드를 더 작은 레코드로 교환합니다. 키 값이 순서대로 앞으로 이동합니다. 키 값이 큰 레코드는 순서의 뒤로 이동합니다. 1. 버블 정렬

버블 정렬(버블 정렬, 대만어 번역: 버블 정렬 또는 버블 정렬)은 간단한

정렬 알고리즘

입니다. 정렬할 시퀀스를 반복적으로 살펴보며 한 번에 두 요소를 비교하고 순서가 잘못된 경우 교체합니다. 더 이상 교환이 필요하지 않을 때까지 어레이 방문 작업이 반복됩니다. 이는 어레이가 정렬되었음을 의미합니다. 이 알고리즘의 이름은 작은 요소가 스와핑을 통해 배열의 맨 위로 천천히 "부동"된다는 사실에서 유래되었습니다.

단계:

인접한 요소를 비교합니다. 첫 번째 것이 두 번째 것보다 크면 둘 다 교환하세요.

시작의 첫 번째 쌍부터 끝의 마지막 쌍까지 인접한 요소의 각 쌍에 대해 동일한 작업을 수행합니다. 이때 마지막 요소가 가장 큰 숫자가 되어야 합니다.

마지막 요소를 제외한 모든 요소에 대해 위 단계를 반복합니다.

비교할 숫자 쌍이 더 이상 없을 때까지 매번 요소 수를 줄여 위 단계를 계속 반복하세요.

버블 정렬은 이해하기 가장 간단하지만 시간 복잡도(O(n^2))도 가장 큰 것 중 하나입니다. 구현 코드는 다음과 같습니다.
```
<br/>
```
1. $arr=array(1,43,54,62,21,66,32,78,36,76,39) function
  getpao(
2. $arr
  ) {
3. $len
  =
4. count
  ($arr); //비워두기 설정
5. //이 레이어 루프는 버블링이 필요한 라운드 수를 제어합니다
6. for
  (
7. $i
  =1;$iaee03dbf916deb8349a6842a25a0499d $arr[$k+1] )
8. {
9. $tmp=$arr[ $k+1];
10. $arr[$k+1]=$arr[$k];
11. }}}} $ arr; 2. Quick sort
12. 소개:
13. Quick Sort는
  Tony Hall이 개발한 정렬 알고리즘입니다. 평균적으로 n
  항목을 정렬하려면
14. (
  n log n
  )번의 비교가 필요합니다. 최악의 경우에는
15. (
  n2) 비교가 필요하지만 이런 상황은 흔하지 않습니다. 실제로 퀵 정렬은 내부 루프가 대부분의 아키텍처에서 효율적으로 구현될 수 있고 대부분의 실제 데이터에서 2차 항의 가능성이 필요한 시간을 줄이는 설계 선택을 지시합니다. 단계:
  1. 시퀀스에서 "피벗"이라는 요소를 선택합니다.
  2. 시퀀스를 재정렬합니다. 피벗 값보다 작은 모든 요소는 피벗 앞에 배치되고 피벗보다 큰 모든 요소는 값은 베이스 뒤에 배치됩니다(같은 숫자가 양쪽에 올 수 있음). 이 파티션이 종료된 후 베이스는 시퀀스의 중간에 있습니다. 이것을 partition 작업이라고 합니다.
  3. 기본 값보다 작은 요소의 하위 배열과 기본 값보다 큰 요소의 하위 배열을 재귀적으로 정렬합니다.
  퀵 정렬도 효율적인 정렬 알고리즘이고, 시간 복잡도도 O(nlogn)입니다. 코드는 다음과 같습니다:
  1. functionquick_sort($arr) {
  2. $ 길이
  3. =
    count ($arr) 1) {
  4. ㅋㅋ >
  5. //첫 번째 요소 선택
  6. $base_num =
  7. [0]
  10. = 배열 ();// 자보다 작은
  11. $right_array = array
  12. //
  13. if($base_num > $arr[$i]) { //넣어 왼쪽 배열에
  14. ] else { 그렇죠 G i $ right_array
  15. [] =
    $ ar [ $ i] }}
  16. / /The n 왼쪽에서도 동일한 정렬을 수행 및 오른쪽 배열 각각
  18. = Quick_sort($left_array)
  19. $right_array = Quick_sort($right_array
  20. //왼쪽 눈금자를 오른쪽 눈금자와 병합
  21. return array_merge($left_array, array($base_num), $right_array)
  22. }
  선택 정렬
  
  선택 정렬에는 직접 선택 정렬과 힙 정렬의 두 가지 유형이 있습니다. 선택 정렬의 기본 아이디어는 매번 n-i+ 1 ( i=1,2,3,...,n-1) 레코드, 가장 작은 키 값을 가진 레코드를 순서대로 i 번째 레코드로 선택
  
  3. 선택 정렬
  
  소개:
  
  선택 정렬은 간단하고 직관적인 정렬 알고리즘입니다. 작동 방식은 다음과 같습니다. 먼저 정렬되지 않은 시퀀스에서 가장 작은 요소를 찾아 정렬된 시퀀스의 시작 부분에 저장한 다음, 정렬되지 않은 나머지 요소에서 계속해서 가장 작은 요소를 찾아 정렬된 시퀀스의 끝에 넣습니다. 모든 요소가 정렬될 때까지 계속됩니다.
  
  선택 정렬도 비교적 이해하기 쉽고, 시간 복잡도도 O(n^2)입니다. 구현 코드는 다음과 같습니다.
```
<br/>
```
  [php] view plain 복사
  1. function select_sort($arr) {
  2. //구현 아이디어 이중 루프가 완료되고 외부 제어 라운드 수는 현재 최소값입니다. 내부 레이어에서 제어하는 비교 횟수
  3. //$i 현재 최소값의 위치, 비교에 참여해야 하는 요소
  4. for ($i =0, $len=count($arr); -1 ; $i ++ ) { $i
  5. ㅋㅋ ~ // $arr[$p] +
  6. // 알려진 최소값을 비교에 사용해야 합니다.
  7. //현재 최소값 위치가 결정되어 $p에 저장되었습니다. ㅋㅋㅋ ($ p !=
  8. ) {
    $p
  9. ];
    [$p] = $arr[$i];
  10. [$i] = $tmp;
  12. //최종 결과 반환
  13. return $arr
  14. }
  4.
  
  소개:
  
  스태킹 정렬(Heapsort)은 heap의 데이터 구조를 사용하여 설계된 정렬 알고리즘을 말합니다. 힙은 완전 이진 트리에 근접하면서 힙 속성을 동시에 만족하는 구조입니다. 즉, 하위 노드의 키 값이나 인덱스는 항상 더 작습니다(또는 더 큽니다). ) 상위 노드보다.
  
  단계:
  
  힙 정렬은 배열의 특성을 이용하여 지정된 인덱스에서 요소를 빠르게 찾는 스택 트리(힙)와 같은 데이터 구조를 사용하여 설계된 정렬 알고리즘을 말합니다. 힙은 큰 루트 힙과 작은 루트 힙으로 나누어지며 이는 완전한 이진 트리입니다. 큰 루트 힙의 요구 사항은 각 노드의 값이 해당 상위 노드의 값, 즉 A[PARENT[i]] >= A[i]보다 크지 않아야 한다는 것입니다. 배열의 비내림차순 정렬에서는 큰 루트 힙의 요구 사항에 따라 최대값이 힙의 맨 위에 있어야 하기 때문에 큰 루트 힙을 사용해야 합니다.
  
  정렬 효과:
  
  堆排序是一种高效的排序算法，它的时间复杂度是O(nlogn)。原理是：先把数组转为一个最大堆，然后把第一个元素跟第i元素交换，然后把剩下的i-1个元素转为最大堆，然后再把第一个元素与第i-1个元素交换，以此类推。实现代码如下：
```
function heapSort($arr) {
    $len = count($arr);    // 先建立最大堆
    for ($i = floor(($len - 1) / 2); $i >= 0; $i--) {        $s = $i;        $childIndex = $s * 2 + 1;        while ($childIndex < $len) {            // 在父、左子、右子中 ，找到最大的
            if ($childIndex + 1 < $len && $arr[$childIndex] < $arr[$childIndex + 1]) $childIndex++;            if ($arr[$s] < $arr[$childIndex]) {                $t = $arr[$s];                $arr[$s] = $arr[$childIndex];                $arr[$childIndex] = $t;                $s = $childIndex;                $childIndex = $childIndex * 2 + 1;
            } else {                break;
            }
        }
    }    // 从最后一个元素开始调整
    for ($i = $len - 1; $i > 0; $i--) {        $t = $arr[$i];        $arr[$i] = $arr[0];        $arr[0] = $t;        // 调整第一个元素
        $s = 0;        $childIndex = 1;        while ($childIndex < $i) {            // 在父、左子、右子中 ，找到最大的
            if ($childIndex + 1 < $i && $arr[$childIndex] < $arr[$childIndex + 1]) $childIndex++;            if ($arr[$s] < $arr[$childIndex]) {                $t = $arr[$s];                $arr[$s] = $arr[$childIndex];                $arr[$childIndex] = $t;                $s = $childIndex;                $childIndex = $childIndex * 2 + 1;
            } else {                break;
            }
        }
    }    return $arr;
}$arr = [3,1,13,5,7,11,2,4,14,9,15,6,12,10,8];
print_r(bubbleSort($arr));
```
  插入排序
  
  五、插入排序
  
  介绍：
  
  插入排序（Insertion Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
  
  步骤：
  1. 从第一个元素开始，该元素可以认为已经被排序
  2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
  3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
  4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
  5. 将新元素插入到该位置中
  6. 重复步骤2
  感觉插入排序跟冒泡排序有点相似，时间复杂度也是O(n^2)，实现代码如下：
  
  [php]일반 보기copy
  1. function insert_sort($arr) {
  2. //어떤 부분을 구별 정렬되었습니다
  3. //정렬되지 않은 부분
  4. //정렬해야 할 요소 중 하나를 찾으세요
  5. //이 요소는 두 번째 요소에서 시작하여 정렬이 필요한 마지막 요소로 끝납니다
  6. //루프를 사용하여 표시할 수 있습니다
  7. //i 루프는 삽입해야 하는 요소를 매번 제어합니다. 삽입해야 하는 요소를 제어하면
  8. //간접적으로 배열이 2개로 나누어졌습니다. , 그리고 아래 첨자가 현재 것(왼쪽에 있는 것)보다 작으면 정렬된 시퀀스입니다
  9. for($i=1, $len=count($arr); $i 16a5964c6dafbcd665a34985cb293642=0;$ j --) {
  10. //$arr[$i];//삽입할 요소; $arr[$j] //비교할 요소
  11. if( $tmp f2c1801fb4151ac97219c0b76b168efd
    
    排序效果：
    
    希尔排序其实可以理解是插入排序的一个优化版，它的效率跟增量有关，增量要取多少，根据不同的数组是不同的，所以希尔排序是一个不稳定的排序算法，它的时间复杂度为O(nlogn)到O(n^2)之间，实现代码如下：
```
function shellSort($arr) {
    $len = count($arr);    $stepSize = floor($len / 2);    while ($stepSize >= 1) {        for ($i = $stepSize; $i < $len; $i++) {            if ($arr[$i] < $arr[$i - $stepSize]) {                $t = $arr[$i];                $j = $i - $stepSize;                while ($j >= 0 && $t < $arr[$j]) {                    $arr[$j + $stepSize] = $arr[$j];                    $j -= $stepSize;
                }                $arr[$j + $stepSize] = $t;
            }
        }        // 缩小步长，再进行插入排序
        $stepSize = floor($stepSize / 2);
    }    return $arr;
}$arr = [3,1,13,5,7,11,2,4,14,9,15,6,12,10,8];
print_r(bubbleSort($arr));
```
    七、归并排序
    
    介绍：
    
    归并排序（Merge sort，台湾译作：合并排序）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（pide and Conquer）的一个非常典型的应用
    
    步骤：
    1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
    2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置
    3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
    4. 重复步骤3直到某一指针达到序列尾
    5. 将另一序列剩下的所有元素直接复制到合并序列尾
    排序效果：
    
    归并排序的时间复杂度也是O(nlogn)。原理是：对于两个排序好的数组，分别遍历这两个数组，获取较小的元素插入新的数组中，那么，这么新的数组也会是排序好的。代码如下：
    
    我们先来看看主函数部分：
```
//交换函数function swap(array &$arr,$a,$b){
    $temp = $arr[$a];    $arr[$a] = $arr[$b];    $arr[$b] = $temp;
}//归并算法总函数function MergeSort(array &$arr){
    $start = 0;    $end = count($arr) - 1;
    MSort($arr,$start,$end);
}
```
    在总函数中，我们只调用了一个 MSort() 函数，因为我们要使用递归调用，所以将 MSort() 封装起来。
    
    下面我们来看看 MSort() 函数：
```
function MSort(array &$arr,$start,$end){    //当子序列长度为1时，$start == $end，不用再分组    if($start < $end){        $mid = floor(($start + $end) / 2);	//将 $arr 平分为 $arr[$start - $mid] 和 $arr[$mid+1 - $end]        MSort($arr,$start,$mid);			//将 $arr[$start - $mid] 归并为有序的$arr[$start - $mid]        MSort($arr,$mid + 1,$end);			//将 $arr[$mid+1 - $end] 归并为有序的 $arr[$mid+1 - $end]        Merge($arr,$start,$mid,$end);       //将$arr[$start - $mid]部分和$arr[$mid+1 - $end]部分合并起来成为有序的$arr[$start - $end]
    }
}
```
    上面的 MSort() 函数实现将数组分半再分半（直到子序列长度为1），然后将子序列合并起来。
    
    现在是我们的归并操作函数 Merge() :
```
//归并操作function Merge(array &$arr,$start,$mid,$end){
    $i = $start;    $j=$mid + 1;    $k = $start;    $temparr = array();    while($i!=$mid+1 && $j!=$end+1)
    {       if($arr[$i] >= $arr[$j]){           $temparr[$k++] = $arr[$j++];
       }       else{           $temparr[$k++] = $arr[$i++];
       }
    }    //将第一个子序列的剩余部分添加到已经排好序的 $temparr 数组中
    while($i != $mid+1){        $temparr[$k++] = $arr[$i++];
    }    //将第二个子序列的剩余部分添加到已经排好序的 $temparr 数组中
    while($j != $end+1){        $temparr[$k++] = $arr[$j++];
    }    for($i=$start; $i<=$end; $i++){        $arr[$i] = $temparr[$i];
    }
}
```
    到了这里，我们的归并算法就完了。我们调用试试：
```
$arr = array(9,1,5,8,3,7,4,6,2);
MergeSort($arr);
var_dump($arr);
```
    相关推荐：
    
    php冒泡、选择、插入和快速排序算法分享
    
    PHP多维数组排序算法分析
    
    PHP排序算法系列之直接选择排序详解

위 내용은 PHP는 몇 가지 일반적인 정렬 알고리즘을 구현합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

성명：

이전 기사：PHP Elasticsearch의 기본 사용법다음 기사：PHP Elasticsearch의 기본 사용법