JZTXT

十大排序算法

发布时间 2023-03-26 22:09:59作者: real010
  • 冒泡排序
    从序列的一端开始往另一端冒泡，依次比较相邻的两个数的大小。代码实现如下
void sort(vector<int>& vec) {
    for (int i = 0; i < vec.size() - 1; ++i) {
        for (int j = 0; j < vec.size() - i - 1; ++j) {
            int tem;
            if (vec[j] > vec[j + 1])
                swap(vec[j], vec[j + 1]);
        }
    }
}

时间复杂度为\(O(n^2)\)，空间复杂度\(O(1)\)
还可以进一步对冒泡排序进行优化，当进行一轮交换操作之后，如果没有两个逆序对，则证明序列此时已经有序，退出循环即可。代码如下

void sort(vector<int>& vec) {
    for (int i = 0; i < vec.size() - 1; ++i) {
        bool flag = true;
        for (int j = 0; j < vec.size() - i - 1; ++j) {
            int tem;
            if (vec[j] > vec[j + 1]) {
                flag = false;
                swap(vec[j], vec[j + 1]);
            }
        }
        if (flag)
            break;
    }
}
  • 选择排序
    遍历数组，每次挑选出最大的放到数组末尾，代码如下
void sort(vector<int>& vec) {
    for (int i = 0; i < vec.size(); ++i) {
        int min = i;
        for (int j = i; j < vec.size(); ++j) {
            if (vec[j] < vec[min]) {
                min = j;
            }
        }
        swap(vec[i], vec[min]);
    }
}

时间复杂度为\(O(n^2)\)，空间复杂度\(O(1)\)

  • 插入排序
void sort(vector<int>& vec) {
    for (int i = 1; i < vec.size(); ++i) {
        int val = vec[i];
        int j;
        for (j = i - 1; j >= 0; --j) {
            if (vec[j] < val) {
                break;
            }
            vec[j + 1] = vec[j];
        }
        vec[j + 1] = val;
    }
}

下标i将数组分为两部分，i之前的数组已经有序，将vec[i]在\([0,i-1]\)范围内寻找合适位置进行插入。时间复杂度也为\(O(n^2)\)