快速排序

发表于 更新于 分类于

关于快速排序的开始顺序

右指针不断左移直到找到比基准元素小的元素位置，而左指针不断右移直至找到比基准元素大的元素位置。

对于一般的快速排序，通常将最左边的元素a[0]作为基准元素，所以要先从右边扫描。

先从右边扫描最后停留的位置肯定是小于基准数的。因为右指针是找比基准数小的数，先停在比基准数小的数，因此左指针和右指针相遇的情况只能是右指针先停止，然后左指针向右扫描直到和右指针相遇，所以相遇的位置肯定是比基准数小的，然后这个数和基准数交换，这个数在基准数左边并小于基准数，此时符合快排规则

先从左边扫描最后停留的位置肯定是大于基准数的，因为左指针是找比基准数大的数，先停在比基准数大的数，左指针和右指针相遇的情况只能是左指针先停止，然后右指针向左扫描直到和左指针相遇，所以相遇的位置肯定是比基准数大的，然后这个数和基准数交换，这个数在基准数左边但大于基准数，此时不符合快排规则

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void quick_merge(int a[], int low, int high)
{
    if (low < high)
    {
        int pivot = partition(a, low, high);
        quick_merge(a, low, pivot - 1);
        quick_merge(a, pivot + 1, high);
    }
}

int partition(int a[], int low, int high)
{
    // 比较基准元素
    int pivot = a[low];
    while (low < high)
    {
        while (low < high && a[high] >= pivot)
            high--;
        a[low] = a[high];
        while (low < high && a[low] <= pivot)
            low++;
        a[high] = a[low];
    }
    a[low] = pivot;
    return low;
}