快速排序语义化解法与改进-python描述

基本思想

基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
通过以上思路,我们可以很容易的想到以下解法:

  1. 将数据分为三部分:left(左),key(中),right(右)
  2. 左边的数据都小于key,右边的数据都大于key
  3. 对左右两边数据继续执行上述操作,直到每组只剩下一个数据
  4. 从栈中弹出所有数据返回

语义化解法

按照上述步骤可以很容易的写出以下代码:

class Solution:
    def QuickSort(self, arr):
        length = len(arr)
        if length <= 1:
            return arr
        left = []
        right = []
        key = arr[0]
        for i in range(1, length):
            if arr[i] > key:
                right.append(arr[i])
            else:
                left.append(arr[i])
        left = self.QuickSort(left)
        right = self.QuickSort(right)
        temp = []
        temp.extend(left)
        temp.extend([key])
        temp.extend(right)

        return temp

注意:for循环中要注意边界条件,因为key默认取数组第一个元素,所以要从第二个元素开始循环,否则将会无限递归。

上述代码根据定义一步一步实现,容易理解,易于实现,但是我们发现该算法开辟了更多的额外空间,有着较高的空间复杂度。直觉告诉笔者,该算法一定还有很多可以优化的地方,于是笔者经过分析与查阅资料,又找到了下面一种解题思路:

优化

设要排序的数组是A[0]……A[N-1],首先任意选取一个数据(通常选用数组的第一个数)作为关键数据,然后将所有比它小的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一趟快速排序。值得注意的是,快速排序不是一种稳定的排序算法,也就是说,多个相同的值的相对位置也许会在算法结束时产生变动。
一趟快速排序的算法是:

  1. 设置两个变量i、j,排序开始的时候:i=0,j=N-1;
  2. 以第一个数组元素作为关键数据,赋值给key,即key=A[0];
  3. 从j开始向前搜索,即由后开始向前搜索(j--),找到第一个小于key的值A[j],将A[j]和A[i]互换;
  4. 从i开始向后搜索,即由前开始向后搜索(i++),找到第一个大于key的A[i],将A[i]和A[j]互换;
  5. 重复第3、4步,直到i=j; (3,4步中,没找到符合条件的值,即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值,使得j=j-1,i=i+1,直至找到为止。找到符合条件的值,进行交换的时候i, j指针位置不变。另外,i==j这一过程一定正好是i+或j-完成的时候,此时令循环结束)。

优化代码如下

class Solution:
    def QuickSort(self, arr, low, height):
        i = low
        j = height
        if i >= j:
            return arr
        key = arr[i]
        while i < j:
            while arr[j] > key and i < j:
                j -= 1
            arr[i] = arr[j]
            while arr[i] <= key and i < j:
                i += 1
            arr[j] = arr[i]
        arr[i] = key
        self.QuickSort(arr, low, i-1)
        self.QuickSort(arr, j+1, height)
        return arr

该解法在原数组上进行操作,空间复杂度较低,优化合理。
笔者认为,两种解法思路上大同小异,第一种更容易理解,第二种更加巧妙。如果你还有更好的解法,欢迎在下面给我留言,我们一起讨论学习。

-- END

暂无评论~~