快速排序

快速排序

syndi

2019 年 03 月 18 日

917 次浏览

暂无评论

908字数

以下内容转自https://blog.csdn.net/k_koris/article/details/80585979

1. 快速排序之单路快排

首先选择数组中的一个元素，比如用l索引指向最左边的元素v，逐渐遍历数组所有位于l左边的元素，在遍历的过程中，我们将逐渐整理出小于v的元素和大于v的元素，当然我们继续用一个索引j来记录小于v和大于v的分界点，然后我们当前访问的元素索引为i。

那么i怎么处理呢？很简单当i指向的元素e大于v的时候，直接包含进大于v的部分中，像这样：

如果元素e小于v的时候怎么做呢？只需要把元素e和橙色部分之后的一个元素交换，就可以了，此时索引j++。如图：

最后i继续往后走，到最后的时候就直接将数组分成了等于v，小于v，大于v的三部分。
最后将l位置和j位置交换，就实现了快速排序的子过程，如图：

#include <stdio.h>

void swap(int* i, int* j) {
    int tmp = *i;
    *i = *j;
    *j = tmp;
}

int partition(int* arr, int l, int r) {
    int key = arr[l];
    int i, j;
    j = l;
    for(i = j+1; i<=r; i++) {
        if(arr[i] < key) {
            swap(&arr[i], &arr[j+1]);
            j++;
        }
    }
    swap(&arr[l], &arr[j]);
    return j;
}

void __quick_sort(int* arr, int l, int r) {
    int key;

    if(l < r) {
        key = partition(arr, l, r);
        __quick_sort(arr, l, key-1);
        __quick_sort(arr, key+1, r);
    }
}

void quick_sort(int* arr, int size) {
    __quick_sort(arr, 0, size-1);
}

int main(int argc, char const *argv[])
{
    int arr[] = {2, 4, 1, 1, 7, 9, 3, 6, 5, 8};
    int i;
    quick_sort(arr, sizeof(arr) / sizeof(int));
    for(i = 0; i<10; i++) 
        printf("%d\n", arr[i]);
    return 0;
}

2. 快速排序之双路快排

和快排不同的是此时我们将小于v和大于v的元素放在数组的两端，那么我们将引用新的索引j的记录大于v的边界位置。如图：

i索引不断向后扫描，当i的元素小于v的时候继续向后扫描，直到碰到了某个元素大于等于v。j同理，直到碰到某个元素小于等于v。如图：

然后绿色的部分便归并到了一起，而此时只要交换i和j的位置就可以了

这里有一个十分重要的地方，如果你的基准选取的是最左边的元素的话，那么，一定要先让j向前寻找第一个比v小的元素，再让i向后寻找第一个比v大的元素，这个顺序一定不能搞反。为什么呢？可以想到，当这个进程进行到最后i与j交汇的时候，我们需要像普通快排一样把位于第一位的基准v和这个交汇位置的元素交换，而只有交汇位置的元素是小于基准v的时候这个交换才是合乎逻辑的，否则若交汇位置元素大于v却被交换到了第一位，那排序肯定就错了。那么如何保证这个交汇位置的元素一定是小于v的呢？当然，就是像之前所说的那样，先进行j从后往前的搜索，再进行i从前往后的搜索。

下面是代码，其实双路快排只需要把普通快排的partition函数改写就行了

#include <stdio.h>

void swap(int* i, int* j) {
    int tmp = *i;
    *i = *j;
    *j = tmp;
}

int partition(int* arr, int l, int r) {
    int key = arr[l];
    int i = l, j = r;  // 这里i必须初始化成l，错了很多次了，如果初始化为l+1，试想基准即最小元素的情况

    while(1) {
        while(i<j && arr[j]>=key) j--;
        while(i<j && arr[i]<=key) i++;
        if(i!=j)
            swap(&arr[i], &arr[j]);
        // 注意交换完两个元素的值后不能顺势让j-- i++，必须要重新回到上面的逻辑，先让j往左找，再让i往右找
                // 否则当i与j中间只有一个元素的时候，i++j--会指向这个元素
                // 但这个数作为最后要和基准交换的元素我们不能保证它一定比基准小
        else
            break;
    }
    swap(&arr[l], &arr[i]);
    return i;
}

void __quick_sort(int* arr, int l, int r) {
    int keyIndex;

    if(l < r) {
        keyIndex = partition(arr, l, r);
        __quick_sort(arr, l, keyIndex-1);
        __quick_sort(arr, keyIndex+1, r);
    }
}

void quick_sort(int* arr, int size) {
    __quick_sort(arr, 0, size-1);
}

int main(int argc, char const *argv[])
{
    int arr[] = {2, 4, 1, 1, 7, 9, 3, 6, 5, 8};
    int i;
    quick_sort(arr, sizeof(arr) / sizeof(int));
    for(i = 0; i<10; i++) 
        printf("%d\n", arr[i]);
    return 0;
}

3. 快速排序之挖坑法

挖坑法类似于双路快排，下面简要介绍一下挖坑法的思路。

假设还是取最左边的元素为pivot，则先记下来pivot的值供最后使用。现在pivot所在的位置看成一个“坑”，然后从右往左找第一个比pivot小的元素填充到坑里。此时看作那个比pivot小的元素之前的位置是一个”坑“，则再从左往右找第一个比pivot大的元素填充到坑里，重复上述步骤。最终左右指针相遇，即找到最后一个”坑“，此时将pivot填进坑里即可。

int partition2(int* arr, int left, int right) {
    int pivot = arr[left];  // base
    int l = left, r = right;

    while (1) {
        // 从右往左找第一个比pivot小的元素
        while (r > l && arr[r] >= pivot) {
            r--;
        }
        if (r > l) {  // 填坑
            arr[l] = arr[r];
        }

        // 从左往右找第一个比pivot大的元素
        while (r > l && arr[l] <= pivot) {
            l++;
        }
        if (r > l) {  // 填坑
            arr[r] = arr[l];
        }

        // 如果左右指针相遇，退出循环
        if (r == l) {
            arr[r] = pivot;
            break;
        }
    }

    return r;
}

void __quick_sort(int* arr, int left, int right) {
    if (left < right) {
        int pivotIndex = partition2(arr, left, right);
        __quick_sort(arr, left, pivotIndex - 1);
        __quick_sort(arr, pivotIndex + 1, right);
    }
}

void quick_sort(int* arr, int size) {
    __quick_sort(arr, 0, size - 1);
}

4. 快速排序非递归

用循环代替递归通常都要用栈模拟递归。而在快速排序中，栈中需要记录的应该是算出pivotIndex后的左右两个区间的边界。例如，先对整个区间做一次分割得到左右两个区间，然后先把右区间压栈再把左区间压栈。之后从栈中取出左区间继续分割得到左右两个区间，依此类推。

void quick_sort_stack(int* arr, int size) {
    int left = 0;
    int right = size - 1;
    Stack s;
    StackInit(&s);

    // 先把整个区间入栈，用以进入下面的循环
    StackPush(&s, right);
    StackPush(&s, left);

    while (!StackEmpty(&s)) {
        // 取出栈顶区间
        left = StackTop(&s);
        StackPop(&s);
        right = StackTop(&s);
        StackPop(&s);

        // 如果区间不止一个元素，则分割
        if (left < right) {
            int pivotIndex = partition(arr, left, right);

            // 保存右半部分区间
            StackPush(&s, right);
            StackPush(&s, pivotIndex + 1);

            // 保存左半部分区间
            StackPush(&s, pivotIndex - 1);
            StackPush(&s, left);
        }    
    }
}

快速排序