算法基础——基本排序算法

本文中的基础排序算法分类依据是算法的时间复杂度，之所以被称作基础排序算法，是因为他们实现起来比较简单，对应的算法的时间复杂度较高，一般情况下效率较低，但这并不影响我们去学习、使用和优化他们。

算法的时间复杂度

算法的时间复杂度，可以简单地理解为其执行指令（粗浅的理解为循环）的次数的多少，记作O,在理想的情况下算法的时间复杂度应该为O(1),其次排列下去有O(n)、O(log(n))、O(n**2)等。

选择排序

选择排序是一种常见的较容易实现的排序算法，算法的思想是：经过多轮遍历，不断缩小列表的区间，在这个区间内再遍历（选择）最小值。所以它的时间复杂度为O(N**2)。

template <typename T>
void selectionSort(T* arr, int n){
    for( int i = 0; i < n-1; i++){
        int minIndex = i;
        //在[i,n)区间内寻找最小值的下标
        for(int j = i+1; j < n; j++){
            if(arr[j] < arr[minIndex]){
                minIndex = j;
            }
        }
        //把找到的最小值放到区间的最左边
        swap(arr[minIndex], arr[i])
    }
}

插入排序

插入排序就像是整理手上的扑克牌，每当有一张新牌接到手上后，都要去选择一个合适的位置插入，最终整套手牌都会排序完成。它的时间复杂度为O(N**2)。插入排序的好处是，每一次排序之后，排序过后的序列都是有序的，所以在内层遍历比较中，一旦发现用来比对的数据比当前数据大，则直接可以跳出循环。所以，在最理想的情况下，如果数据本来就是已经排序好的，那么插入排序的是时间复杂度可以为O(n)，在近似于有序的序列排序中，插入排序的时间复杂度很多时候超过了很多高级排序算法(O(lg(n)))。

一般情况下的插入排序:效率较低，因为频繁的进行交换操作（以此交换等于三次赋值）

template <typename T>
void insertionSort(T* arr, int n){
    //循环从第二张牌开始，因为针对第一张牌来讲，本来就是有序的
    for( int i = 1; i < n; i++){
        for(int j = i; j > 0; j--){
            //内层遍历从i开始，向前遍历比较，如果小则交换，否则跳出
            if(arr[j] < arr[j-1]){
                swap(arr[j], arr[j-1]);
            }else{
                break;
            }
        }
    }
}

优化之后的插入排序：优化之后避免了频繁的赋值操作。在排序的思想上，相当于把当前的手牌提出来，挨个向前比对，如果前面的牌比当前牌大，前面的牌就后移一位，最终找到的是的位置的时候，这个位置就是空的，这个时候把当前牌放入即可。

template <typename T>
void insertionSort(T* arr, int n){
    //循环从第二张牌开始，因为针对第一张牌来讲，本来就是有序的
    for( int i = 1; i < n; i++){
        T e = arr[i];
        int j;
        for(j = i; j > 0 && arr[j] > e; j--){
            arr[j] = arr[j-1];
        }
        arr[j] = e;
    }
}

冒泡排序

冒泡排序是一种很形象的描述，在排序过程中冒泡排序会和相邻的元素比较，然后建换位置，循环往复到序列的尽头，最大的数字就被放在了最右边（或最小的元素被放在最左边），就像冒泡泡一样，谁最大（小）谁先冒出来。

template <typename T>
void bubbleSort(T* arr, int n){
    //大的循环控制区间范围，随着最大的泡泡冒出，区间被不断的缩小
    for( int i = n-1; i > 0; i--){
        //内层循环不断地和下一个元素比较，最终把最大的泡泡冒上去
        for(int j = 0; j < i; j++){
            if(arr[j] > arr[j+1]){
                swap(arr[j], arr[j+1])
            }
        }
    }
}

总结

以上是常见的所有的时间复杂度为O(n**2)的排序算法，但是时间复杂度复杂并不代表算法差劲，重要的是理解算法的思想，排序算法的集中思想影响着很多其他的算法。再者，在一些特殊情况下时间和空间的复杂度也并不是评判算法的唯一标准。比如上述算法中的插入排序在面对近似有序的寻列排序中，其效率大多数时候要超越一些时间复杂度为O(n*logn(n))的算法。

###　相关代码

github
C++实现的O(n**2)的基本排序算法, 欢迎点星星！