网站模板 asp pc wap,自学学网页设计,建设招标网网站,新闻源发稿平台图解 快速排序是一种常见的排序算法#xff0c;它通过选取一个基准元素#xff0c;将待排序的数组划分为两个子数组#xff0c;一个子数组中的元素都小于基准元素#xff0c;另一个子数组中的元素都大于基准元素。然后递归地对子数组进行排序#xff0c;直到子数组的长度为… 图解 快速排序是一种常见的排序算法它通过选取一个基准元素将待排序的数组划分为两个子数组一个子数组中的元素都小于基准元素另一个子数组中的元素都大于基准元素。然后递归地对子数组进行排序直到子数组的长度为1或0。
快速排序的步骤如下
选择一个基准元素通常选择数组的第一个元素。将数组划分为两个子数组左边的子数组中的元素都小于基准元素右边的子数组中的元素都大于基准元素。可以使用双指针法实现。对左边的子数组递归地应用上述步骤对右边的子数组递归地应用上述步骤直到子数组的长度为1或0。
快速排序的时间复杂度为O(nlogn)空间复杂度为O(logn)其中n为待排序数组的长度。
快速排序是一种高效的排序算法以下是Java代码实现
public class QuickSort {public static void quickSort(int[] arr, int left, int right) {if (left right) {int pivotIndex partition(arr, left, right); // 获取基准值的位置quickSort(arr, left, pivotIndex - 1); // 递归排序左子数组quickSort(arr, pivotIndex 1, right); // 递归排序右子数组}}public static int partition(int[] arr, int left, int right) {int pivot arr[left]; // 将左边第一个元素选为基准值while (left right) {// 从右边开始找到第一个小于基准值的元素while (left right arr[right] pivot) {right--;}// 将小于基准值的元素放到左边arr[left] arr[right];// 从左边开始找到第一个大于基准值的元素while (left right arr[left] pivot) {left;}// 将大于基准值的元素放到右边arr[right] arr[left];}arr[left] pivot; // 将基准值放到中间return left; // 返回基准值的位置}public static void main(String[] args) {int[] arr {6, 1, 3, 9, 2, 7, 4, 8, 5};quickSort(arr, 0, arr.length - 1);for (int i 0; i arr.length; i) {System.out.print(arr[i] );}}
}快速排序的时间复杂度为O(nlogn)。
