排序

题目：

给定一个长度为 n 的数组，请你编写一个函数，返回该数组按升序排序后的结果。

示例:

输入：[5,2,3,1,4]

返回值：[1,2,3,4,5]

输入：[5,1,6,2,5]

返回值：[1,2,5,5,6]

方法：

快速排序

思路：

将当前数组中的第一个元素设为枢轴值。将小于枢轴值的元素移动到左端，将大于枢轴值的元素移动到右端，枢轴值放置在空出的位置上。递归上述过程直至所有元素放到其最终位置上。

```/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 将给定数组排序
 * @param arr int整型一维数组 待排序的数组
 * @param arrLen int arr数组长度
 * @return int整型一维数组
 * @return int* returnSize 返回数组行数
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
//快速排序
void QuickSort(int* arr, int low, int high){
    if (low < high){//递归跳出条件
        int pivotpos = Partition(arr, low, high);//划分
        QuickSort(arr, low, pivotpos - 1);     //依次对两个子表进行递归排序
        QuickSort(arr, pivotpos + 1, high);   
    }
}
int Partition(int* arr, int low, int high){
    int pivot = arr[low];//当前表中第一个元素设为枢轴值，对表进行划分
    while(low < high){//循环跳出条件
        while(low < high && arr[high] >= pivot)
            --high;
        arr[low] = arr[high];//将比枢轴值小的元素移动到左端
        while(low < high && arr[low] <= pivot)
            ++low;
        arr[high] = arr[low];//将比枢轴值大的元素移到右端
    }
    arr[low] = pivot;//枢轴元素存放最终位置
    return low;//返回存放枢轴的最终位置
}
int* MySort(int* arr, int arrLen, int* returnSize ) {
    // write code here
    QuickSort(arr, 0, arrLen - 1);
    *returnSize = arrLen;
    return arr;
}