912. 排序数组

• 稳定排序：如果 a 原本在 b 前面，且 a == b，排序之后 a 仍然在 b 前面。
• 非稳定排序：如果 a 原本在 b 前面，且 a == b，排序之后 a 不一定在 b 前面。
• 原地排序 / 非原地排序：区别在于是否 使用额外的数组 辅助排序

快排

快排不稳定
平均时间复杂度\(O(n \log n)\)

简单快排

最差情况时间复杂度\(n^2\)

void QuickSortSimple(vector<int>& nums, int start, int end){
    if(start >= end) return;
    swap(nums[start], nums[rand() % (end - start + 1) + start]); // 基于随机的原则,随机选取一个值作为哨兵值
    int tmp = nums[start];
    int l = start, r = end;
    while(l<r){
        // 往左走
        while (l<r && nums[r] >= tmp) --r;          // 结束时，右边遇到第一个小于tmp的数字就交换
        // 往右走
        while (l<r && nums[l] <= tmp) ++l;          // 结束时，左边遇到第一个大于tmp的数字；加等号的意义：如果在前进的过程中出现了相等的元素，加上等号，就代表跳过，继续向右移动，不进行填坑
        if(l<r) swap(nums[r], nums[l]);                  // 右边填坑
    }
    // 两边相等了
    swap(nums[start], nums[l]);
    QuickSortSimple(nums, start, l-1);     // 左边区间
    QuickSortSimple(nums, l+1, end);      // 右边区间
}

三点中值（Median-Of-Three）快排

最差情况下时间复杂度为\(O(n \log n)\)

int choosePivot(vector<int>& nums, int start, int end){
        int mid = start+(end-start)/2;
        if(nums[start] > nums[mid]) swap(nums[start], nums[mid]);
        if(nums[start] > nums[end]) swap(nums[start], nums[end]);
        if(nums[mid] > nums[end]) swap(nums[mid], nums[end]);
        return nums[mid];
    }
void QuickSortMedianOfThree(vector<int>& nums, int start, int end){
    if(start >= end) return;
    // 三数取中
    int pivot = choosePivot(nums, start, end);
    int l = start, r = end;
    while(l <= r) {
        while(nums[l] < pivot) ++l;    // 从左边找到第一个大于哨兵的值 
        while(nums[r] > pivot) --r;    // 从右边找到第一个小于哨兵的值
        if(l <= r) {                                              // 如果小于，则交换位置，并双方向各自的前方移动一个位置
            swap(nums[l++], nums[r--]);
        }
    }
    // 此时r<l，哨兵左边都是小于该哨兵值，右边都是大于该哨兵值
    QuickSortMedianOfThree(nums, start, r);
    QuickSortMedianOfThree(nums, l, end);
}

归并排序

稳定
时间复杂度\(O(n \log n)\)

自顶向下

// 自顶向下
void mergeSort(vector<int>& nums, int l, int r){
    if(l>=r) return ;
    int mid = l + (r-l) /2;
    mergeSort(nums, l, mid);                    // 递归到最左端
    mergeSort(nums, mid+1, r);                  // 递归到最右端，子区间只有一个元素
    int i=l, j = mid+1;
    int cnt =0;
    while(i<=mid && j<= r)temp[cnt++] = nums[i] < nums[j] ? nums[i++] : nums[j++];                      // 将两个右序数组合并到一个temp数组
    while(i<= mid) temp[cnt++] = nums[i++];
    while(j<= r) temp[cnt++] = nums[j++];
    for(int i=0; i< r-l+1; i++){ nums[i+l] = temp[i];
}

自底向上

// 自底向上
vector<int> sortArray(vector<int>& nums) {
    if(nums.size()==1) return nums;
    int n = nums.size();

    for(int size=1; size< n; size *= 2){
        for(int start =0; start < n-size; start += 2*size){
            int mid = start + size -1;
            int end = min(start + size * 2 -1,  n-1);
            merge(nums, start, mid, end);
        }
    }
    return nums;
}
void merge(vector<int>&nums, int start, int mid, int end){
    vector<int> temp(end-start+1, 0);
    int i=start, j = mid+1;
    int cnt=0;
    while(i<= mid && j <= end) temp[cnt++] = nums[i]<nums[j] ? nums[i++] : nums[j++];
    while(i<=mid) temp[cnt++] = nums[i++];
    while(j<=end) temp[cnt++] = nums[j++];
    for(int i=0; i< cnt; ++i){
        nums[start+i] = temp[i]; 
    }
}

堆排

大顶堆

// len显示调整的区间长度
// holeIndex为开始节点，len为结束节点 
void AdjustHeap(vector<int>& nums, int holeIndex, int len){
    while(holeIndex*2+1 < len){     // 左孩子节点要小于总节点数量，只要没有超出范围就一直向下调整大小关系
        int lchild = holeIndex * 2+1;
        int rchild = lchild + 1;
        int large = holeIndex;
        if((lchild < len) && nums[lchild] > nums[holeIndex])  large = lchild;       // 左节点大于父节点
        if((rchild < len) && nums[rchild] > nums[large])  large = rchild;           // 右节点大于父节点大于左节点
        if(large != holeIndex){
            swap(nums[holeIndex], nums[large]);
            holeIndex = large; // 将替换的孩子作为新洞
        }
        else break;   // 父节点都大于子节点，退出
    }
}
void MakeHeap(vector<int>& nums){
    int len = nums.size();
    // 找出第一个需要重排的子树头部，任何叶子节点不需要执行下溯：将子节点和其较大子节点“对调”，并持续下放，直到叶子节点
    // 数组array中如果当前节点为i，则左节点为2i+1，右节点为2i+2，父节点位于i/2处：#0元素使用
    int holeIndex = (len-1) / 2;        // 最右端叶子节点的父节点下标
    for(int i = holeIndex; i>=0; i--){
        AdjustHeap(nums, i, len);
    }
}
int main(){
    vector<int> nums = {-2, 45, 0, 11, -9, 7};
    MakeHeap(nums);                     // 创建一个大顶堆
    int len = nums.size()-1;
    for(int i=len; i>=0;i--){
        swap(nums[i], nums[0]);          // 将堆顶元素放到数组最后面，此时堆已经不是大顶堆了，需要重新调整堆的结构
        --len;                              // 调整范围[0, --len)
        AdjustHeap(nums, 0, len);           // 只调整堆顶元素就可以
    }

    for(auto& c:nums){
        cout << c <<" " ;
    }
    cout <<endl;
}

冒泡排序

时间复杂度\(O(n^2)\)

// n个长度数组长度要排n-1次
void bubblesort(vector<int>& nums){
    int n = nums.size();
    for(int i=0;i<n-1;i++){ // 当前元素
        bool flag = false;
        for(int j=0; j<n-1-i;j++){      // n-1-i后面的元素表示已经排序完成
            if(nums[j]>nums[j+1]) {
                swap(nums[j], nums[j+1]);   // 将大的元素交换到最后面
                flag = true;
            }
        }
        if(flag == false) break;
    }
}