排序算法

快排

#include <iostream>
#include<bits/stdc++.h>
using namespace std;

int partition(vector<int>& nums,int l,int r){

        int mid = (l+r)>>1;
        swap(nums[l],nums[mid]);
        int pivot = nums[l];
        while(r>l){
            while(r>l&&nums[r]>=pivot)
                --r;
            nums[l]=nums[r];
            while(r>l&&nums[l]<=pivot)
                ++l;
            nums[r]=nums[l];
        }
        //出来这里 l==r
        nums[l]=pivot;
        return l;
    }
void quickSort(vector<int>& arr,int l,int r){
    //递归出口
    if(r<=l) return;
    int pivot_index = partition(arr,l,r);
    //排序左半边
    quickSort(arr,l,pivot_index-1);
    //排序右半边
    quickSort(arr,pivot_index+1,r);
}
int main()
{
    vector<int> v = {0,0,1,2,4,2,998,2021,2,3,1,4};
    quickSort(v,0,v.size()-1);
    for(auto& a:v)
        cout<<a<<" ";
    return 0;
}

堆排序

#include <iostream>
#include<bits/stdc++.h>
using namespace std;

const int maxn = 100; // 限定堆的最大容量为100
int n;  // 堆内元素个数
vector<int>heap(100,0); // 以大顶堆为例 底层实际存在元素的容器是数组

//上浮函数 调整区间[low,high]之间的元素
void upAdjust(int low,int high){
    int i = high, j = i/2;  // 记j为i的父节点
    while(j>=low){
        //当前节点大于其父节点则交换
        if(heap[i]>heap[j]){
            swap(heap[i],heap[j]);
            i = j;
            j = i/2;

        }
        //否则的话 已经有序 不用继续调整
        else break;
    }
}

void downAdjust(int low,int high){
    int i = low, j = i*2;  //记j为i的左孩子
    while(j<=high){
            //如果有右孩子并且值比左孩子大
            //修改j为右孩子
        if(j+1<=n && heap[j+1]>heap[j]){
            j = j+1;
        }

        //当前节点与较大的那个孩子交换
        if(heap[i]<heap[j]){
            swap(heap[i],heap[j]);
            i = j;
            j = i*2;
        }
        //否则 已经有序 无需继续下调
        else break;
    }
}

int main()
{
    //给定的一组无序数据
    vector<int> v = {0,0,1,2,4,2,998,2021,2,3,1,4};
    //初始化空堆
    n = 0;
    //往堆中放入各节点
    for(int i=0;i<v.size();++i){
        //新加入的节点在最末尾 然后上浮调整
        heap[++n]=v[i];
        upAdjust(1,n);

    }
    //排序结果
    while(n>0){
        cout<<" "<<heap[1];
        //输出堆顶元素后 取最末尾元素覆盖堆顶 然后再下沉调整
        heap[1]=heap[n--];
        downAdjust(1,n);
    }
    return 0;
}

归并排序

#include <iostream>
#include<bits/stdc++.h>
using namespace std;

void merge_(vector<int>& nums,int l,int r){
    int mid = (l+r)>>1;
    int left = l, right = mid + 1;
    //中间数组暂存元素
    vector<int>tmp;
    //左半段到mid位置结束 右半段到r位置结束
    while(left<=mid && right<= r){
        if(nums[left]<=nums[right])
            tmp.push_back(nums[left++]);
        else tmp.push_back(nums[right++]);
    }
    //剩余没处理完的部分
    while(left<=mid){
        tmp.push_back(nums[left++]);
    }
    while(right<=r){
        tmp.push_back(nums[right++]);
    }
    //注意填回到原数组的位置
    for(int i=0;i<tmp.size();++i){
        nums[l++] = tmp[i];
    }
}

//对区间[l,r]之间的元素排序
void mergeSort(vector<int>& nums,int l,int r){
    //结束递归
    if(l>=r) return;
    int mid = (l+r)>>1;
    //划分成两部分 分别归并排序
    mergeSort(nums,l,mid);
    mergeSort(nums,mid+1,r);

    //左右两部分都有序了 将它们合并
    merge_(nums,l,r);
}

int main()
{
    //给定的一组无序数据
    vector<int> v = {0,0,1,2,4,2,998,2021,2,3,1,4};
    //vector<int>v = {3,1,2};
    mergeSort(v,0,v.size()-1);
    for(auto& a:v)
        cout<<" "<<a;
    return 0;
}