Python (Implement Quicksort with first element as pivot)以第一个元素为枢轴元素实现快速排序

如果您喜欢此文章请收藏、点赞、评论谢谢祝您快乐每一天。快速排序是一种分治算法。它选择一个元素作为枢轴并围绕该枢轴对给定数组进行分区。快速排序有很多不同的版本它们选择枢轴的方式各不相同。·始终选择第一个元素作为枢轴。·始终选择最后一个元素作为枢轴点。·随机选择一个元素作为枢轴。·选择中位数作为枢轴点。注意这里我们将通过选择第一个元素作为枢轴来实现快速排序。选择第一个元素作为枢轴进行快速排序快速排序的关键功能是分区。分区的目标是在数组已排序的情况下将枢轴元素放置在正确的位置并将较小的或相等的元素放在其左侧较大的元素放在其右侧并且所有这些都要在线性时间内完成。分区算法分区的方法有很多种以下伪代码采用了 CLRS 书中给出的方法。我们从最左边的元素开始并将较小或相等元素的索引记为i。在遍历过程中如果我们找到一个更小或相等的元素我们将当前元素与 arr[i] 交换。否则我们将忽略当前元素。递归快速排序函数的伪代码// low – Starting index, high – Ending indexquickSort(arr[], low, high) {if (low high) {// pi is partitioning index, arr[pi] is now at right placepi partition(arr, low, high);quickSort(arr, low, pi – 1); // Before piquickSort(arr, pi 1, high); // After pi}}partition() 函数的伪代码/* 此函数以数组首元素为基准元素将基准元素放置在排序数组中的正确位置并将所有小于或等于基准元素的元素放置在基准元素的左侧所有大于基准元素的元素放置在基准元素的右侧。*/partition(arr[], low, high) {// 第一个元素作为枢轴pivot arr[low]k highfor (i high; i low; i--) {if (arr[i] pivot){swap arr[i] and arr[k];k--;}}swap arr[k] and arr[low]return k;}分区的图示 partition() Consider: arr[] { 7, 6, 10, 5, 9, 2, 1, 15, 7 }第一次分区 low 0high 8pivot arr[low] 7初始化最右边元素的索引 k high 8。·从 i 高处到低处横移如果 arr[i] 大于 pivot交换 arr[i] 和 arr[k]。减去 k·最后交换 arr[low] 和 arr[k]。现在枢轴的正确位置是索引5。第二次分区 low 0high 4pivot arr[low] 2类似地初始化 k high 42 的正确位置变为索引 1。左侧部分只有一个元素右侧部分有 {6, 5, 7}。另一方面划分发生在段 [6, 8] 上即数组 {10, 9, 15}。这里 low 6high 8pivot 10k 8。10 的正确位置变为索引 7左右两部分都只有一个元素。第三划分 这里划分线段 {6, 5, 7}。低位 2高位 4枢轴 6k 4。如果应用相同的过程我们将得到 6 的正确位置即索引 3并且左右两部分都只有一个元素。这样一来整个数组就排序完成了。请查看下图了解递归树。请按照以下步骤实施该方法。使用递归函数例如快速排序来初始化该函数。调用分区函数对数组进行分区并在分区函数内部执行以下操作以第一个元素为枢轴并初始化迭代器k high。使用 for 循环从i high 到 low1 迭代如果 arr[i] 大于 pivot则交换arr[i]和arr[k]并将 k 减 1。迭代后将枢轴与arr[k]交换。返回 k-1 作为分割点。现在递归地对分区索引的左半部分和右半部分调用快速排序。上述方法的代码示例# This function takes first element as pivot, the function# places the pivot element(first element) on its sorted# position and all the element lesser than pivot will placed# left to it, and all the element greater than pivot placed# right to it.def partition(array, low, high):# First Element as pivotpivot array[low]# st points to the starting of arraystart low 1# end points to the ending of the arrayend highwhile True:# It indicates we have already moved all the elements to their correct side of the pivotwhile start end and array[end] pivot:end end - 1# Opposite processwhile start end and array[start] pivot:start start 1# Case in which we will exit the loopif start end:array[start], array[end] array[end], array[start]# The loop continueselse:# We exit out of the loopbreakarray[low], array[end] array[end], array[low]# As we got pivot element index is end# now pivot element is at its sorted position# return pivot element index (end)return end# The main function that implements QuickSort# arr[] -- Array to be sorted,# low -- Starting index,# high -- Ending indexdef quick_sort(array, start, end):# If low is lesser than highif start end:# idx is index of pivot element which is at its# sorted positionidx partition(array, start, end)# Separately sort elements before# partition and after partitionquick_sort(array, start, idx-1)quick_sort(array, idx1, end)# Function to print an arraydef print_arr(arr, n):for i in range(n):print(arr[i], end )print()# Driver Codearr1 [7, 6, 10, 5, 9, 2, 1, 15, 7]quick_sort(arr1, 0, len(arr1)-1)print_arr(arr1, len(arr1))# This code is contributed by Aditya Sharma输出已排序数组 1 2 5 6 7 7 9 10 15复杂性分析时间复杂度平均情况O(N * logN)其中 N 是数组的长度。最佳情况O(N * logN)最坏情况O(N 2 )辅助空间O(1)如果您喜欢此文章请收藏、点赞、评论谢谢祝您快乐每一天。