JAVA快速排序代码 java快速排序算法

快速排序三个步骤：

选择基准值：在待排序列中，按照某种方式挑出一个元素，作为基准值。
分割操作：以该基准值在序列中的实际位置，把序列分成两个子序列，一边是比它大的值，另外一边是比它小的值。
递归：对两个子序列进行快排，直到序列为空或者只有一个元素。

代码实现

package sort; import java.util.Arrays; public class QuickSort { public static void quickSort(int[] arr, int left, int right){ // 递归的出口：只剩下一个元素的时候 if (left >= right){ return; } int pivot = arr[left]; int i = left, j = right; while (i < j) { // 这里如果pivot 选在左侧，就要先从右侧开始遍历，反之则先从左侧开始 // 小于等于来处理重复的元素 while (arr[j] >= pivot && i < j){ j--; } // 找到比基准小的数换到左侧 arr[i] = arr[j]; while (arr[i] <= pivot && i < j) { i++; } // 找到比基准大的数换到右侧去 arr[j] = arr[i]; } // 最后将基准放到中间位置 arr[i] = pivot; //递归快排左侧数列 quickSort(arr, left, i - 1); // 递归遍历右侧数列 quickSort(arr, i + 1, right); }public static void main(String[] args) { int[] arr = {7,3,2,1,6,4,5,6}; int left = 0; int right = arr.length - 1; quickSort(arr, left, right); System.out.println(Arrays.toString(arr)); } }

时间复杂度对n个元素进行快速排序的过程构成一棵递归树，在这样的递归树中，每一层最多对n个元素进行划分，所花的时间为O(n)。当初始排序数据随机分布，使每次分成的两个子区间中的元素个数大致相等时，递归树高度为log2n，快速排序呈现最好情况，即最好情况下的时间复杂度为O(nlog2n)。快速排序算法的平均时间复杂度也是O(nlog2n)。所以快速排序是一种高效的算法。
【JAVA快速排序代码】最坏情况为，每一轮分不成两组，每一轮都只能把基准值索引放到第一个或者最后一个，因此一共需要n轮。
因此，最坏时间复杂度为O(n^2)。