// 冒泡排序
// 最差时间复杂度 ---- O(n^2)
// 最优时间复杂度 ---- 如果能在内部循环第一次运行时,使用一个旗标来表示有无需要交换的可能,可以把最优时间复杂度降低到O(n)
// 平均时间复杂度 ---- O(n^2)
// 所需辅助空间 ------ O(1)
// 稳定性 ------------ 稳定
void bubble_sort(vector<int>& x) {
    for (int i = 0; i < x.size() - 1; ++i) {    //i只是一个计数作用，不是下标，而且只需要遍历x.size()-1次就可以了
    for (int j = 0; j < x.size() - i - 1; ++j) { //这里j要小于x.size()-i-1，因为只要遍历到倒数第二个元素就可以了
            if (x[j] > x[j + 1]) 
                swap(x[j], x[j + 1]);

        }
    }
}

// 选择排序
// 最差时间复杂度 ---- O(n^2)
// 最优时间复杂度 ---- O(n^2)
// 平均时间复杂度 ---- O(n^2)
// 所需辅助空间 ------ O(1)
// 选择排序是不稳定的排序算法，不稳定发生在最小元素与A[i]交换的时刻。
void SelectSort(vector<int>& x) {
    for (int i = 0; i < x.size(); ++i) {
        int max_pos = 0;
        for (int j = 0; j < x.size() - i; ++j){
            max_pos = x[max_pos] < x[j] ? j : max_pos;
        }
        swap(x[max_pos],x[x.size() - 1 - i]);
    }
}

// 插入排序
// 最差时间复杂度 ---- 最坏情况为输入序列是降序排列的,此时时间复杂度O(n^2)
// 最优时间复杂度 ---- 最好情况为输入序列是升序排列的,此时时间复杂度O(n)
// 平均时间复杂度 ---- O(n^2)
// 所需辅助空间 ------ O(1)
// 稳定性 ------------ 稳定
void InsertSort(vector<int> & x) {
    for (int i = 1; i < x.size(); ++i) {
        int j = i;
        while (j>0&& x[j] < x[j - 1]) {  //注意j>0 要在x[j] < x[j - 1] 前面！！要先判断j>0
            swap(x[j], x[j - 1]);
            j--;
        }

    }
}

// 最差时间复杂度 ---- 根据步长序列的不同而不同。已知最好的为O(n(logn)^2)
// 最优时间复杂度 ---- O(n)
// 平均时间复杂度 ---- 根据步长序列的不同而不同。
// 所需辅助空间 ------ O(1)
// 稳定性 ------------ 不稳定 希尔排序是不稳定的排序算法，虽然一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱。
void ShellSort(vector<int> &x) {
    int gap = x.size() / 2;
    while (gap >= 1) {
        for (int i = 0; i < gap; ++i) {  //一共有gap组
            for (int j = i+gap; j < x.size(); j = j + gap) { //每组执行一次直接插入排序
                int k = j;
                while (k-gap>=0 && x[k] < x[k - gap]) {  
                    swap(x[k], x[k - gap]);
                    k-=gap;
                }
            }
        }
        gap /= 2;
    }
}

