八大排序算法的python实现（四）快速排序

时间：2023-12-20 16:06:38

代码：

#coding:utf-8

#author:徐卜灵

#交换排序.快速排序

# 虽然快速排序称为分治法，但分治法这三个字显然无法很好的概括快速排序的全部步骤。因此我的对快速排序作了进一步的说明：挖坑填数+分治法：

# import sys

# sys.setrecursionlimit(150000)

L = [6, 3, 2, 32, 5, 4]

def Fast_sort(L, left,right):

    if left >= right:

        return L

    key = L[left]

    low = left

    high = right

    while left < right:

        # if L[right] > key:

        #     right-=1

        # else:

        #     L[left] = L[right]

        # if L[left] <= key:

        #     left += 1

        # else:

        #     L[right] = L[left]

        # L[left] = key

        while left < right and L[right] >= key:

            right -= 1

        L[left] = L[right]

        while left < right and L[left] <= key:

            left += 1

        L[right] = L[left]

    L[left] = key

    Fast_sort(L, low, left - 1)

    Fast_sort(L,left + 1,high)

    return L

print Fast_sort(L,0,5)

# 1.高质量代码

# def quick_sort(lists, left, right):

#     # 快速排序

#     if left >= right:

#         return lists

#     key = lists[left]

#     low = left

#     high = right

#     while left < right:

#         while left < right and lists[right] >= key:

#             right -= 1

#         lists[left] = lists[right]

#         while left < right and lists[left] <= key:

#             left += 1

#         lists[right] = lists[left]

#     lists[left] = key

#     quick_sort(lists, low, left - 1)

#     quick_sort(lists, left + 1, high)

#     return lists

# print quick_sort(L,0,5)

#2.高质量代码

# # 设置最低位和最高位

# def quickSort(nums, low, high):

#     # 设置一个比较基准key

#     key = nums[low]

#     while low<high:

#         # 如果最高位的数 大于等于 key则向前走

#         while low<high and nums[high] >= key:

#             high -= 1

#         # 如果最低位的数 小于等于 key则向后走

#         while low<high and nums[low] <= key:

#             low += 1

#         # 交换值

#         nums[low], nums[high] = nums[high], nums[low]

#

#     #最后low=high, 此时交换key和high位上的值, 使小于key的值在key左边, 大的在key右边

#     nums[nums.index(key)], nums[low] = nums[low], nums[nums.index(key)]

#     # 返回最低位的位置

#     return low

#

#

# # 进行重复操作

# def interval(nums, low, high):

#     if low<high:

#         # 进行排序并得到最低位位置以循环操作

#         key_index = quickSort(nums, low, high)

#         interval(nums, low, key_index)

#         interval(nums, key_index+1, high)

#

#

# nums = [64,3,9,2,4,7,0,12,45,]

# interval(nums, 0, len(nums)-1)

# print nums

#

算法理解上没有什么问题，问题在算法实现上。特别注意的是几个索引，low 和 high 做一下缓存。

另外，在用递归的时候，一定注意迭代停止的判断条件。我在写代码的时候就一直忘了加判断条件，结果总是提示错误。一个简单的错误就搞这么久。

时间复杂度：O（nlogn）

空间复杂读：O（nlogn）

非稳定排序算法。

大多数情况下的最优选的排序算法，时间复杂度低嘛。

相关文章