愿你坚持不懈,努力进步,进阶成自己理想的人

—— 2017.09, 写给3年后的自己

简单排序算法总结

一、冒泡排序

冒泡排序是最基本的排序算法,它的核心思想,是进行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),不是稳定排序