14_学习日志_数据结构_冒泡排序_快速排序_插入排序

#include<编织有意义的谎言，使我相信闭上眼再睁开眼时的世界是同一个>

1.介绍

        从后往前或者从前往后开始两两比较元素，使得最小数上浮或者最大数下沉为冒泡排序，快速排序利用分治思想，使得基准数左边都存放相对较小数，右边存放较大数，两边再按照同样的做法重复。插入排序默认第一个数据为有序排列，剩余的数字依次与之比较形成新的有序序列，直至最后一个元素找到最终位置。

2.冒泡排序函数以及交换函数

        外层循环决定函数执行次数，内层循环从后往前遍历，两两比较，后一个数小于前一个数时交换两数位置，加入ret判断，若一趟下来没有发生任何交换，说明该序列原本就有序。

void swap(int &a, int &b) {
    int tmp;
    tmp = a;
    a = b;
    b = tmp;
}
void bubble_sort(Elem *n, int a) {
    int i, j;
    bool ret;
    for (i = 0; i < a - 1; i++) {
        ret = false;
        for (j = a - 1; j > i; j--) {
            if (n[j - 1] > n[j]) {
                swap(n[j - 1], n[j]);
                ret = true;
            }
        }
    }
    if (!ret) {
        return;
    }
}

3.快排递归函数与快排核心函数

        quick_sort用于递归，基准数将序列分割成两部分后，前一部分与后一部分继续执行操作，基准数不再参与。核心函数partition，默认第一个元素为基准，记录该基准数，进入循环，从后往前遍历，找到比基准数小的元素，赋值给low位置元素，此时high位置不动，low往前遍历，找到第一个比基准数大的元素，赋值给此时high的位置，经过一轮交换，low与high相遇，此时low位置就是基准数确定下来的最终位置。

int partition(Elem *s, int low, int high) {
    int pivot = s[low];
    while (low < high) {
        while (low < high && s[high] >= pivot)
            high--;
        s[low] = s[high];
        while (low < high && s[low] <= pivot)
            low++;
        s[high] = s[low];
    }
    s[low] = pivot;
    return low;
}

void quick_sort(Elem *s, int low, int high) {

    if (low < high) {
        int pivot_pos = partition(s, low, high);
        quick_sort(s, low, pivot_pos - 1);
        quick_sort(s, pivot_pos + 1, high);
    }
}

4.插入排序函数

        内层循环决定执行次数，记录第二个元素值，进入内层循环第二个元素与第一个元素比较，若第一个元素较大，将第一个元素的值赋给第二个元素，最后将记录下来的值放入第一个元素，循环往复直至遍历整个数组。

void insert_sort(Elem *s, int len) {
    int i, j, tem;
    for (i = 1; i < len; i++) {
        tem = s[i];
        for (j = i - 1; j >= 0 && s[j] > tem; j--) {
            s[j + 1] = s[j];
//            s[j]=tem;
        }
        s[j + 1] = tem;
    }
}

5.总结

        快速排序作为上述排序中综合表现最为优异的算法，代码量同样高于另外两种排序方式。