赞
踩
什么是快速排序?
首先确立pivot,比如下图位于末尾
然后i遍历3到6
在3的时候,j指向i前面一位
如果3<=5(pivot),那么j++,同时将i与j指向的交换,第一次交换是原地不动
一直到遇见9,此时j不动,然后i指向2,j++,j指向9,此时2与9交换,也就是将小的与大的交换。快速排序所要达到的目的是,每轮大循环,确定pivot的位置,以及保证pivot左边都是小于等于他,右边都是大于他
可以看到这里i走到了头,出了循环,此时将pivot与j+1指向的交换,确定了pivot的位置
然后5的左右两边分别再次进行快排
- import random
- '''1 首先start不能小于last,退出边界
- 2 选择pivot放在last位置上
- 3 遍历start到last-1位置上的数a
- 如果a<=pivot,则与j指向的值原地交换
- 如果a>pivot,则j不变,等到下次a>pivot,则a与这个j指向的大值交换
- 4 循环结束,j+1指向的与pivot交换,将pivot放在合适的位置上,
- 左边都是小于等于的,右边都是大于他的
- 5 继续执行快排,分别执行j左边和右边部分 '''
-
- def quick_sort(nums, start, last):
- if start >= last:
- return
- first = start
-
- '''# 1 pivot随机选择
- pivot_index = random.randint(start, last)
- nums[pivot_index], nums[last] = nums[last], nums[pivot_index]
- pivot = nums[last]
- # 2 选第一个
- nums[first], nums[last] = nums[last], nums[first]
- pivot = nums[first]'''
-
- #3 选最后一个
- pivot = nums[last]
-
- j = start - 1
- for i in range(start, last):
- if nums[i] <= pivot:
- j += 1
- nums[j], nums[i] = nums[i], nums[j]
- nums[j + 1], nums[last] = nums[last], nums[j + 1]
- print(nums)
- print('j:', j, 'pivot:', pivot)
- quick_sort(nums, first, j)
- quick_sort(nums, j + 2, last)
-
- if __name__ == '__main__':
- nums = arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
- quick_sort(nums, 0, len(nums) - 1)
- print("Sorted array is:", nums)
O(NlogN)
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。