电子商务网站开发规划,游戏挂机云服务器,wordpress7.6,自学ui设计需要哪些资料什么是快速排序 快速排序#xff08;Quick Sort#xff09;是一种广泛使用的高效排序算法#xff0c;由计算机科学家托尼霍尔在1960年提出。它采用分治法#xff08;Divide and Conquer#xff09;策略#xff0c;将一个大数组分为两个小数组#xff0c;然后递归地对这两…什么是快速排序 快速排序Quick Sort是一种广泛使用的高效排序算法由计算机科学家托尼·霍尔在1960年提出。它采用分治法Divide and Conquer策略将一个大数组分为两个小数组然后递归地对这两个小数组进行排序。快速排序在平均情况下具有良好的性能时间复为 O(nlogn)O(nlogn)并且在实际应用中通常比其他 O(nlogn)O(nlogn) 的排序算法如归并排序和堆排序更快。
核心思想
快速排序的核心思想可以概括为以下几个步骤 选择基准Pivot从数组中选择一个元素作为基准。基准的选择可以影响排序的效率常见的选择方法包括选择第一个元素、最后一个元素或随机选择。分区Partition通过一趟扫描将数组分为两个部分 小于等于基准的元素大于基准的元素 这个过程称为分区。在分区完成后基准元素将处于其最终位置。递归排序对基准元素左侧和右侧的子数组进行递归调用快速排序。合并结果由于基准元素已经在正确的位置最终的排序结果将由所有递归调用的结果自动合并。 两个指针的定义和移动
在快速排序的实现中我们使用两个指针 i 和 j 来进行分区操作。
i 指针从左到右扫描数组找到第一个大于基准的元素。j 指针从右到左扫描数组找到第一个小于等于基准的元素。当 i 小于 j 时交换 i 和 j 指向的元素。
这个过程一直持续到 i 大于等于 j此时分区操作完成。
根据基准值交换 在分区过程中当 i 小于 j 时我们需要交换 i 和 j 指向的元素。这样可以确保左侧的元素都小于等于基准右侧的元素都大于基准。 让我们来看两道题目带你快速上手
示例一
题目描述 代码
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner new Scanner(System.in);int n scanner.nextInt();int arr[] new int[n];for (int i 0; i n; i) {arr[i] scanner.nextInt();}quickSort(arr, 0, n-1);for (int i 0; i n; i) {System.out.print(arr[i] );}}public static void quickSort(int[] arr,int l,int r) {if (l r) return;int x arr[lr 1];int i l - 1, j r 1;while (i j) {do i;while (arr[i] x) ;do --j;while (arr[j] x);if (i j) {int temp arr[i];arr[i] arr[j];arr[j] temp;}}quickSort(arr, l, j);quickSort(arr, j 1, r);}
}解释 Scanner scanner new Scanner(System.in);创建一个Scanner对象用于读取输入。int n scanner.nextInt();读取数组的长度。int arr[] new int[n];创建一个长度为n的整数数组。for (int i 0; i n; i) { arr[i] scanner.nextInt(); }循环读取数组的元素。quickSort(arr, 0, arr.length-1);调用quickSort方法对数组进行排序。for (int i 0; i n; i) { System.out.print(arr[i] ); }输出排序后的数组。if (l r) return;如果左边界l大于或等于右边界r则直接返回因为这意味着子数组只有一个元素或为空不需要排序。int x arr[l];选择数组的第一个元素作为基准元素。int i l - 1, j r 1;初始化两个指针i和j分别指向数组的左边界的前一个位置和右边界的后一个位置。while (i j) { ... }进入主循环直到i和j指针相遇。if (i j) { ... }如果i和j指针没有相遇交换arr[i]和arr[j]的值。do --j; while (arr[j] x);j指针从右向左移动直到找到一个小于或等于基准元素的元素。do i; while (arr[i] x);i指针从左向右移动直到找到一个大于或等于基准元素的元素。quickSort(arr, l, j);递归地对左子数组进行排序从l到j。quickSort(arr, j 1, r);递归地对右子数组进行排序从j 1到r。 示例二
题目描述 代码
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc new Scanner(System.in);int n,k;n sc.nextInt();k sc.nextInt();int[] arr new int[n];for (int i 0; i n; i) {arr[i] sc.nextInt();}quickSort(arr, 0, n - 1);System.out.println(arr[k - 1]);}public static void quickSort(int[] arr,int l,int r) {if (l r) return;int x arr[l];int i l - 1, j r 1;while (i j) {do i; while (arr[i] x) ;do --j; while (arr[j] x);if (i j) {int temp arr[i];arr[i] arr[j];arr[j] temp;}}quickSort(arr, l, j);quickSort(arr, j 1, r);}
}解释 导入Scanner类 用于读取输入数据。 定义类和main方法 Scanner sc new Scanner(System.in);创建Scanner对象从标准输入读取数据。int n, k;声明两个整数n和k。n sc.nextInt(); k sc.nextInt();读取数组长度n和目标索引k。int[] arr new int[n];创建长度为n的整数数组。for (int i 0; i n; i) { arr[i] sc.nextInt(); }从输入中读取n个整数存入数组arr。quickSort(arr, 0, n - 1);调用quickSort方法对数组进行排序。System.out.println(arr[k - 1]);输出排序后数组的第k个元素下标从0开始所以是k-1。 quickSort方法 使用快速排序算法对数组arr的从l到r部分进行排序。if (l r) return;如果左边界l大于或等于右边界r则返回子数组为空或只有一个元素。int x arr[l];选择子数组的第一个元素作为基准。int i l - 1, j r 1;初始化两个指针i和j。通过while循环将数组分割为两个部分所有小于基准值的元素放在左边所有大于基准值的元素放在右边并递归地对两边进行快速排序。 总结 快速排序是一种高效的排序算法它采用分治法的思想通过递归的方式将数组分为两个子数组然后对这两个子数组进行排序。通过选择基准、分区和递归调用快速排序能够在平均情况下以 O(nlogn)O(nlogn) 的时间复杂度完成排序。尽管在最坏情况下可能退化为 O(n2)O(n2)但通过合理的基准选择和随机化策略可以有效避免这一问题。快速排序的空间效率和实际性能使其成为排序任务中的热门选择。
