题解 | #排序#

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

//符合题目要求的排序算法有：希尔排序、快速排序、堆排序、归并排序
//一次快速排序函数Quick_one()
void Quick_sort(int *arr,int start,int end) //依次是数组、数组中排序开始位置、排序结束位置
{
    if(start>=end)
        return;
    int i=start,j=end;
    int temp=arr[i];  //让第一位作为中枢分割开，排序后数组左边的值都小于等于该中枢，右边的值则都大于等于。
    while(i<j)
    {
        while(i<j && arr[j]>temp)
        {
            j--;
        }
        if(i<j)
        {
            arr[i]=arr[j];
            i++;
        }
        while(i<j && arr[i]<temp)
        {
            i++;
        }
        if(i<j)
        {
            arr[j]=arr[i];
            j--;
        }
    }
    arr[i]=temp;//此处完成后，一次快排完成。
    //递归快排中枢的左右两个数组
    Quick_sort(arr,start,j-1);
    Quick_sort(arr,j+1,end);
}
int* MySort(int* arr, int arrLen, int* returnSize ) {
    // write code here
    * returnSize =arrLen;
    Quick_sort(arr,0,arrLen-1);
    return arr;
}