常见排序算法原理及实现——第二部分（归并排序、快速排序、堆排序）

// 快速排序
int Partion(vector<int>&nums, int start, int end)
{
    int povit = nums[start]; // 这里选取第一个元素为基准点pivot
    while(start < end){
      // 从最后一个元素往前遍历，找到第一个小于等于基准点的元素，注意start < end
        while (start < end && nums[end] > povit) end--;
        nums[start] = nums[end];
    // 从第一个元素往后遍历，找到第一个大于基准点的元素，注意start < end
        while (start < end && nums[start] <= povit) start++;
        nums[end] = nums[start];
    }
    // 将基准点放到合适的位置
    nums[start] = povit; 
    // 返回修正后的基准点的下标位置
    return start;  
}
// @param nums： 待排序原始数据
// @param start：第一个元素的下标
// @param end：  最后一个元素的下标
void QuickSort(vector<int>&nums, int start, int end)
{
    if (start < end){
        int mid = Partion(nums, start, end);
        QuickSort(nums, start, mid-1);  // 递归处理pivot左边
        QuickSort(nums, mid+1, end); // 递归处理pivot左边
    }
    return;
}
int main()
{
    vector<int> nums = {20, 5, 3, 11, 6, 8, 7, 2};
    QuickSort(nums, 0, 7);
    cout << "QuickSort: " << endl;
    for (int i = 0; i < nums.size(); i++){
        cout << nums[i] << " " ;
    }
    cout << endl;
  return 0;
}

void QuickSortGetKth(vector<int>&nums, int start, int end, int k){
    if (start < end){
        int mid = Partion(nums, start, end);
        if (mid == k-1){
            cout << "the k is: " << nums[mid] << endl;
            return ;
        }
        else if(mid > k-1)
        {
            QuickSortGetKth(nums, start, mid-1, k);
        }else
        {
            QuickSortGetKth(nums, mid+1, end, k);
        }
    }
    return;
}

递推公式：
MergeSort(start, end) = Merge(MergeSort(start, mid),  MergeSort(mid+1, end));
终止条件：
start >= end 不再继续分解

// 归并排序
void Merge(vector<int>& nums, int start, int mid, int end) // 合并函数
{
    int i = start, j = mid+1, k = 0;
    vector<int> tmp(end-start+1);  // 开辟临时空间
    while (i <= mid && j <= end)
    {
        if (nums[i] <= nums[j])
        {
            tmp[k++] = nums[i++];
        }
        else{
            tmp[k++] = nums[j++];
        }
    }
    while (i <= mid){
        tmp[k++] = nums[i++];
    }
    while (j <= end){
        tmp[k++] = nums[j++];
    }   
    for (int i = 0; i < end-start+1; i++){
        nums[i+start] = tmp[i];
    }
    return;
}
void MergeSort(vector<int>& nums, int start, int end)
{
    if (start >= end) return;
    int mid = start + ((end - start) >> 1);
    MergeSort(nums, start, mid);  // 继续分解前半部分，直到不满足分解条件
    MergeSort(nums, mid+1, end);
    Merge(nums, start, mid, end);
    return ;
}
int main()
{
    vector<int> nums = {20, 5, 3, 11, 6, 8, 7, 2};
    MergeSort(nums, 0, 7);
    cout << "MergeSort: " << endl;
    for (int i = 0; i < nums.size(); i++){
        cout << nums[i] << " " ;
    }
    cout << endl;
  return 0;
}

// 堆排序
void AdjustHeap(vector<int>&nums, int i, int size){
    int maxIdx = i;
    int lChild = 2*i+1, rChild = 2*i+2;
    if (lChild < size && nums[lChild] > nums[maxIdx]){
        maxIdx = lChild;
    }
    if (rChild < size && nums[rChild] > nums[maxIdx]){
        maxIdx = rChild;
    }
    if (maxIdx != i){
        swap(nums[maxIdx], nums[i]);
        AdjustHeap(nums, maxIdx, size);
    }
    return;
}
void BuildHeap(vector<int>&nums, int size)
{
    for (int i = size/2-1; i >= 0; i--){
        AdjustHeap(nums, i, size);
    }
    return;
}
void HeapSort(vector<int>&nums)
{
    int size = nums.size();
    BuildHeap(nums, size); 
    for (int i = size-1; i >= 0; i--){
        swap(nums[0], nums[i]); // 将堆顶元素与“最后一个元素交换”，继续调整
        AdjustHeap(nums, 0, i); // 注意这里i的变化
    }
    return;
}
int main()
{
    vector<int> nums = {20, 5, 3, 11, 6, 8, 7, 2};
    HeapSort(nums);
    cout << "Heap Sort: " << endl;
    for (int i = 0; i < size; i++){
        cout << nums[i] << " " ;
    }
    cout << endl;
  return 0;
}