踏踏实实地打好算法基础(3)—快速排序算法-一一网

快速排序(Quick Sort)

算法和冒泡排序算法类似，都是基于交换排序思想。快速排序算法对冒泡排序算法进行了改进，从而具有更高的执行效率。

快速排序算法

首先设定一个分界值(pivot),分界值选择是任意随机没有任何限制，通过该分界值将数组分成左右两部分
将大于分界值放在数据集中到数组右边，小于分界值的数据集中到数组的左边。
然后左边和右边的数据可以独立排序，对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分
重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两部分各数据排序完成后，整个数组的排序也就完成了。

基本思想

分而治之的思想将问题分解为多个子问题，通过递归方式，不断划分数组直至将问题分解为足够简单来解决

首先在数组中选择一个元素作为 pivot 这里就选择 4 作为 pivot
然后分别设定两个指针位于数组的两侧
首先从左侧开始移动左侧的指针来到 6 因为 6 比 4 大所以将 6 和 4 位置交换

接下来开始移动右侧指针，移动方向从右向左
当指针来到 3 时候我们发现 3 小于 4，我们需要保证在右侧的元素要大于 4 所以就进行将 3 和 4 进行交换。
交换完后，再去移动左侧指针将左侧指针向右侧移动一个位置
因为 5 大于 4 说以就需要将 4 和 5 位置进行交换

接下来还是去移动右侧指针，向左移动一个位置来到 1 ，1 又小于 4 所以继续进行交换
当完成交换后再去移动左侧指针发现这一次指针重合在一个位置，这样边结束了一轮迭代

演示

这里选择 2 做 pivot 作为标准值
然后在数组两端分别放置一个指针，这两个指针相对而行
首先我们将右侧指针向左侧移动，当移动到值大于或者等于标准值，也就是 pivot 值就继续向前移动知道

当从右侧出发指针找到了比标准值小的值就停下来
然后左侧指针开始出发找比标准值大值，2 等于标准值所继续向前(右侧)前进来 5 ，5 比 2 大所以从左侧出发指针就停在 5 位置
然后判断两个指针是否指向同一个位置

完成交换之后，现在轮到开始移动右侧指针，右侧指针继续向前移动一个位置，这时两个指针重叠
接下来就将 2 和两个指针位置的值进行交换完成第一次迭代

现在数组被 2 pivot 切分为两个部分，2 左侧的数据元素都小于 2 而 2 右侧数据元素都大于 2

时间复杂度

最坏情况为 $O(n^2)$
最理想或者平均 $O(n\log(n))$

class Solution:

    def quickSort(self,nums,left,right):
        if (left >= right):
            return
        p = nums[left]
        i = left
        j = right
        while (i != j):
            while (j > i) and nums[j] > p:
                j -= 1
            nums[i],nums[j] = nums[j],nums[i]
            while (i < j) and nums[i] <= p:
                i += 1
            nums[i],nums[j] = nums[j],nums[i]
        self.quickSort(nums,left,i-1)
        self.quickSort(nums,i+1,right)
        # print(nums)
        
    def quickArraySort(self,nums):
        left = 0
        right = len(nums) - 1
        self.quickSort(nums,left,right)

复制代码