python 算法之快速排序-python基础

快速排序

快速排序是由东尼·霍尔元件所发展趋势的一种快速排序算法。在均值情况下，排列 n 个新项目要 Ο(nlogn) 次较为。在最坏情况下则必须 Ο(n2) 次较为，但这类情况并不普遍。实际上，快速排序一般显著比别的 Ο(nlogn) 优化算法更快，因为它的內部循环系统（inner loop）能够在绝大多数的构架上很高效率的被完成出去。

快速排序应用分治法（Divide and conquer）对策来把一个串行通信（list）分成2个子串行（sub-lists）。

快速排序也是一种分而治之观念在快速排序算法上的典型性运用。实质上看来，快速排序应当算作在冒泡排序基本上的递归分治法。

快速排序的姓名起的是简单直接，由于一听见这一姓名你就知道它存在的价值，便是快，并且高效率！它是解决互联网大数据更快的快速排序算法之一了。尽管 Worst Case 的算法复杂度做到了 O(n²)，可是别人便是出色，在大部分状况下都比均值算法复杂度为 O(n logn) 的快速排序算法主要表现要更强，但是这是为什么呢，我不知道。好在我的强迫思维又犯了，查了 N 多材料总算在《算法艺术与信息学竞赛》上找到令人满意的回答：

快速排序的最坏运作状况是 O(n²)，例如次序数列的灭火吹。但它的分摊期待时间 O(nlogn)，且 O(nlogn) 标记中暗含的参量因素不大，比复杂性平稳相当于 O(nlogn) 的归并排序要小许多。因此，对绝大部分次序性较差的随机数字列来讲，快速排序一直好于归并排序。

优化算法流程

从数列中挑出来一个原素，称之为 “标准”（pivot）;
再次排列数列，全部原素比基准值小的摆在标准前边，全部原素比基准值大的摆放在标准的后边（同样的数能够上任一边）。在这个系统分区撤出以后，该标准就处在数列的正中间部位。这一称之为系统分区（partition）实际操作；
递归地（recursive）把低于基准值原素的子数列和超过基准值原素的子数列排列；

递归的最底端情况，是数列的尺寸是零或一，也就是始终都早已被排列好啦。尽管一直递归下来，可是这一优化算法总是会撤出，由于在每一次的迭代更新（iteration）中，它最少会把一个原素摆放在它最终的部位去。

Python 编码完成

def quickSort(arr, left=None, right=None):
    left = 0 if not isinstance(left,(int, float)) else left
    right = len(arr)-1 if not isinstance(right,(int, float)) else right
    if left < right:
        partitionIndex = partition(arr, left, right)
        quickSort(arr, left, partitionIndex-1)
        quickSort(arr, partitionIndex 1, right)
    return arr

def partition(arr, left, right):
    pivot = left
    index = pivot 1
    i = index
    while  i <= right:
        if arr[i] < arr[pivot]:
            swap(arr, i, index)
            index =1
        i =1
    swap(arr,pivot,index-1)
    return index-1

def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]

快速排序

优化算法流程

Python 编码完成

关键字：