排序算法

排序算法之快速排序Python

2020-09-11 16:31发布

站内文章 / Python
786 0 0

排序算法之快速排序

介绍一种新的排序算法，快速排序。前面一片文章中介绍了归并排序，简单的说，归并排序是物理意义上的分治法，就是把前面几个位置（下标）上的元素看成一个子序列，后面几个位置（下标）上的元素看成一个子序列。然后再将每个子序列继续分而治之，直到每个子序列只有一个元素，这样作为有序序列向上归并。
那么这样做的时间复杂度为O(nlogn)，但是空间上需要多备份一份，作为新的序列，空间复杂度为O(n)，如果需要排序的数据集特别大，这时候就要仔细考虑一下了。
可以思考一种逻辑意义上的分治法，或者说是内容上的分治法。不是按照下标来分割序列，而是根据数值来分治，每次根据一个数将序列分割成两个子序列和这个数，一个子序列的元素全部比这个数小，另一个子序列，全部比这个数大，并将原始序列的元素位置按照分割的序列进行排列。然后再分别两个子序列继续分割，直到每个子序列只有一个元素。这样，每个子序列都是由“特殊的数”连接起来，这个”特殊的数”的左边都比它小，右边都比它大，所以整体上肯定是排好序的。这就是快速排序。其实简单的说就是找中间元素（或者说选取的元素）的位置。

那么这个特殊的数怎么选取呢？理想状态下肯定是选取的数就是整个序列的中间值，这样每次都是均分的。但是实际上这是不可能的，因为事先并不知道中间值到底是多少，而查找中间值也是有开销的。所以一般情况下是随机选取序列中的一个数，我们选取的是第一个元素。

接下来叙述一下快速排序的具体原理过程。

  1. 对于给定的一个待排序列，选取首元素作为分割序列的数值（也就是最终的序列中，首元素所在的位置的左面一定都是比首元素小的，右面一定都是比首元素大的）。然后分别从第二个元素起向后遍历和最后一个元素位置起向前遍历。

  2. 向后遍历时，当遇到比首元素大的元素时，停止遍历。

  3. 向前遍历时，当遇到比首元素小的元素时，停止遍历。

  4. 注意在2和3步的过程中，一定要保证向后遍历的位置一定要在向前遍历的前面（或者说左面，即向后遍历的下标一定要小于向前遍历的下标，就像两个人过独木桥那样，一定要保证二者没有相遇）。没有相遇，说明二者还没有遍历完整个序列，也就是二者中间还有一定长度个数的元素，也就是还没有到达逻辑意义上的中点，也就是还没有到达首元素该有的位置。

  5. 2和3都停止遍历时，判断是否符合4的规定，如果符合，就把两个停止遍历时的下标处的元素进行交换。因为符合的话，说明还没有遍历完，没有遍历完就说明此时向后遍历的元素一定全部都应该在左面，而左面不应该出现比首元素大的数，向前遍历同理。所以二者需要交换。

  6. 如果不满足规定，说明二者已经交叉了，说明二者遍历经过的序列长度之和加起来已经超过了原始序列，所以必然是已经走过了中间元素的最终位置。那么此时到底哪个位置是呢？

  7. 其实是向前遍历的下标。因为假设此时向前遍历到了一个元素a，向后遍历到了一个元素b，此时已经交叉且都停止遍历了，那么就是a比首元素小，b比首元素大。此时因为交叉，所以b在a的右面（下标）。那么如果首元素最终的位置是b，也就是和b交换，那么b就在首元素的起始位置（最开始），而最开始的位置又是在最左面，所以最终的结果就是首元素的左边出现了比首元素大的数，这显然是不符合规定的，也是排序不正确的。所以如何和a交换，原始a的右面一定都是比首元素大的，因为如果不大，就在a之前就停止遍历了。而a的左面一定是比首元素小的，因为因为如果不小，则在b的前面就停止遍历了。所以最终如果交叉的话，那么就是向前遍历的下标是最终首元素的位置。

  8. 这样一轮遍历结束之后，实际上是找到了首元素的最终位置。那么接下来递归，分而治之即可。

这是教程给的代码，还好吧。其实可以不用定义这么多函数的。

# 快速排序
def quick_sort(alist):
    quick_sort_helper(alist, 0, len(alist)-1)

def quick_sort_helper(alist, first, last):
    if first < last:

        splitpoint = partition(alist, first, last)

        quick_sort_helper(alist, first, splitpoint-1)
        quick_sort_helper(alist, splitpoint + 1, last)


