【数据结构与算法】快速排序

[buckrudy]

快速排序

快速排序使用分治法（Divide and conquer）策略。选择一个基准值来把一个序列分为较小和较大的2个子序列，然后递归地排序两个子序列。

步骤为：

1. 挑选基准值：从数列中挑出一个元素，称为“基准”（pivot）
2. 分割：重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（与基准值相等的数可以到任何一边）。在这个分割结束之后，对基准值的排序就已经完成
3. 递归排序子序列：递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。

排序过程图解

代码实现

void _quickSort(int a[], int start, int end)
{
    int left = start;
    int right = end;
    int pivot = a[start];

    if (start >= end)
        return;

    while (left < right) {
        while (a[right] >= pivot && left < right)   // 从右向左找小于基站值的元素
            right--;

        if (left != right)
            a[left++] = a[right];

        while (a[left] <= pivot && left < right)  // 从左向右找大于基准值的元素
            left++;

        if (left != right)
            a[right--] = a[left];
    }
    //循环结束时，left == right
    a[left] = pivot;    //将基准值放回数列中

    _quickSort(a, start, left-1);
    _quickSort(a, right+1, end);
}

// a 数组
// len 数组长度
void quickSort(int a[], int len)
{
    _quickSort(a, 0, len-1);
}

算法复杂度

快速排序的平均算法复杂度为 O(n log n)。
快速排序是不稳的排序，所谓稳定性是指：排序前，数据中两个相等的数之前的前后位置在排序完成后不发送变化。例如 A[i] == A[j], 排序前，A[i] 在 A[j] 的前面，排序后，A[i] 任在 A[j] 的前面，则是稳定的。