Learning to be Giant.

Quick sort 实现笔记

|

说实话,作为一个程序员,对于一些基本算法竟然只停留在了理解层面上儿从来没曾实践过实在是可笑。为了弥补自己的这个问题,从今天开始我打算把一些常用的算法都实现一下,在实践当中进一步加深理解。

快速排序是分治法思想的一个典型应用,其原理就是通过将一组数据不断地分成两部分然后递归。具体原理可以参照网上的其他文章。

快速排序的平均时间复杂度是$O(nlogn)$,最差情况(原数列为目标数列的倒序)时间复杂度为$O(n^2)$。复杂度的推导可见网上的其他文章。

这里给出我的实现:

void partition(int * arr, size_t start, size_t end) {
    if (start + 1 >= end) return;
    size_t front = start, back = end - 1;
    int pivot = arr[start];
    while (front < back) {
        while (front < back && arr[back] >= pivot) back--;
        arr[front] = arr[back];
        while (front < back && arr[front] <= pivot) front++;
        arr[back] = arr[front];
    }
    arr[front] = pivot;

    partition(arr, start, pivot);
    partition(arr, pivot+1, end);
}

void quicksort(int * arr, size_t n) {
    partition(arr, 0, n);
}

这个地方简单记录一下,这个地方的想法其实是先把作为pivot的元素保存下来,然后用不符合要求的元素覆盖掉原本的pivot所在位置,最后将pivot放回原位。

Comments