排序算法

LeetCode解题记录

快速排序

先整体有序，再局部有序。

思路

选取其中一个值 pivot，（通过头尾双指针向中间相向查找，左右分别找到一个不合适的值，进行交换，）使数组分成两部分[A] pivot [B]，其中 [A] 里的值 <= pivot， [B]里的值 >= pivot。再将 [A] 和[B] 分别重复这个操作，直到完成整个排序。

注意点

void quickSort(std::vector<int>& nums, const int start, const int end);

• 判断结束

  if (start >= end) return;

• pivot 一般选择中间点

  int pivot = nums[(start + end) / 2];

• 为了让两边数组尽量均分(主要针对多个相同值的极端情况)，使[A] 里的值 <= pivot， [B]里的值 >= pivot 。所以左边指针遇到不满足的情况，也就是 nums[left] > pivot 才停，而右边指针遇到 nums[right] < pivot才停。

  while (left <= right && nums[left] > pivot) left++;
  while (left <= right && nums[right] < pivot) right++;

• while 循环结束时，right < left，所以下层排序起始点分别为 [start, right]和 [left, end]

完整代码

class Solution {
private:
    void quickSort(vector<int>& nums, const int start, const int end)
    {
        if (start >= end) return;

        int left = start;
        int right = end;
        int pivot = nums[(start + end) / 2];

        int temp;
        while (left <= right)
        {
            while (left <= right && nums[left] < pivot)
            {
                left++;
            }
            while (left <= right && nums[right] > pivot)
            {
                right--;
            }
            if (left <= right)
            {
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
                left++;
                right--;
            }
        }

        quickSort(nums, start, right);
        quickSort(nums, left, end);
    }

public:
    vector<int> sortArray(vector<int>& nums) {
        quickSort(nums, 0, nums.size() - 1);
        return nums;
    }
};

归并排序

先局部有序，再整体有序。

思路

分治法(而非二分) 每层递归将数组分为两部分，使其分别有序；对于两个有序数列，再使用双指针算法排序（到临时数组空间，再复制回原本数组中）。

注意点

• 由于每次需要临时数组，为了不重复开辟空间，可以直接传入

完整代码

class Solution {
private:
    void mergeSort(vector<int> &nums,
                   vector<int> &temp,
                   const int start,
                   const int end)
    {
        if (start >= end) return;

        int mid = (start + end) / 2;
        mergeSort(nums, temp, start, mid);
        mergeSort(nums, temp, mid + 1, end);

        int left = start;
        int right = mid + 1;
        int index = 0;
        while (left <= mid && right <= end)
        {
            auto &i = (nums[left] <= nums[right]) ? left : right;
            temp[index++] = nums[i++];
        }

        while (left <= mid) temp[index++] = nums[left++];
        while (right <= end) temp[index++] = nums[right++];

        for (int i = 0; i <= index - 1; i++)
        {
            nums[i + start] = temp[i];
        }
    }

public:
    vector<int> sortArray(vector<int>& nums) {
        vector<int> temp_vec(nums.size());
        mergeSort(nums, temp_vec, 0, nums.size() - 1);
        return nums;
    }
};