基础排序算法解析

冒泡排序，选择排序，插入排序的解析与实现

基础排序算法解析

1. 冒泡排序

冒泡排序的核心思想就是：

从左到右，相邻元素进行比较。每次比较一轮，就会找到序列中最大的一个或最小的一个。这个数就会从序列的最右边冒出来。

以从小到大排序为例，第一轮比较后，所有数中最大的那个数就会浮到最右边；第二轮比较后，所有数中第二大的那个数就会浮到倒数第二个位置……就这样一轮一轮地比较，最后实现从小到大排序。

void bubble(int *array, int n)
{
    int i, j;
    int temp;
    
    //外层的i循环是为了确定要进行遍历次数
    //每遍历一次可以确定一个当前 "待比较序列" 的最大值放在末尾
    //n个数据需要遍历n - 1次才可以，最后一个数据不需要比较，位置确定
    for (i = 0; i < n - 1; i++) {
        //内层的循环j是当前 "待比较的序列" 中，相邻数据需要比较多少次
        //易得需要比较 "待比较序列" 的长度减一次
        //进入第i次外层循环后，就有i个数据已经确定位置，待比较序列的长度就为n - i
        //相邻数据就需要比较 "待比较序列" 的长度减一次，即 n - 1 - i
        for (j = 0; j < n - 1 - i; j ++) {
            //满足条件时，相邻数据相互交换即可
            if (array[j] > array[j + 1]) {
                temp = array[j + 1];
                array[j + 1] = array[j];
                array[j] = temp;
            }
        }
    }
    return;
}

2. 选择排序

选择排序的核心思想是：

它在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

void select(int *array, int n)
{
    int i, j;
    int temp;
    int min;
    
    // 正如冒泡排序一样，外层的i循环是为了确定要进行遍历的次数
    // n个元素的序列只需要选择n - 1次即可，每次选择都会确定当前 “待选择序列” 的最小元素
    // 放在当前的位置 i 上
    for (i = 0; i < n - 1; i++) {
        // 假定当前位置的元素是最小元素
        min = i;
        // 内层j循环就是 “待选择序列” 需要和当前最小元素比较多少次
        // 当然起步是从i后面一个元素开始比较，即 i + 1,一直到最后一个元素
        for (j = i + 1; j < n; j++) {
            if (array[j] < array[min]) {
                min = j;
            }
        }
        
        //退出内层循环后，如果min改变说明发现了更小的元素，将之与当前位置i进行交换
        if (min != i) {
            temp = array[i];
            array[i] = array[min];
            array[min] = temp;
        }
    }

    return;
}

3. 插入排序

插入排序的核心思想是

逐个将未排序的元素插入到已排序的部分中，构建有序序列

void insert(int *array, int n)
{
    int i, j;
    int temp;
    
    // 插入排序，首先第一个元素的位置是确定的, 即array[0], 它是当前的待插入序列
    // 我们从第二个元素开始，向当前 "待插入序列" 插入元素
    // 外层循环i 表示了剩余待插入的元素的当前位置，从1 到 n -1 
    for (i = 1; i < n; i++) {
        // 内层循环j表示 “待插入序列” 的末尾，也是 当前待插入元素的前一个位置
        // 当前待插入元素需要和 “待插入序列” 中的每一个元素比较，找到自己的插入位置
        temp = array[i];
        for (j = i -1; j >= 0; j--) {
            if (array[j] > temp) {
                //由于当前元素大于待插入元素
                //将当前元素后移
                //之后进入下一次循环时，比较下一个当前元素与待插入元素
                //大于待插入元素时，就将其后移，空出插入位置
                array[j + 1] = array[j];
            } else {
                //不满足if的条件说明已经找到了当前待插入元素的位置
                break;
            }
        }
        
        array[j + 1] = temp;
    }
    
    return;
}

4. 快速排序