常见的排序算法

1. 冒泡排序

冒泡的思想是（假设为从小到大排序）： 顺序扫描数组元素，将相邻两个数进行比较，将小数调到前面，大数调到后面。

冒泡排序的特点是：

1. 如果有 N 个数，则要进行 N - 1 轮排序；

2. 在第 i 轮排序中，要进行 N - i 次两两比较

3. 可以从前往后排序，也可从后往前排序

第一个for循环是 n-1, 第二个for循环是n - i - 1, 冒泡排序的时间复杂度是O（n^2）

Go

package main

import "fmt"

func main() {
   fmt.Println("冒泡排序")
   var a = []int{7,3,2,1,5,4,6,8,9}
   aSort := bubbleSort(a)
   fmt.Println(aSort)
}

// 冒泡排序
func bubbleSort(a []int) []int {
   n := len(a)
   if n <= 1 {
      return a
   }

   for i := 0; i < n-1; i++ {
      for j := 0; j < n-i-1; j++ {
         if a[j] > a[j+1] { // // 这里是从小到大排序，如果是从小到大排序，只需将">"换成"<"
            a[j], a[j+1] = a[j+1], a[j]
         }
      }
   }
   return a
}

PHP

2. 插入排序

插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

插入排序和冒泡排序一样，也有一种优化算法，叫做拆半插入。

算法步骤

将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。

从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

Go

package main

import "fmt"

func main() {
   fmt.Println("插入排序")
   var arr = []int{7,3,2,1,5,4,6,8,9}
   aSort := insertSort(arr)
   fmt.Println(aSort)
}

// 插入排序
func insertSort(arr []int) []int {
   for i := range arr {
      preIndex := i-1
      current := arr[i]
      for preIndex >= 0 && arr[preIndex] > current {
         arr[preIndex+1] = arr[preIndex]
         preIndex -= 1
      }
      arr[preIndex+1] = current
   }
   return arr
}

PHP

2. 快速排序

快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。 快速排序又是一种分而治之思想在排序算法上的典型应用。 本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。

function quickSort($arr) {
    if (count($arr) <= 1)
        return $arr;
    $middle = $arr['0'];
    $leftArray = array();
    $rightArray = array();

    for ($i = 1; $i < count($arr); $i++) {
        if ($arr[$i] > $middle)
            $rightArray[] = $arr[$i]; // 5
        else
            $leftArray[] = $arr[$i]; // 3, 2
    }
    $leftArray = quickSort($leftArray);
    $leftArray[] = $middle;
    $rightArray = quickSort($rightArray);
    return array_merge($leftArray, $rightArray);
}

$arr = [4, 5, 3, 2];
$result = quickSort($arr);
echo '<pre>';
print_r($result);

3. 选择排序

选择排序(Selection Sort)是一种简单直观的排序算法。 它的工作原理如下，首先在未 排序序列中找到最小(大)元素，存放到排序序列的起始位置， 然后，再从剩余未排序元 素中继续寻找最小(大)元素，然后放到已排序序列的末尾。 以此类推，直到所有元素均 排序完毕。

function selectionSort($arr) {
    $len = count($arr);
    for ($i=0; $i < $len - 1; $i++) {
        $minValue = $arr[$i];
        for ($j = $i + 1; $j < $len; $j++) {
            if ($arr[$j] < $minValue) {
                $minIndex = $j;
                $minValue = $arr[$minIndex];
            }
        }
        // 每次找出一个最小值 交换位置
        $temp = $arr[$i];
        $arr[$i] = $minValue;
        $arr[$minIndex] = $temp;
    }
    return $arr;
}

$arr = [8, 5, 2, 6, 9, 3, 1, 4, 0, 7];

$result = selectionSort($arr);
echo '<pre>';
print_r($result);