给你一个整数数组 nums，请你将该数组升序排列。
你必须在 不使用任何内置函数 的情况下解决问题，时间复杂度为 O(nlog(n))，并且空间复杂度尽可能小。
我用的是快速排序。
示例 1：
输入：nums = [5,2,3,1]
输出：[1,2,3,5]
解释：数组排序后，某些数字的位置没有改变（例如，2 和 3），而其他数字的位置发生了改变（例如，1 和 5）。
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
void swapNum(int *num1, int *num2) {
int temp = *num1;
*num1 = *num2;
*num2 = temp;
}
void quickSort(int *arr, int left, int right) {
int i = left, j = right;
int mid = (left + right) / 2;
int base = arr[mid];
while (i <= j) {
while (arr[i] < base) {
i++;
}
while (arr[j] > base) {
j–;
}
if (i <= j) {
swapNum(arr + i, arr + j);
i++;
j–;
}
}
if (left < j) {
quickSort(arr, left, j);
}
if (i < right) {
quickSort(arr, i, right);
}
}
int* sortArray(int* nums, int numsSize, int* returnSize) {
*returnSize = numsSize;
int *arr = (int *)malloc(sizeof(int) * numsSize);
for (int i = 0; i < numsSize; i++) {
arr[i] = nums[i];
}
quickSort(arr, 0, numsSize – 1);
return arr;
}
