题解 | #NC140-排序，时间复杂度O(nlogn)#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 将给定数组排序
 * @param arr int整型一维数组 待排序的数组
 * @param arrLen int arr数组长度
 * @return int整型一维数组
 * @return int* returnSize 返回数组行数
 */

/*快速排序算法思想
* step1：从数组中选择一个中轴元素，把数组中所有小于等于中轴元素的元素放到中轴元素左侧
* 把所有大于中轴元素的元素放到中轴元素右侧，此时中轴元素所处位置是有序的（左侧比它小，右侧比它大）
* step2：根据中轴元素把大数组分割成2个小组（注意这2个小数组都不包含中轴元素）
* 接着用递归方法让中轴元素左边元素和中轴元素右边元素进行重复操作，直到数组大小为1
* step3：看不懂怎么办？先背下来。。。
****************************************************/

int partition(int *arr, int left, int right)
{
    int i = left+1;
    int j = right;
    int pivot = arr[left];//先假设中轴元素为第一个元素
    int tmp;
    
    while(1)
    {
        while(i <= j && arr[i] <= pivot) i++;//向右查找第一个大于piovt的元素
        while(i <= j && arr[j] >= pivot) j--;//向左查找第一个小于pivot的元素
        if(i >= j)
            break;
        //交换arr[i]和arr[j],使中轴元素左侧元素不大于中轴元素，中轴右侧元素不小于中轴元素
        tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
        
    arr[left] = arr[j];//i>j时，j的位置就是中轴元素的位置
    arr[j] = pivot;//把左边第一个元素挪到中轴元素位置arr[j] 
    return j;//返回中轴元素位置，下一步递归时使用
}


int *quickSort(int *arr, int left, int right)
{
    if(left < right)
    {
        //切换函数，找到中轴元素，并返回中轴元素位置
        int mid = partition(arr, left, right);
        //中轴元素左边元素(不包办中轴元素）进行快速排序
        arr = quickSort(arr, left, mid-1);
        //中轴元素右边元素（不包含中轴元素）进行快速排序
        arr = quickSort(arr, mid+1, right);
    }
    return arr;
}    

int* MySort(int* arr, int arrLen, int* returnSize ) {
    // write code here
    *returnSize = arrLen;
    quickSort(arr, 0, arrLen-1);
    
    return arr;
    
}