简单排序算法总结

一、冒泡排序

冒泡排序是最基本的排序算法，它的核心思想，是进行n-1趟比较，每趟比较都把最小的元素放到前面，像吐泡泡一样，轻的元素向上冒，所以得名冒泡排序。
过程：

实现：
PHP实现：

function bubbleSort(&$arr) {
    $n = count($arr);
    for($i=1; $i<$n-1; ++$i) {
        for($j=$n-1; $j>=$i; --$j) {
            if($arr[$j] < $arr[$j-1]) swap($arr[$j], $arr[$j-1]);
        }
    }
}

C++实现：

void bubbleSort(int arr[], int n) {
    for(int i=1; i<n; ++i) {
        for(int j=n-1; j>=i; --j) {
            if(arr[j] < arr[j-1]) swap(arr[j], arr[j-1]);
        }
    }
}

二、插入排序

插入排序，就是不断地将一个新的元素插入到已排序好的数组中，然后比较后移元素，找到位置插入。需要进行n-1趟比较
过程：

实现：
PHP实现：

function insertSort(&$arr) {
    $n = count($arr);
    for($i=1; $i<$n; ++$i) {
        $item = $arr[$i];
        $j = $i;
        while($j>0 && $item < $arr[$j-1]) {
            $arr[$j] = $arr[$j-1];
            --$j;
        }
        $arr[$j] = $item;
    }
}

C++实现：

void insertSort(int arr[], int n) {
    for(int i=1; i<n; ++i) {
        int item = arr[i];
        int j = i;
        while(j>0 && item < arr[j-1]) {
            arr[j] = arr[j-1];
            --j;
        }
        arr[j] = item;
    }
}

三、选择排序

选择排序就是对元素进行n-1趟处理，第i趟（i从0开始）的时候，选择出arr[i]~arr[n-1]中最小的元素，然后和arr[i]进行交换
过程：

实现：
PHP实现：

function selectSort(&$arr) {
    $n = count($arr);
    for($i=0; $i<$n; ++$i) {
        $min = $i;
        for($j=$i+1; $j<$n; ++$j) {
            if($arr[$j] < $arr[$min]) $min = $j;
        }
        swap($arr[$i], $arr[$min]);
    }
}

C++实现：

void selectSort(int arr[], int n) {
    for(int i=0; i<n; ++i) {
        int min = i;
        for(int j=i+1; j<n; ++j) {
            if(arr[j] < arr[min]) min = j;
        }
        swap(arr[i], arr[min]);
    }
}

四、性能分析

1、冒泡排序，平均时间复杂度为O(n^2)，无论输入是什么，最好最差的情况均为O(n^2)，是稳定排序
2、插入排序，平均时间复杂度为O(n^2)。最好情况下，输入是已排序好的数组，所以就不需要进行比较后移的过程，时间复杂度是O(n)，最差情况下，输入是逆序数组，那么比较后移的过程就要进行最大程度次，时间复杂度为O(n^2)
3、选择排序，平均时间复杂度为O(n^2)，最好情况和最差情况下，均为O(n^2)，不是稳定排序