问题
排序 [30, 24, 5, 58, 18, 36, 12, 42, 39]
快速排序
快速排序采用分治策略,首先从数组中选择一个元素作为基准元素。以基准元素为标准,将问题分解为两个子序列,使小于等于基准元素的子序列在左侧,大于基准元素的子序列在右侧。然后将两个子序列分别进行快速排序,将排序好的两个子序列合并在一起,完成排序。
图解
快速排序算法的重点是选择基准元素,并将其移动到正确的位置。
- 初始化第一个元素为基准元素,pivot = 30,i = low,j = high
- 从数组的右边位置向左找,一直找到小于 pivot 的元素 12,与基准元素交换位置,i += 1
- 从数组的左边位置向右找,一直找到大于 pivot 的元素 58,与基准元素交换位置,j -= 1
- 从数组的右边位置向左找,一直找到小于 pivot 的元素 18,交换位置,i += 1。此时 i = j,第一轮排序结束,返回 i 的位置,mid = i
5. 完成第一轮排序之后,以 mid 为界,将原数据分为两个子序列,左侧子序列都比 pivot 小,右侧子序列都比 pivot 大,然后分别对两个子序列进行快速排序。
代码
# 获取基准元素的正确位置
def partition(nums, low, high):pivot = nums[low]i, j = low, highwhile i < j:while i < j and nums[j] >= pivot: # 从右向左找小于pivot的数,并交换位置j -= 1if i < j: nums[i], nums[j] = nums[j], nums[i]i += 1while i < j and nums[i] <= pivot: # 从左向右找大于pivot的数,并交换位置i += 1if i < j: nums[i], nums[j] = nums[j], nums[i]j -= 1return idef quick_sort(nums, low=0, high= len(nums)-1):if low < high:mid = partition(nums, low, high)quick_sort(nums, low, mid-1)quick_sort(nums, mid+1, high)return nums
时间复杂度
-
快速排序最好的时间复杂度是 O(nlogn)
最理想的情况下,每次划分将问题分解为两个规模都是 n/2 的子问题,递归求解
递归最终规模为 1,令 2x = n,x = logn,那么 -
快速排序最块的时间复杂度为 O(n2)
在最坏的情况下,每次划分将问题分解后,基准元素的左侧或右侧没有元素,基准元素的另一侧为 1 个规模为 n-1 的子问题,递归求解
算法优化
在上述算法中,每次交换都是在和基准元素交换,但实际没必要这样做。只需要从右往左找到小于等于基准元素的数,再从左往右找到大于基准元素的数,将这两个数交换,一直交替进行,直到 i 和 j 碰头,这时将其和基准元素交换,这样就完成了一次划分过程。
-
首先取数组第一个元素为基准元素 pivot = 30
-
从数组的右边往左找,一直找到小于 pivot 的元素 12,从数组的左边往右找,一直找到大于 pivot 的元素 58,然后将它们交换位置
-
继续从数组的右边往左找,找到小于 pivot 的元素 18,从左往右找大于 pivot 直到 i = j 时停止
-
将基准元素和 i 位置的元素交换,返回 i 的位置 mid = i,第一轮排序结束
代码
def partition(nums, low, high):pivot = nums[low]i, j = low, highwhile i < j:while i < j and nums[j] > pivot:j -= 1while i < j and nums[i] <= pivot:i += 1if i < j:nums[i], nums[j] = nums[j], nums[i]i += 1j -= 1if nums[i] > pivot:nums[i-1], nums[low] = nums[low], nums[i-1]return i-1nums[low], nums[i] = nums[i], nums[low]return i