基础排序算法

前言

万变不离其宗。基础不牢，地动山摇。

十大经典排序算法

（声明：算法中动态gif图片均来源于网络）

冒泡排序（Bubble Sort）

计算机专业的同学们第一次接触的排序算法恐怕就是冒泡排序。冒泡排序过程十分简单，即是循环中两两交换，每次选出一个最大/最小的元素，依次遍历整个数组交换。
算法的动态演示图如下：

冒泡排序动态图

其C语言代码如下，

void bubblesort(int* arr, int length) {
    if (!arr || length == 0)
        return ;
    
    for (int i = 0; i < length - 1; ++i) {
        for (int j = 0; j < length - 1 - i; ++j) {
            if (arr[j] > arr[j + 1]) {
                arr[j] = arr[j] ^ arr[j+1];
                arr[j+1] = arr[j] ^ arr[j+1];
                arr[j] = arr[j] ^ arr[j+1];
            }
        }
    }
}

这里需要注意的是，二层循环中length-1-i，
i=0，j < length-1；
i=1，j < length-2；
i=length-2，j < length-1-(length-2)=1
......
一层循环为循环次数，二层循环为交换次数。

时间复杂度分析

• 最好的情况，arr={1,2,3,4,5,6,7,8,9,10}，只需要遍历一遍就够了，O(n)；
• 最差的情况，arr={10,9,8,7,6,5,4,3,2,1}，每次都需要交换，其交换次数为9+8+...+1=45次，即(n-1+1)(n-1)/2=n(n-1)/2，复杂度为O(n²)。

空间复杂度分析

• 一般情况下，需要使用一个临时变量temp来进行交换，其空间复杂度为O(1)。
  （这里我使用异或省去了该变量。）

因此，时间复杂度平均为O(n²)，最好为O(n)，最差为O(n²)。空间复杂度为O(1)。

选择排序（Select Sort）

选择排序首先是确定首位数，然后从剩余未排序元素中选出最小/大的数与首位数交换，依次遍历直至结束。
动态演示如下：

选择排序动态图.gif

这句话理解起来比较简单，实现起来要注意几个点，

void select_sort(int* arr, int length) {
    if (!arr || length == 0)
        return;
    
    int temp, pos = 0;
    for (int i = 0; i < length; ++i) {
        temp = arr[i];
        
        for (int j = i; j < length; ++j) {
            if (arr[j] < temp) {
                pos = j;
                temp = arr[j];
            }
        }
        
        // swap
        if (pos > i) {
            arr[i] = arr[i] ^ arr[pos];
            arr[pos] = arr[i] ^ arr[pos];
            arr[i] = arr[i] ^ arr[pos];
        }
    }
}

要注意的点有，

• temp变量可以存储INT_MAX，也可以存储遍历过程中的第一个元素；
• 交换时分清交换的条件，pos>i时才交换，其它情况交换没有意义。

时间复杂度分析

• 无论是最好的情况还是最差的情况，都需要比较这些次数，O(n²)；

空间复杂度分析

• 需要临时变量来记录局部最小/大值，以及其下标，O(1)；

因此，时间复杂度平均为O(n²)，最好为O(n²)，最差为O(n²)。空间复杂度为O(1)。

插入排序

插入排序是对于数组中的某个元素，依次向前遍历找到其位置，然后插入进去。一直遍历到数组结尾。
其算法动态过程如下：

插入排序动态图.gif

插入排序非常容易理解，但是在实现过程中要注意index的位置，

void insert_sort(int* arr, int length) {
    if (!arr || length == 0)
        return ;

    for (int i = 1; i < length; ++i) {
        int pos = 0, temp = arr[i];
        for (int j = i - 1; j >= 0; --j) {
            if (arr[j] < temp) {
                pos = j;
                break;
            }
        }
        // move
        for (int j = i - 1; j >= pos; --j)
            arr[j + 1] = arr[j];
        
        arr[pos] = temp;
    }
}

要注意的点有：

• pos的初始值为0。这是由于如果比较了一遍后没有找到位置，即是最开始的为最小/最大；
• 比较要从插入的数的前一个数往前遍历；
• 最后不要忘记找到的pos位置插入数据。

时间复杂度分析

• 最好的情况下是数组已经排好序，这样只需要遍历一遍，不用比较，O(n)；
• 最差的情况下是数组是倒序状态，每个数都需要比较，O(n²)；

空间复杂度分析

• 需要两个临时变量来记录pos及插入的当前数据，O(1)；

因此，时间复杂度平均为O(n²)，最好为O(n)，最差为O(n²)。空间复杂度为O(1)。

未完待续