快速排序

快速排序是十分常用的高效率的算法，其思想是：先选一个标尺，用它把整个队列过一遍筛选，以保证其左边的元素都不大于它，其右边的元素都不小与它

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

/**
 * 快速排序
 * 数据结构----------------数组
 * 最差时间复杂度-----------每次选取的基准都是最大（或最小）的元素，导致每次只划分出了一个分区，需要进行n-1次划分才能结束递归，时间复杂度为O(n^2)
 * 最优时间复杂度-----------每次选取的基准都是中位数，这样每次都均匀的划分出两个分区，只需要logn次划分就能结束递归，时间复杂度为O(nlogn)
 * 平均时间复杂度-----------O(nlogn)
 * 空间复杂度--------------O(logn)
 * 稳定性-----------------不稳定
 */
function quickSort($arr){
  // 获取数组长度
  $length = count($arr);
  // 判断长度是否需要继续二分比较
  if($length <= 1){
    return $arr;
  }
  // 定义基准元素
  $base = $arr[0];
  // 定义两个空数组，用于存放和基准元素的比较后的结果
  $left = [];
  $right = [];
  // 遍历数组
  for ($i=1; $i < $length; $i++) { 

    // 和基准元素作比较
    if ($arr[$i] > $base) {
      $right[] = $arr[$i];
    }else {
      $left[] = $arr[$i];
    }
  }
  // 然后递归分别处理left和right
  $left = quickSort($left);
  $right = quickSort($right);
  // 合并
  return array_merge($left,[$base],$right);
}

冒泡排序

在要排序的一组数中，对当前还未排好的序列，从前往后对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即，每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。

比如：2，4，1
第一次冒出4：2，1，4
第二次冒出2：1，2，4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

/**
 * 冒泡排序
 * 数据结构----------------数组
 * 最差时间复杂度-----------O(n^2)
 * 最优时间复杂度-----------O(n)
 * 平均时间复杂度-----------O(n^2)
 * 空间复杂度---------------O(1)
 * 稳定性------------------稳定
 */
function bubbleSort($arr){

  // 获取数组长度
  $length = count($arr);

  // 第一层循环控制冒泡轮次
  for ($i=0; $i < $length-1; $i++) { 
    
    // 内层循环控制从第0个键值和后一个键值比较，每次冒出一个最大的数
    for ($k=0; $k < $length-$i-1; $k++) { 
      if($arr[$k] > $arr[$k+1]){
        $tmp = $arr[$k+1];
        $arr[$k+1] = $arr[$k];
        $arr[$k] = $tmp;
      }
    }
  }

  return $arr;
}

选择排序

在要排序的一组数中，选出最小的一个数与第一个位置的数交换。然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

/**
 * 选择排序
 * 数据结构----------------数组
 * 最差时间复杂度-----------O(n^2)
 * 最优时间复杂度-----------O(n^2)
 * 平均时间复杂度-----------O(n^2)
 * 空间复杂度--------------O(1)
 * 稳定性-----------------不稳定
 */
function selectSort($arr){
     
      // 实现思路
      // 双重循环完成，外层控制轮数，当前的最小值，内层控制比较次数

      // 获取长度
      $length = count($arr);
  
      for ($i=0; $i < $length - 1; $i++) { 
        // 假设最小值的位置
        $p = $i;
  
        // 使用假设的最小值和其他值比较，找到当前的最小值
        for ($j=$i+1; $j < $length; $j++) { 
          // $arr[$p] 是已知的当前最小值
  
          // 判断当前循环值和已知最小值的比较，当发下更小的值时记录下键，并进行下一次比较
          if ($arr[$p] > $arr[$j]) {
            $p = $j; // 比假设的值更小
          }
        }
  
        // 通过内部for循环找到了当前最小值的key,并保存在$p中
        // 判断 日光当前$p 中的键和假设的最小值的键不一致增将其互换
        if ($p != $i) {
          $tmp = $arr[$p];
          $arr[$p] = $arr[$i];
          $arr[$i] = $tmp;
        }
      }
      // 返回最终结果
      return $arr;
    }

插入排序

在要排序的一组数中，假设前面的数已经是排好顺序的，现在要把第n个数插到前面的有序数中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。

插入排序算法还有使用二分查找的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

/**
 * 直接插入排序
 * 数据结构----------------数组
 * 最差时间复杂度-----------O(n^2)：输入序列是降序排列的
 * 最优时间复杂度-----------O(n)：输入序列是升序排列的
 * 平均时间复杂度-----------O(n^2)
 * 空间复杂度--------------O(1)
 * 稳定性-----------------稳定
 */
function insertSort($arr) {
    $len=count($arr); 
    for($i=1, $i<$len; $i++) {
        $tmp = $arr[$i];
        //内层循环控制，比较并插入
        for($j=$i-1;$j>=0;$j--) {
            if($tmp < $arr[$j]) {
                //发现插入的元素要小，交换位置，将后边的元素与前面的元素互换
                $arr[$j+1] = $arr[$j];
                $arr[$j] = $tmp;
            } else {
                //如果碰到不需要移动的元素，由于是已经排序好是数组，则前面的就不需要再次比较了。
                break;
            }
        }
    }
    return $arr;
}