排序算法1=选择+插入

一、选择排序
基本思想：遍历元素中最大的一个然后与第一个元素进行交换。

template<typename T>
void selectSort(T arr[], int n) {
    for (int i = 0; i < n; i++) {
        int k = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] > arr[k]) {
                k = j;
            }
        }
        swap(arr[i], arr[k]);
    }
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
}

选择排序的算法如上面所示，这里定义的是模板，这里用一个具体的例子来讲述选择排序的排序流程
输入序列 4 2 1 3 6
进入第一重循环，令k=0，进入第二重循环，找到5个数中最大的一个然后与第一个元素进行交换，
此时序列变成6 2 1 3 4，继续第一重循环令k=1，找剩下的最大的数放置在数组i=1的地方
循环结束后，序列就变成了6 4 3 2 1

二、插入排序
基本思想：插入排序的重点是插入二字，每次将该位置的元素插入到前面的合适的位置当中，与选择排序每次向后找的方式不同，插入排序是选择向前找，依次找，如果找到比他小的则交换位置，提前中止循环，这里我是从大到小排，也可以找比他小的从小到大排
输入序列 2 6 5 7 3 1
进入第一重循环，从i=1；令j=i-1；交换2和6的位置，跳出循环
6 2 5 7 3 1
i=2，j=2-1=1，往前找5比2大，交换位置，5比6小跳出循环
6 5 2 7 3 1
i=3，j=3-1=2，往前找7比2大，交换位置，7比5大交换位置，7比6大交换位置，此时循环结束
7 6 5 2 3 1
i=4，j=4-1=3，3比2大交换位置，3比5小跳出循环
7 6 5 3 2 1
i=5，j=5-1=4，2比3小跳出循环，同理i=6时，1比2小，跳出循环

template<typename T>
void insertSort(T arr[], int n) {
    for (int i = 1; i < n; i++) {
        for (int j = i - 1; j>=0; j--) {
            if (arr[j] < arr[i]) {
                swap(arr[j], arr[i]);
                i = j;
            }
            else
                break;
        }
        for (int i = 0; i < n; i++)
            cout << arr[i] << " ";
        cout << endl;
    }
}

注释：for输出数组为测试代码，上面那个二重循环才是主代码
优化1，针对上述代码中的往前找找到比他小的就交换位置，这里就不采用交换函数，而是先把数组第i位置上的值赋值给一个临时变量，在比较的过程中就直接往后移位即可，最后再把临时变量赋值给空出来的位置上。

template<typename T>
void insertSort(T arr[], int n) {
    for (int i = 1; i < n; i++) {
        T temp = arr[i];
        int j = i - 1;
        for (; j>=0; j--) {
            if (arr[j] < temp) {
                arr[j + 1] = arr[j];
            }
            else
                break;
        }
        arr[j + 1] = temp;
        for (int i = 0; i < n; i++)
            cout << arr[i] << " ";
        cout << endl;
    }
}

总结：选择排序和插入排序都是O(n^2)级别的算法，选择排序对于数据量大的情况所耗费的时间较多，每次都是循环一部分找最值，插入排序稍微好一些，存在提前中止循环的情况。

排序算法1=选择+插入

全站热榜