lancelei

基础排序算法之——快速排序算法
前几天,班上的小伙伴面试,问到了快速排序算法,闲来无事,正好整理一下自己知道的会用的算法,毕竟知识不用,遗忘的也...
扫描右侧二维码阅读全文
24
2018/10

基础排序算法之——快速排序算法

 前几天,班上的小伙伴面试,问到了快速排序算法,闲来无事,正好整理一下自己知道的会用的算法,毕竟知识不用,遗忘的也很快

快速排序(英语:Quicksort),又称划分交换排序(partition-exchangesort),简称快排,一种排序算法,最早由东尼·霍尔提出。
时间复杂度:在平均状况下,排序n个项目要O(n log n)(大O符号)次比较。在最坏状况下则需要O(n^2)次比较,但这种状况并不常见。事实上,快速排序O(n log n)通常明显比其他算法更快,因为它的内部循环(innerloop)可以在大部分的架构上很有效率地达成。

很多资料上都把算法说明说的很啰嗦,又是序列子序列,又是基准的,照例,还是先贴上官方说明,然后我再用小白一眼就能看懂的文字说明一下。

快速排序使用分治法(Divide and conquer)策略来把一个序列(list)分为两个子序列(sub-lists)。 步骤为:
1、从数列中挑出一个元素,称为“基准”(pivot),
2、重新排序数列,所有比基准值小的元素摆放在基准前面,所有比基准值大的元素摆在基准后面(相同的数可以到任何一边)。在这个分割结束之后,该基准就处于数列的中间位置。这个称为分割(partition)操作。
3、递归地(recursively)把小于基准值元素的子数列和大于基准值元素的子数列排序。
4、递归到最底部时,数列的大小是零或一,也就是已经排序好了。这个算法一定会结束,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。

好了,我简单用文字叙说一下上面的深奥语言。快速排序,其实不快,毕竟时间复杂度O(n log n)在那儿呢,但是为什么看上去明显比其他同样是O(n log n)复杂度的算法,排序要快呢,那是因为这个算法内部的循环效率很高,所以,会比其他同复杂度算法要快很多。
快速排序是怎么排的呢。想象一下,现在你是XX中学高一的班主任,你面前站着N个才上高中的小P孩。现在你组织他们到操场集合,为了很快的让他们按照从矮到高的顺序一字排开,你现在要想一个办法。好了,参照上面官方的步骤,我来说说快排的想法是怎么排的。
1:你瞄一眼大家的身高,然后找一个感觉上不高不矮,中等身高的孩子。他的名字叫“基准”。
2、拿出你手中的高音喇叭,对着这群熊孩子喊:“所有比“基准”高的人站在他的前面,所有比他矮的人站在他的后面。”大家哗哗哗的站好了。这时,“基准”就在所有熊孩子的中间了。
3、然后,在基准前面的熊孩子中,你又选了一个看上去应该是他们中身高在中间的孩子,我们就叫他小A吧。按照2的步骤,再来一次,这时,所有比小A矮的熊孩子就站在了小A的前面,所有比小A高的站在了小A的后面。不断的重复重复,计算机语言就是递归。分割的孩子越来越少,知道小A前面的孩子全部都分割——排队、分割——排队之后,继续这种方式,分割小A后面至基准前面的孩子。同理,比基准高的孩子也是这样分割——排队。
4、分割到最后,也就是身高最高的两个熊孩子都分割OK了,没有新的熊孩子队伍需要分割了,他们也就按照高矮顺序排好了。


啰啰嗦嗦的讲了个故事,不知道各位想明白这个逻辑没有。这里我放一个演示图给大家,想想我讲的故事,因该就能看出来这个动图是怎么一回事了。
10dalunce-7231.gif

现在,我把用C++和java语言写的算法代码给大家研究研究。其中,C++使用迭代和递归两种方法(迭代和递归看这里http://lancelei.com/archives/91/)。Java同理,写出一种给大家看看就好,另外一种自己研究去。


C语言

迭代

// 参考:http://www.dutor.net/index.php/2011/04/recursive-iterative-quick-sort/
struct Range {
    int start, end;
    Range(int s = 0, int e = 0) {
        start = s, end = e;
    }
};
template <typename T> // 整数或浮点数皆可使用,若要使用物件(class)时必须设定"小于"(<)、"大于"(>)、"不小于"(>=)的运算子功能
void quick_sort(T arr[], const int len) {
    if (len <= 0)
        return; // 避免len等于负值时程序崩了
    // r[]模拟堆叠,p为数量,r[p++]为push,r[--p]为pop且取得元素
    Range r[len];
    int p = 0;
    r[p++] = Range(0, len - 1);
    while (p) {
        Range range = r[--p];
        if (range.start >= range.end)
            continue;
        T mid = arr[range.end];
        int left = range.start, right = range.end - 1;
        while (left < right) {
            while (arr[left] < mid && left < right) left++;
            while (arr[right] >= mid && left < right) right--;
            std::swap(arr[left], arr[right]);
        }
        if (arr[left] >= arr[range.end])
            std::swap(arr[left], arr[range.end]);
        else
            left++;
        r[p++] = Range(range.start, left - 1);
        r[p++] = Range(left + 1, range.end);
    }
}
   

递归

template <typename T>
void quick_sort_recursive(T arr[], int start, int end) {
    if (start >= end)
        return;
    T mid = arr[end];
    int left = start, right = end - 1;
    while (left < right) { //在整个范围内搜寻比枢纽元值小或大的元素,然后将左侧元素与右侧元素交换
        while (arr[left] < mid && left < right) //试图在左侧找到一个比枢纽元更大的元素
            left++;
        while (arr[right] >= mid && left < right) //试图在右侧找到一个比枢纽元更小的元素
            right--;
        std::swap(arr[left], arr[right]); //交换元素
    }
    if (arr[left] >= arr[end])
        std::swap(arr[left], arr[end]);
    else
        left++;
    quick_sort_recursive(arr, start, left - 1);
    quick_sort_recursive(arr, left + 1, end);
}
template <typename T>
void quick_sort(T arr[], int len) {
    quick_sort_recursive(arr, 0, len - 1);
}

不建议重复的造轮子,但是,在用别人现成的轮子之前,还是先建议先学习别人轮子怎么造的,最好模仿着造一个轮子自己重复用。毕竟,别人的终究是别人的,只有自己的,才是自己的。
放个大招~~~~

函数法

 sort(a,a+n);//排序a[0]-a[n-1]的所有数.

JAVA版本

public class Application {

    public static void qSort(int[] arr, int head, int tail) {
        if (head >= tail || arr == null || arr.length <= 1) {
            return;
        }
        int i = head, j = tail, pivot = arr[(head + tail) / 2];
        while (i <= j) {
            while (arr[i] < pivot) {
                ++i;
            }
            while (arr[j] > pivot) {
                --j;
            }
            if (i < j) {
                int t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
                ++i;
                --j;
            } else if (i == j) {
                ++i;
            }
        }
        qSort(arr, head, j);
        qSort(arr, i, tail);
    }

    public static void main(String[] args) {
        int[] arr = new int[]{1, 4, 8, 2, 55, 3, 4, 8, 6, 4, 0, 11, 34, 90, 23, 54, 77, 9, 2, 9, 4, 10};
        qSort(arr, 0, arr.length - 1);
        String out = "";
        for (int digit : arr) {
            out += (digit + ",");
        }
        System.out.println(out);
    }
}

结语

大致上快速排序就是那么个意思了,完结撒花

Last modification:October 24th, 2018 at 05:02 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment