排序算法之快速排序

作者: 盗梦者_56f2 | 来源:发表于2018-11-13 15:49 被阅读10次

    介绍

    快速排序,又称划分交换排序,简称快排,这种排序算法,最早由东尼·霍尔提出。

    演示

    Sorting_quicksort

    复杂度

    最坏时间复杂度:O(n^2)
    最优时间复杂度:O(nlog n)
    平均时间复杂度:O(n
    log n)
    最坏空间复杂度:根据实现的方式不同而不同

    步骤

    快速排序使用分治法策略来把一个序列分为两个子序列。
    步骤为:

    1. 从数列中挑出一个元素,称为基准,
    2. 重新排序数列,所有比基准值小的元素摆放在基准前面,所有比基准值大的元素摆在基准后面(相同的数可以到任何一边)。在这个分割结束之后,该基准就处于数列的中间位置。这个称为分割操作。
    3. 递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。

    递归到最底部时,数列的大小是零或一,也就是已经排序好了。这个算法一定会结束,因为在每次的迭代中,它至少会把一个元素摆到它最后的位置去。

    python

    def quick_sort(li):
        if len(li) <= 1:
            return li
        else:
            pivot = li[0]
            less = quick_sort([i for i in li[1:] if i < pivot])
            more = quick_sort([i for i in li[1:] if i >= pivot])
            return less + [pivot] + more
    print(quick_sort(li))
    

    java

    public static void quickSort(List<Integer> items) {
            if(items.size() > 1) {
                List<Integer> smaller = new ArrayList<>();
                List<Integer> same = new ArrayList<>();
                List<Integer> larger = new ArrayList<>();
                Integer chosenItem = items.get(items.size() / 2);
                for(Integer i: items) {
                    if(i < chosenItem)
                        smaller.add(i);
                    else if(i > chosenItem)
                        larger.add(i);
                    else
                        same.add(i);
                }
                quickSort(smaller);
                quickSort(larger);
                items.clear();
                items.addAll(smaller);
                items.addAll(same);
                items.addAll(larger);
            }
        }
    

    相关文章

      网友评论

        本文标题:排序算法之快速排序

        本文链接:https://www.haomeiwen.com/subject/dhllfqtx.html