排序数组

描述

给你一个整数数组 nums，请你将该数组升序排列。

示例 1：

输入：nums = [5,2,3,1]
输出：[1,2,3,5]
示例 2：

输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]

提示：

1 <= nums.length <= 5 * 104
-5 * 104 <= nums[i] <= 5 * 104

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/sort-an-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

C++代码

快速排序：

这是一个基于快速排序算法的解决方案，它将数组分为两个子数组，其中一个子数组的所有元素都比另一个子数组的所有元素小，然后递归地对这两个子数组进行排序。

在这个实现中，我们定义了一个quicksort函数来执行快速排序，它接受三个参数：要排序的数组，子数组的左边界和右边界。我们还定义了一个sortArray函数来调用quicksort函数并返回排序后的数组。

在quicksort函数中，我们首先检查左边界是否大于或等于右边界，如果是，则返回。否则，我们选择第一个元素作为枢轴，并将左指针i初始化为左边界加1，右指针j初始化为右边界。然后，我们使用while循环将左指针i和右指针j移动，直到它们相遇。在循环中，我们检查左指针i指向的元素是否小于枢轴，并检查右指针j指向的元素是否大于枢轴。如果是这样，我们就交换这两个元素，并将左指针i和右指针j分别向右和向左移动。如果左指针i指向的元素大于或等于枢轴，则将左指针i向右移动。如果右指针j指向的元素小于或等于枢轴，则将右指针j向左移动。

最后，我们交换枢轴和右指针j指向的元素，并递归地对左子数组和右子数组进行快速排序。

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
    	quickSort(nums, 0, (int)nums.size() - 1);
    	return nums;
    }
    void quickSort(vector<int>& nums, int start, int end) {
        if (start >= end) return;
        int pivot = nums[start], i = start + 1, j = end;
        while (i <= j) {
            if (nums[i] > pivot && nums[j] < pivot) {
                swap(nums[i++], nums[j--]);
            }
            if (nums[i] <= pivot) ++i;
            if (nums[j] >= pivot) --j;
        }
        swap(nums[start], nums[j]);
        quickSort(nums, start, j - 1);
        quickSort(nums, j + 1, end);
    }
};

归并排序：

归并排序的思想跟快速排序比较类似，但也不完全一样，这里其实是一种先对半分，一直不停的对半分，直到分到只有一个数字的时候返回，然后在返回的途中进行合并，合并的时候用到了一个临时数组 tmp，先将区间 [start, end] 中的数字按顺序存入这个临时数组 tmp 中，然后再覆盖原数组中的对应位置即可。

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        mergeSort(nums, 0, nums.size() - 1); // 调用归并排序函数
        return nums;
    }

    void mergeSort(vector<int>& nums, int left, int right) {
        if (left < right) {
            int mid = (right - left)/2 + left; // 获取中间位置
            mergeSort(nums, left, mid); // 递归排序左半部分
            mergeSort(nums, mid+1, right); // 递归排序右半部分
            merge(nums, left, mid, right); // 合并两个有序数组
        }
    }

    void merge(vector<int>& nums, int left, int mid, int right) {
        int n1 = mid - left + 1; // 左半部分数组长度
        int n2 = right - mid; // 右半部分数组长度
        vector<int> L(n1), R(n2); // 创建左右两个临时数组

        // 将原数组的左半部分和右半部分分别复制到临时数组中
        for (int i = 0; i < n1; i++) {
            L[i] = nums[left + i];
        }
        for (int j = 0; j < n2; j++) {
            R[j] = nums[mid + 1 + j];
        }

        // 合并两个有序数组
        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                nums[k++] = L[i++];
            } else {
                nums[k++] = R[j++];
            }
        }

        // 将剩余的元素复制到原数组中
        while (i < n1) {
            nums[k++] = L[i++];
        }
        while (j < n2) {
            nums[k++] = R[j++];
        }
    }
};