排序总结

归并排序

tmp数组作为参数传递，减少创建数组的空间消耗

void merge(vector<int>& nums, int l, int mid, int r, vector<int>& tmp) {
    int cnt = l;    // 辅助指针，排序后的元素先放在tmp，最后再存回nums
    int i = l, j = mid + 1; // 左区间和右区间的指针
    while (i <= mid && j <= r) {
        if (nums[i] <= nums[j]) {   // 这里是小于等于
            tmp[cnt++] = nums[i++];
        }
        else {
            tmp[cnt++] = nums[j++];
        }
    }
    while (i <= mid) tmp[cnt++] = nums[i++];
    while (j <= r) tmp[cnt++] = nums[j++];
    for (int k = l; k <= r; k++) {  // [l,r]
        nums[k] = tmp[k];
    }
}

void mergeSort(vector<int>& nums, int l, int r, vector<int>& tmp) {
    if (l == r) return; // [l,r]左闭右闭区间，只有一个元素就直接返回
    int mid = l + (r - l) / 2;
    mergeSort(nums, l, mid, tmp);       // 左区间 [l, mid]
    mergeSort(nums, mid + 1, r, tmp);   // 右区间 [mid+1, r]
    merge(nums, l, mid, r, tmp);        // 合并左右区间
}

int main(int argc, char const *argv[])
{
    vector<int> nums = {4, 1, 3, 2, 5};
    vector<int> tmp(nums.size());
    mergeSort(nums, 0, nums.size() - 1, tmp);
    return 0;
}
1 2 3 4 5

时间复杂度：$O(nlogn)$，由于归并排序每次都将当前待排序的序列折半成两个子序列递归调用，然后再合并两个有序的子序列，而每次合并两个有序的子序列需要$O(n)$的时间复杂度，所以可以列出归并排序运行时间$T(n)$的递归表达式

$$T(n) = 2T(\frac{n}{2}) + O(n)$$

根据主定理可以得出归并排序的时间复杂度为$O(nlogn)$

空间复杂度：$O(n)$，需要$O(n)$空间的tmp数组，且递归调用的层数最深为$log_2 n$，所以还需要额外的$O(logn)$的栈空间，所以空间复杂度是$O(n+logn)=O(n)$

冒泡排序

每一轮都选出剩下的元素中最大的那个，并移动到最后

• 优化1：如果这一轮没有发生交换，说明全都是有序的了，可以退出

void bubbleSort(vector<int>& nums) {
    int n = nums.size();
    for (int i = 0; i < n - 1; i++) {
        bool flag = true;
        for (int j = 0; j < n - 1 - i; j++) {
            if (nums[j] > nums[j + 1]) {
                swap(nums[j], nums[j + 1]);
                flag = false;
            }
        }
        if (flag) break;    // 没有发生交换，说明都是有序的了
    }
}

• 优化2：如果只是前面少量无效，后面都是有序的，就可以不用进行后面那些的比较，所以只要记录无序的最大长度

void bubbleSort(vector<int>& nums) {
    int n = nums.size();
    int len = nums.size() - 1;
    int maxIndex = 0;
    for (int i = 0; i < n - 1; i++) {
        bool flag = true;
        for (int j = 0; j < len; j++) { // 只需要遍历无序部分
            if (nums[j] > nums[j + 1]) {
                swap(nums[j], nums[j + 1]);
                flag = false;
                maxIndex = j;   // 记录无序的最大范围
            }
        }
        len = maxIndex;
        if (flag) break;
    }
}

时间复杂度：$O(n^2)$
空间复杂度：$O(1)$

快速排序

以最右边的元素或者随机选取一个元素作为pivot，把小于pivot的放在左边，大于等于pivot的放在右边，递归处理

void quickSort(vector<int>& nums, int l, int r) {
    if (l >= r) return;
    int pivot = nums[r];
    int i = l;  // i前面的都是小于pivot的元素
    for (int j = l; j <= r; j++) {
        if (nums[j] < pivot) {  // 如果小于pivot就跟nums[i]交换
            swap(nums[i], nums[j]);
            i++;
        }
    }
    swap(nums[i], nums[r]); // 最后把pivot换到中间
    quickSort(nums, l, i - 1);  // 递归处理左区间[l, i-1]
    quickSort(nums, i + 1, r);  // 递归处理右区间[i+1, r]
}

int main(int argc, char const *argv[])
{
    vector<int> nums = {4, 1, 3, 2, 5};
    vector<int> tmp(nums.size());
    quickSort(nums, 0, nums.size() - 1);
    return 0;
}
1 2 3 4 5

时间复杂度：$O(nlogn)$
空间复杂度：$O(h)$，其中$h$为快速排序递归调用的层数

堆排序

• buildHeap先执行一次，将最开始的数组构建为大根堆
• heapify保证每个父节点都大于子节点
• 每次heapify之后，nums[0]都是最大值，把和最后一个节点交换，然后再对0的位置重新heapify，重复n次

void heapify(vector<int>& nums, int i, int n) {
    int l = 2 * i + 1, r = 2 * i + 2;   // 左右节点
    int max = i;
    if (l < n && nums[l] > nums[i]) max = l;
    if (r < n && nums[r] > nums[i]) max = r;
    if (max != i) {
        swap(nums[i], nums[max]);   // 交换
        heapify(nums, max, n);  // 交换后需要对子节点heapify
    } 
}

void buildHeap(vector<int>& nums, int n) {
    for (int i = n / 2; i >= 0; i--) {  // 从最后一个元素的父节点开始heapify
        heapify(nums, i, n);
    }
}

void heapSort(vector<int>& nums) {
    int n = nums.size();
    buildHeap(nums, n); // 先建一个大根堆
    for (int i = n - 1; i >= 0; i--) {
        swap(nums[0], nums[i]); // 每次把堆顶元素移到最后，然后再把剩下的元素从堆顶元素开始重新heapify
        heapify(nums, 0, i);
    }
}

int main(int argc, char const *argv[])
{
    vector<int> nums = {3, 2, 1, 4, 5};
    heapSort(nums);
    return 0;
}
1 2 3 4 5

时间复杂度：$O(nlogn)$，初始化建堆buildHeap的时间复杂度为$O(n)$，建完堆后需要进行$n-1$次调整，一次调整heapify的时间复杂度为$O(logn)$，所以$n-1$次调整的时间复杂度为$O(nlogn)$，总时间复杂度为$O(n+nlogn)=O(nlogn)$
空间复杂度：$O(1)$