常用排序算法

一、快速排序

void splitArray(int arr[], const int start, const int end)
{
    if(start >= end)
    {
        return;
    }

    int left = start + 1; //用第一个元素做为基数，并拿出来，将剩下的数按这个基数，分开
    int right = end;
    int key = arr[start];
    while (left < right)
    {
        if(key <= arr[right]) //先从右往左找第一个大于key的值，退出循环时，left=right,在传入数组是需要分开的情况，此值应该是小于key的值,从小到大排序，所以先找这个，退出时
        {                       //和key值的元素交换。在传入数组是已经分开的情况下，此下标就是start+1，也是left
            right--;           //先从右往左，是因为从小到大排序，小的在左边，大的在右边。数组需要划分的情况下，退出时应当是小于key的数与arr[start]进行交换
            continue;
        }

        if(key >= arr[left])
        {
            left++;
            continue;
        }

        arr[left] = arr[left] ^ arr[right];
        arr[right] = arr[left] ^ arr[right];
        arr[left] = arr[left] ^ arr[right]; //交换后arr[right]就大于等于key了，下一次循环会继续找下一个；left同理
    }//退出时left==right;当数组传进来就有序时，arr[right]就是start+1，可能不是小于key的；不是有序时，arr[right]小于key。所以需要判断再交换
    if(key > arr[right])
    {
        arr[start] = arr[start] ^ arr[right];
        arr[right] = arr[start] ^ arr[right];
        arr[start] = arr[start] ^ arr[right];
    }

    std::cout << "left " << left << "; right " << right << std::endl;
    splitArray(arr, start, right - 1);
    splitArray(arr, right + 1, end);
}

int quickSort(int arr[], const int k)
{
    if(nullptr == arr)
    {
        return -1;
    }

    splitArray(arr, 0, k - 1);
    return 0;
}