def partition(alist, first, last):
    pivotvalue = alist[first]

    leftmark = first + 1
    rightmark = last

    done = False

    while not done:

        while leftmark <= rightmark and alist[leftmark] <= pivotvalue:
            leftmark = leftmark + 1
        
        while alist[rightmark] >= pivotvalue and rightmark >= leftmark:
            rightmark = rightmark - 1
        
        if rightmark < leftmark:
            done = True
        else:
            temp = alist[leftmark]
            alist[leftmark] = alist[rightmark]
            alist[rightmark] = temp


    temp = alist[first]
    alist[first] = alist[rightmark]
    alist[rightmark] = temp

    return rightmark


# alist = [54,26,93,17,77,31,44,55,20]
# alist = [2, 1]
# alist = [1]
alist = [54,23,31,78]
quick_sort(alist)
print(alist)1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950

这是我写的代码，挺菜的。开始不太理解，对于长度为1和2的就特殊判别了一下。而且没有想到传递下标，把列表直接传进去了。

# 快速排序1
def quick_sort(alist):

    if len(alist) > 1:

        mid_value = alist[0]
        first = 1
        last = len(alist) - 1

        if first < last:
            while first < last:
                # 左边游标开始向右移动
                if alist[first] <= mid_value:
                    first += 1
                else:
                    # 左边找到了大于中间值的位置，即需要交换的位置。
                    # 右边下标开始向左移动
                    if alist[last] >= mid_value:
                        last -= 1
                    else:
                        # 右边找到了小于中间值的位置，即需要交换的位置。
                        # 交换
                        alist[first], alist[last] = alist[last], alist[first]

            alist[0], alist[first - 1] = alist[first - 1], alist[0]
            # print(alist[:first-1])
            left = quick_sort(alist[:first-1])
            right = quick_sort(alist[first:])

            # 快排结束后，将左半部分，中间值，和右半部分三个合并为一个，注意extend语法
            left.extend([alist[first-1]])
            left.extend(right)
            return left
        else:
            if alist[0] <= alist[1]:
                return alist
            else:
                return alist[::-1]
    else:
        return alist

lst = [1,26,93,17,77,31,44,55,20]
# lst = [2,1]
# lst = [3]
print(quick_sort(lst))123456789101112131415161718192021222324252627282930313233343536373839404142434445

稍微改进了一下下，不用判别长度为2的了。

# 快速排序2
def quick_sort(alist):

    if len(alist) > 1:

        mid_value = alist[0]
        first = 1
        last = len(alist) - 1

        if first <= last:
            while first <= last:
                # 左边游标开始向右移动
                if alist[first] <= mid_value:
                    first += 1
                else:
                    # 左边找到了大于中间值的位置，即需要交换的位置。
                    # 右边下标开始向左移动
                    if alist[last] >= mid_value:
                        last -= 1
                    else:
                        # 右边找到了小于中间值的位置，即需要交换的位置。
                        # 交换
                        alist[first], alist[last] = alist[last], alist[first]

            alist[0], alist[first - 1] = alist[first - 1], alist[0]
            # print(alist[:first-1])
            left = quick_sort(alist[:first-1])
            right = quick_sort(alist[first:])

            # 快排结束后，将左半部分，中间值，和右半部分三个合并为一个，注意extend语法
            left.extend([alist[first-1]])
            left.extend(right)
            return left
    else:
        return alist

# lst = [1,26,93,17,77,31,44,55,20]
lst = [1,2]
# lst = [3]
print(quick_sort(lst))12345678910111213141516171819202122232425262728293031323334353637383940

大改了一下，传递下标，那这样参数就多了一点。

# 快速排序3
def quick_sort(alist, first, last):

    if first < last:
        # 中间值
        mid_value = alist[first]

        # 左右游标
        left = first + 1
        right = last
            
        while left <= right:
            # print(left, right)

            # 左右游标分别移动
            while left <= right and alist[left] <= mid_value:
                left += 1

            while right >= left and alist[right] >= mid_value:
                # print(right)
                right -= 1

            # 此时要么是左右游标相对左右位置发生改变（即左游标在右游标的右边），要么就是出现了要交换的元素
            if left <= right:
                alist[left], alist[right] = alist[right], alist[left]
            else:
                break
        
        alist[first], alist[right] = alist[right], alist[first]
        # print(alist)
        quick_sort(alist, first, right-1)
        quick_sort(alist, right+1, last)


# alist = [54,26,93,17,77,31,44,55,20]
# alist = [2, 1]
# alist = [1]
alist = [54,23,31,78]
quick_sort(alist, 0, len(alist)-1)
print(alist)12345678910111213141516171819202122232425262728293031323334353637383940

时间复杂度的话，这个就是O(nlogn)，和归并排序类似，分为分割和排序两部分，分割的话，划分到长度为1的时候就截止了，所以还是O(logn)（不过取决于初值中间值的选取，这个还不是很清楚），排序的话，就是前后同时遍历，遍历完就完事了，那就是O(n)了。



作者：qq_42907161

链接：https://blog.csdn.net/qq_42907161/article/details/108392357

来源：CSDN
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。