书本常见的三种排序算法

---

冒泡排序

冒泡排序重在相邻的两个数进行比较，从头开始。每次比较都会把小的数冒泡排到前面，
大的数都会沉到后面。经过一轮排序后，最小的一定在最前面，所以下一次排序就可以少排一次。

所以就有了 j < length - 1 - i，让内层循环每次排完一次都减少一次排序

代码如下

#include <stdio.h>
int main() {
    int length = 10;
    int a[length] = {3, 4, 5, 2, 1, 8, 7, 9, 6, 10};
    
    for (int i = 0; i < length - 1; i++) {
        for (int j = 0; j < length - 1- i; j++) {
            if(a[j] > a[j+1]) { 
                int temp = a[j];
                a[j] = a[j+1];
                a[j+1] = temp;
            } 
        }
    }
    
    for (int i = 0; i < length; i++) {
        printf("%d ", a[i]);
    }   

    return 0;
}

交换法（苏小红版的《C程序设计》的叫法）

不同于冒泡排序，每次都越比越少，交换法是在做重复工作，外层循环表示从第一个数到倒数第二个数，
内层循环从当前i指的数的下一个数开始。
每一次循环，i定好一个数，然后j从i的下一位数开始，一直到最后一个数。

所以区别于冒泡排序就是，if里的判断是i与j的判断，然后就是两层for循环的范围细节。

代码如下

#include <stdio.h>
int main() {
    int length = 10;
    int a[length] = {3, 4, 5, 2, 1, 8, 7, 9, 6, 10};
    
    for (int i = 0; i < length - 1; i++) {
        for (int j = i + 1; j < length; j++) {
            if(a[i] > a[j]) { 
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            } 
        }
    }
    
    for (int i = 0; i < length; i++) {
        printf("%d ", a[i]);
    }   

    return 0;
}

选择法（苏小红版的《C程序设计》的叫法）

看到交换法，做了很多重复的比较，就是在做无用功，所以有了选择法。

原理：每次比较两数大小，如果满足交换的条件，先暂时记住要交换的数的下标，存到变量k里面。
因为后面有可能会出现更小的数，所以只是先记录，等比较完所有的数再进行交换，这样交换这一步骤就可以省很多次。

代码如下

#include <stdio.h>
int main() {
    int length = 10;
    int a[length] = {3, 4, 5, 2, 1, 8, 7, 9, 6, 10};
    int i, j;
    
    // 两层for循环都是跟“交换法”相同的 
    for (i = 0; i < length - 1; i++) {
        int k = i;  // k初始化为i，假设最小的数为当前i位置的数 
        for (j = i + 1; j < length; j++) {
            if(a[k] > a[j]) { 
                k = j;
            }
        }
        // 如果k的值发生了变化，即不再是i了，则说明找到更小的数了 
        if (k != i) {
            int temp = a[i];
            // 注意这里要用k而不是上面的j，因为j一直在变，最终确定的是k 
            a[i] = a[k];  
            a[k] = temp;
        }
    }
    
    for (int i = 0; i < length; i++) {
        printf("%d ", a[i]);
    }   

    return 0;
}