算法步骤：

• 从数列中跳出一个元素，成为“基准”
• 重新排序数列，所有元素比基准小的放在基准前面，比基准大的放在后面，相等的放在任意一边，在这个分区退出后，基准处于数列中间位置，这个被称为分区操作
• 递归的把小序列、大序列进行上述排序

代码实现

// 快速排序
public void QuickSort(int[] arr, int left, int right)
{
    if (left >= right)
    {
        return;
    }
    int L = left;
    int R = right;
    int pivot = arr[left]; // 选取第一个元素作为 pivot
    while (left < right)
    {
        while (right > left && arr[right] >= pivot) // 先右标志向左推进
        {
            right -= 1;
        }
        if (arr[right] < pivot)// 右标志停下来，要么是右标志和左标志重合，要么是右标志的值小于 pivot了，如果是后者，需要将左标志的值换成此时右标志的。
        {
            arr[left] = arr[right];
        }
        while (left < right && arr[left] < pivot) // 接下来左标志向右推进
        {
            left += 1;
        }
        if (arr[left] >= pivot)
        {
            arr[right] = arr[left];
        }
        if (left == right)
        {
            arr[left] = pivot;
        }
    }
    QuickSort(arr, L, left - 1);  // 前后关系无所谓
    QuickSort(arr, right + 1, R);
}

// 快速排序
public static void Quick(int[] arr, int begin, int end)
{
    if(begin < end)
    {
        int key = arr[begin];
        int i = begin;
        int j = end;

        while(i < j)
        {
            while(i < j && arr[j] > key)
            {
                --j;
            }
            if(i < j)
            {
                arr[i] = arr[j];
                ++i;
            }
            while(i < j && arr[i] < key)
            {
                ++i;
            }

            if(i < j)
            {
                arr[j] = arr[i];
            }
        }
        arr[i] = key;

        Quick(arr, begin, i - 1);
        Quick(arr, i + 1, end);
    }
}

结果截图

算法复杂度

	最好	最坏	平均	空间复杂度	稳定不？
快速排序					不稳定

参考链接

⭐⭐

⭐⭐