// 最差时间复杂度 ---- O(nlogn)
// 最优时间复杂度 ---- O(nlogn)
// 平均时间复杂度 ---- O(nlogn)
// 所需辅助空间 ------ O(n)
// 稳定性 ------------ 稳定
void Merge(vector<int>&x, int left, int mid, int right) {
    int len = right - left + 1;
    vector<int> temp(len,0);
    int i = left, j = mid + 1, index = 0;
    while (i <= mid && j <=right) {
        temp[index++] = x[i] > x[j] ? x[j++] : x[i++]; // x[i] > x[j]保证归并排序的稳定性
    }
    while (i <= mid)
        temp[index++] = x[i++]; //别忘了i++
    while (j <= right)
        temp[index++] = x[j++];//别忘了j++
    for (i = 0; i < len; ++i) {
        x[left++] = temp[i];
    }
}
void MergeSort(vector<int>&x, int left, int right) {
    if (left == right)// 当待排序的序列长度为1时，递归开始回溯，进行merge操作
        return;
    int mid = (left + right) / 2;
    MergeSort(x, left, mid);
    MergeSort(x, mid+1, right);
    Merge(x, left, mid, right);
}
void MergeSortInteration(vector<int>&x) {
    int left, mid, right;
    for (int i = 1; i < x.size(); i*=2) { //i从1开始，每次i*=2，表示先11合并，再22合并，再44合并...
        int left = 0;
        while (left + i < x.size()) {
            mid = left + i - 1;
            right = mid + i <= x.size() - 1 ? mid + i : x.size() - 1; // 后一个子数组大小可能不够
            Merge(x, left, mid, right);
            left = right + 1;
        }
    }
}

// 最差时间复杂度 ---- 每次选取的基准都是最大（或最小）的元素，导致每次只划分出了一个分区，需要进行n-1次划分才能结束递归，时间复杂度为O(n^2)
// 最优时间复杂度 ---- 每次选取的基准都是中位数，这样每次都均匀的划分出两个分区，只需要logn次划分就能结束递归，时间复杂度为O(nlogn)
// 平均时间复杂度 ---- O(nlogn)
// 所需辅助空间 ------ 主要是递归造成的栈空间的使用(用来保存left和right等局部变量)，取决于递归树的深度，一般为O(logn)，最差为O(n)       
// 稳定性 ---------- 不稳定
int Partition(vector<int>&x, int left, int right) { 
    //int index = RandomInRange(left,right);
    //swap(x[index],x[right]);
    //直接以最后一个元素作为基准
    int small = left - 1;
    for (int i = left; i < right; ++i) { //i<right 即可，因为i==right 是最后一个元素，即基准
        if (x[i] < x[right]) {
            small++;
            swap(x[i], x[small]);
        }
    }
    small++;
    swap(x[small], x[right]);
    return small;
}
void QuickSort(vector<int>&x,int left,int right) {
    if (left >= right)
        return;
    int index = Partition(x, left, right);
    if (index > left)
        QuickSort(x, left, index-1);
    if (index < right)
        QuickSort(x, index + 1, right);
}

// 最差时间复杂度 ---- O(nlogn)
// 最优时间复杂度 ---- O(nlogn)
// 平均时间复杂度 ---- O(nlogn)
// 所需辅助空间 ------ O(1)
// 稳定性 ------------ 不稳定 堆排序是不稳定的排序算法，不稳定发生在堆顶元素与A[i]交换的时刻。
void build_heap(vector<int> &nums, int i, int heap_tail_index){//对以节点i为根节点的子树进行调整，调整为大顶堆
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    if (left <= heap_tail_index && nums[left] > nums[i])
    {
        swap(nums[left], nums[i]);                  //vector这个对象存在栈中，然后栈中有指向vector所存数据的地址，数据保存在堆中。
        build_heap(nums, left, heap_tail_index);    //交换之后都可能造成被交换的孩子节点不满足堆的性质，因此每次交换之后要重新对被交换的孩子节点进行调整
    }

    if (right <= heap_tail_index && nums[right] > nums[i])
    {
        swap(nums[right], nums[i]);
        build_heap(nums, right, heap_tail_index);
    }
}
void heap_sort(vector<int> &nums)
{
    for (int i = (nums.size() - 1) / 2; i >= 0; i--)//应该是(nums.size()-1)/2，而不是nums.size()/2 -1
    {                                               //先初始化最大堆 ，从下往上调整
        build_heap(nums, i, nums.size()-1);
    }
    for (int i = nums.size() - 1; i >= 0;)          //依次调整堆的大小（堆末尾元素对应的数组索引i) i--
    {
        swap(nums[0], nums[i]);
        i--; 
        build_heap(nums, 0, i);
    }
}