算法：排序（一）

部分图片来源：牛客网
本文如果涉嫌侵权，请告知笔者第一时间做处理。

排序问题可以说是最经典的算法问题了。从排序问题上可以看到人们对效率孜孜不倦的渴求，也算是算法进化史的一个小小的缩影。

冒泡排序、选择排序与插入排序

早期的算法时间复杂度为O(N^2)，它们用笨拙和单纯的方式，跨出了算法历史上小小的一步。

冒泡排序

通过依次比较两两相邻的元素，并把两者中较大值交换[注1]至右侧，这样遍历过一次数组后，就会把最大值移动到队尾。对数组剩下的部分继续做此操作，直至排序完成。

CODE

int* bubbleSort(int* A, int n) {
    //长度为n的数组需要遍历n-1次
    for(int i=0;i<n-1;++i){
        //遍历开始时右侧已排好i个元素，故待处理区间为[0,n-i)
        //因为需要j+1<n-i所以j的取值是[0,n-i-1)
        for(int j=0;j<n-i-1;++j){
            if(A[j]>A[j+1]){
                swap(A[j],A[j+1]);
            }
        }
    }
    return A;
}

要点

• 两层循环
• 外层每次循环选出当前范围内的最大值移至队尾
• 内层依次遍历当前范围，两两比较相邻元素
• 外层计数范围：[0,n-1)
• 内层计数范围：[0,n-i-1)

选择排序

通过选出当前范围内的最小值并交换到队首，对剩下的部分不断重复该操作直至排序结束。

CODE

int* selectionSort(int* A, int n) {
    //长度为n的数组需要遍历n-1次
    for(int i=0;i<n-1;++i){
        //每次找出最小值的下标
        int min=i;
        //A[i]暂定为最小值，故j遍历范围是[i+1,n)
        for(int j=i+1;j<n;++j){
            if(A[j]<A[min])
                min=j;
        }
        //交换
        swap(A[min],A[i]);
    }
    return A;
}

要点

• 两层循环
• 外层每次循环把当前范围内的最小值移至队尾
• 内层依次遍历当前范围，选出最小值
• 外层计数范围：[0,n-1)
• 内层计数范围：[i+1,n)

插入排序

待处理元素左侧是一个已经排好序的数组（初始长度为1），从右向左遍历该有序数组，找到合适的位置插入待处理元素，直至所有元素处理完毕。

CODE

int* insertionSort(int* A, int n) {
    //初始时认为A[0]是有序数列，待处理元素范围是[1,n)
    for(int i=1;i<n;i++){
        int get=A[i];
        //待处理元素的插入位置从i-1到0逆序搜索
        int j=i-1;
        //搜索条件：j未越界且位置j上的元素大于待处理元素
        while(j>=0&&A[j]>get){
            //相当于元素右移一位
            A[j+1]=A[j];
            j--;
        }
        //循环结束时若j越界：需插入到A[0]处；
        //否则A[j]<=get需要插入到A[j+1]处
        A[j+1]=get;
    }
    return A;
}

要点

• 两层循环
• 外层循环遍历待处理的元素
• 内层循环遍历左侧有序序列，找到合适的位置插入待处理元素
• 插入位置的选择：大于待处理元素的部分右移一位，直至越界或遇见不大于待处理元素的部分。
• 特别需要提出的是，对于一个近乎有序的序列，插入排序的效率很高

附注

[1] 交换代码如下

void swap(int& a,int& b){
        //加上不等判断来提高性能
        if(a!=b){
            int t=a;
            a=b;
            b=t;
        }
    }