快速排序:简称快排,是利用分治的思想而衍生出来的一种排序算法。通过把待排序数组的元素分成两部分,其中一部分的元素均大于(或小于)另一部分的元素,然后再对该两组元素执行该操作,直到数组有序。

实现

这里我用递归实现的(虽然我很不喜欢递归,但是我更不愿意自己去实现栈,实在是没想到别的替代方案),是原地排序,通过不断分割数组,取第一个元素为“中间元素”,左边的元素均小于“中间元素”,不断递归直到完成排序。

以递增排序为例


C语言实现

Leetcode上917.排序数组中测试通过(效率还行...
KSsort_1

int* sortArray(int* nums, int numsSize, int* returnSize)
{
    *returnSize = numsSize;
    sort(nums,0,numsSize-1);
    return nums;
}

void sort(int* arr, int l, int r)
{
    //保证数组:右<=med     左>med
    if (r <= l){
        return;
    }
    int med = arr[l];
    int i = l + 1, j = r;

    while (i < j)
    {
        if (arr[i] > med) 
        {
            if(arr[j] > med)
            {
                j--;
            }
            else
            {
                arr[i]=arr[i]^arr[j];
                arr[j]=arr[i]^arr[j];
                arr[i]=arr[i]^arr[j];
            }
        }
        else
        {
            i++;
        }
    }

    if (i == r) 
    {
        if (arr[l] > arr[r])
        {
                arr[l]=arr[l]^arr[r];
                arr[r]=arr[l]^arr[r];
                arr[l]=arr[l]^arr[r];
        }
        sort(arr, l, r -1);
    }
    else if (i == l)
    {
        sort(arr, l + 1, r);
    }
    else
    {
        sort(arr, l, i-1);
        sort(arr, i, r);
    }
    
    return;
}

C++实现

Leetcode上917.排序数组中测试通过(效率非常高???
KSsort_2

vector<int> sortArray(vector<int>& nums)
{
    sort(nums.data(),0,nums.size()-1);
    return nums;
}

void sort(int* arr, int l, int r)
{
    //保证数组:右<=bas     左>bas
    if (r <= l){
        return;
    }
    int med = arr[l];
    int i = l + 1, j = r;

    while (i < j)
    {
        if (arr[i] > med) 
        {
            if(arr[j] > med)
            {
                j--;
            }
            else
            {
                swap(arr[i], arr[j]);
            }
        }
        else
        {
            i++;
        }
    }

    if (i == r) 
    {
        if (arr[l] > arr[r])
        {
            swap(arr[l], arr[r]);
        }
        sort(arr, l, r -1);
    }
    else if (i == l)
    {
        sort(arr, l + 1, r);
    }
    else
    {
        sort(arr, l, i-1);
        sort(arr, i, r);
    }
    
    return;
}
Last modification:April 15th, 2020 at 09:11 am