快速排序,是每次找一个数字(一般是列表的第一个元素)作为中间值,将小于这个中间值的元素都放在左边,比这个中间值大的放在右边。然后,对左边和右边的子序列进行递归操作,即可实现排序。只有一个元素的序列是有序的。
首先,对于第一个元素进行操作。调整后的列表中,该元素左边的元素都比它小,右边的元素都比它大:
alist = [3, 8, 5, 7, 6, 9, 2, 1, 4, 6, 3, 3, 2] # 使用重复值更严谨def quick_sort(alist): left = 0 # 第一个元素下标 right = len(alist) - 1 # 最后一个元素下标 # 循环过后的序列中,要确保小于等于基准值的数字在基准值右侧,大于基准值的数在其左侧 while left < right: # 先偏移right,此时基准值3位于left对应的位置 while left < right: if alist[right] > alist[left]: right -= 1 # 如果right对应的值比基准值大,不需要操作,比较下一个数字 else: # 如果right对应的值比基准值小(或等于),则将其与基准值交换位置 alist[right], alist[left] = alist[left], alist[right] left += 1 # 因为原来基准值的位置left的元素已经检查过了,不需要重复检查,所以直接去下一个元素即可 break while left < right: # 先偏移left,此时基准值3位于right对应的位置 if alist[right] >= alist[left]: left +=1 # 如果left对应的值比基准值小或者相等,不需要操作,比较下一个数字 else: # 如果left对应的值比基准值大,将其于基准值交换位置 alist[right], alist[left] = alist[left], alist[right] right -= 1 # 因为原来基准值的位置right的元素已经检查过了,不需要重复检查,所以直接去下一个元素即可 break print(left, right) # 5 5 return alistprint(quick_sort(alist)) # [2, 3, 3, 1, 2, 3, 9, 6, 4, 6, 7, 5, 8]
经一次操作后,左右两侧的索引都到了 5 的位置。接下来,我们对左右两部分的列表进行递归,即可实现快速排序:
alist = [3, 8, 5, 7, 6, 9, 2, 1, 4, 6, 3, 3, 2]def quick_sort(alist, start, end): left = start right = end while left < right: while left < right: if alist[left] < alist[right]: right -= 1 else: alist[left], alist[right] = alist[right], alist[left] left += 1 break while left < right: if alist[left] <= alist[right]: left += 1 else: alist[left], alist[right] = alist[right], alist[left] right -= 1 break # 上述为核心操作,需要将核心操作递归左右到左右子序列中 if start < left - 1: # 结束递归条件:当左侧只剩一个元素或没有元素时 quick_sort(alist, start, left - 1) # 将sort作用到左侧序列中 if right + 1 < end: # 结束递归条件:当右侧只剩一个元素或没有元素时 quick_sort(alist, right + 1, end) # 将sort作用到右侧序列中 return alistquick_sort(alist, 0, len(alist) - 1) # [1, 2, 2, 3, 3, 3, 4, 5, 6, 6, 7, 8, 9]
归并排序采用分而治之的原理:
如何合并?
下图中的倒数第三行表示为第一次合并后的数据。其中一组数据为 4 8 , 5 7。该两组数据合并方式为:每一小组数据中指定一个指针,指针指向每小组数据的第一个元素,通过指针的偏移指定数据进行有序排列。排列情况如下:
归并排序使用 Python 代码实现:
alist = [3, 8, 5, 7, 6, 9, 2, 1, 4, 6, 3, 3, 2]def merge_sort(alist): n = len(alist) # 递归结束条件 if n <= 1: return alist # 将序列分成左右两部分,递归排序 mid = n // 2 left = merge_sort(alist[:mid]) right = merge_sort(alist[mid:]) # 将指针归零 left_pointer = right_pointer = 0 result = [] # 用于存放排序好的结果 # 比较指针位置的数字,较小的放到结果中,并依次移动指针 while left_pointer < len(left) and right_pointer < len(right): if left[left_pointer] < right[right_pointer]: result.append(left[left_pointer]) left_pointer += 1 else: result.append(right[right_pointer]) right_pointer += 1 # 将左右两边剩余的元素直接放到结果中 result.extend(left[left_pointer:]) result.extend(right[right_pointer:]) # 将结果返回 return resultprint(merge_sort(alist)) # [1, 2, 2, 3, 3, 3, 4, 5, 6, 6, 7, 8, 9]
联系客服