如果您喜欢此文章请收藏、点赞、评论谢谢祝您快乐每一天。快速排序是一种分治算法。它选择一个元素作为枢轴并围绕该枢轴对给定数组进行分区。快速排序有很多不同的版本它们选择枢轴的方式各不相同。·始终选择第一个元素作为枢轴。·始终选择最后一个元素作为枢轴点。·随机选择一个元素作为枢轴。·选择中位数作为枢轴点。注意这里我们将通过选择第一个元素作为枢轴来实现快速排序。选择第一个元素作为枢轴进行快速排序快速排序的关键功能是分区。分区的目标是在数组已排序的情况下将枢轴元素放置在正确的位置并将较小的或相等的元素放在其左侧较大的元素放在其右侧并且所有这些都要在线性时间内完成。分区算法分区的方法有很多种以下伪代码采用了 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 作为分割点。现在递归地对分区索引的左半部分和右半部分调用快速排序。上述方法的代码示例import java.util.Arrays;class QuickSort {/* This function takes first element as pivot, thefunction places the pivot element(first element) on itssorted position and all the element lesser than pivotwill placed left to it, and all the element greater thanpivot placed right to it.*/int partition(int arr[], int low, int high){// First element as pivotint pivot arr[low];int st low; // st points to the starting of arrayint end high; // end points to the ending of the arrayint k high;for (int i high; i low; i--) {if (arr[i] pivot)swap(arr, i, k--);}swap(arr, low, k);// As we got pivot element index is end// now pivot element is at its sorted position// return pivot element index (end)return k;}// Function to swap two elementspublic static void swap(int[] arr, int i, int j){int temp arr[i];arr[i] arr[j];arr[j] temp;}/* The main function that implements QuickSortarr[] -- Array to be sorted,low -- Starting index,high -- Ending index */void quickSort(int arr[], int low, int high){// If low is lesser than highif (low high) {// idx is index of pivot element which is at its// sorted positionint idx partition(arr, low, high);// Separately sort elements before// partition and after partitionquickSort(arr, low, idx - 1);quickSort(arr, idx 1, high);}}/* Function to print an array */void printArray(int arr[], int size){int i;for (i 0; i size; i)System.out.print(arr[i] );System.out.println();}// Driver Codepublic static void main(String args[]){int arr[] { 7, 6, 10, 5, 9, 2, 1, 15, 7 };int n arr.length;QuickSort ob new QuickSort();ob.quickSort(arr, 0, n - 1);System.out.println(Sorted array);ob.printArray(arr, n);}}输出已排序数组 1 2 5 6 7 7 9 10 15复杂性分析时间复杂度平均情况O(N * logN)其中 N 是数组的长度。最佳情况O(N * logN)最坏情况O(N 2 )辅助空间O(1)如果您喜欢此文章请收藏、点赞、评论谢谢祝您快乐每一天。