排序算法一

时间复杂度O(n^2)的典型排序算法有三个，冒泡排序、插入排序和选择排序，这三个排序算法最坏时间复杂度都达到了n^2。

冒泡排序是从第一个元素第二个元素开始，每次相邻的两个元素做对比，将较大的元素交换上去，这样一轮下来最大的元素就排到最上面去了，最上面那个元素就固定住了，不参与后面的排序了，再开启下一轮排序，也是从第一个元素第二个元素开始，进行比较交换操作，将次大的元素排上去，等于是每排一轮就排好一个元素，n轮下来就排好序了。其中每排一轮加起来要比较n-1+n-2+n-3+…+1+0=n*(n-1)/2次，这是最坏的情况，当其中某一轮排序未交换任何元素时，说明全部元素已经是排好序的状态，所以最好的情况就是排一轮就达到有序状态，只需要比较n-1次。

void BubbleSort(std::vector<int>& arr) {
    int n = arr.size();

    // 外层循环控制轮数
    for (int i = 0; i < n - 1; ++i) {
        // 内层循环控制每轮比较和交换
        for (int j = 0; j < n - i - 1; ++j) {
            // 如果相邻元素逆序，则交换它们
            if (arr[j] > arr[j + 1]) {
                std::swap(arr[j], arr[j + 1]);
            }
        }
    }
}

插入排序是分两个区进行处理，一个已排序区，一个未排序区，初始化时已排序区就只有第一个元素，从剩余的元素即未排序区取第一个元素插入到已排序区的合适位置，让已排序区始终保持排序的状态，最坏的情况，从未排序区取一个元素插入到已排序区时，需要从已排序区最末尾一个元素开始比较，一直比较到已排序区的第一个元素，每个未排序元素都要如此比较才能选到已排序区的合适位置，这样算下来总共需要比较的次数为1+2+3+…+n-1=n*(n-1)/2，其实这就是完全逆序的情况，而最好的情况就是完全有序的情况，每次比较已排序区最末尾一个元素就找到插入的位置了，只要插入到已排序区末尾就行了，总共有n-1次，这样算下来只需要比较n-1次。

void InsertSort(vector<int>& nums, int n) {
    for (int i = 1; i < n; ++i) {
        int temp = nums[i];
        int j = i - 1;

        while (j >= 0 && nums[j] > temp) {
            nums[j + 1] = nums[j];
            --j;
        }

        nums[j + 1] = temp;
    }
}

选择排序也是分已排序区和未排序区进行处理，不过不一样的是，每次都是从未排序区选择最小或最大的元素，直接放到已排序区的首部或末尾，说起来和插入排序很类似，但关键点在于，从未排序区选择一个最值，必须遍历完未排序区全部的元素才行，而插入排序在最好的情况下，只需要插入到已排序区的末尾就行了，所以选择排序最好最坏时间复杂度都是n-1+n-2+…+1=n*(n-1)/2。

看起来冒泡排序和插入排序时间复杂度都差不多，但其实还有一些细微的差异，主要表现在具体实现上，冒泡排序比较完两个元素需要进行交换时，需要有三步，int tmp=a; a=b;b=tmp;，而插入排序比较完后，只需要把元素往后移动一位即可，a[i+1]=a[i]，这样就能把前面的位置空出来，真正找到要插入的位置后，将空出来的这个位置填入要插入的值即可，这样对比起来，插入排序只需要一步。所以在追求极致性能的情况下，还是优先选择插入排序。

void SelectSort(vector<int>& nums,int n)
{
    // 遍历数组
    // 外层循环 for(int i=0;i<n-1;i++) 中的 n-1 是合理的，因为最后一个元素无需再参与比较和交换。
    for (int i = 0; i < n - 1; i++) {
        // 找到未排序部分的最小元素
        int min = i;
        for (int j = i + 1; j < n; j++) {
            if (nums[j] < nums[min]) min = j;
        }
        // 将找到的最小元素移动到已排序部分的末尾
        if (min != i) swap(nums[i], nums[min]);
    }
}

这三种排序算法最坏的情况下时间复杂度都达到了O(n^2)，都属于原地排序算法，即空间复杂度均为O(1)，不会随着数据量的变大而变大，但是选择排序是不稳定的排序算法，因为每次从未排序区选择最值后，都会与未排序区的第一个元素进行交换，该未排序区的第一个元素也是紧接着已排序区最后一个元素的位置，如果未排序区的第一个元素为未排序区里面多个重复元素中的一个，这个元素就会被交换到最值的位置，所以相同元素的位置可能就发生了变化，还是插入排序靠谱，每次都插入到大于等于的元素之后，就能保证相同的元素还是按照原来的顺序排列的。

综上所述，根据排序效率，是否稳定排序等方面来考虑，优先选择插入排序。