赞
踩
快速排序(Quick Sort)是一种高效的排序算法,它采用分治的思想。以下是使用Java编写的快速排序算法的实现:
- public class QuickSort {
-
- // 快速排序的主要方法
- public static void quickSort(int[] arr, int left, int right) {
- if (left < right) {
- // pi 是分区点,arr[pi] 已经就位
- int pi = partition(arr, left, right);
-
- // 递归地对分区点左边和右边的子数组进行排序
- quickSort(arr, left, pi - 1);
- quickSort(arr, pi + 1, right);
- }
- }
-
- // 分区操作
- // 返回分区点 pi,使得 arr[l..pi] <= arr[pi+1..r]
- private static int partition(int[] arr, int left, int right) {
- // 选择最右侧的元素作为基准值(pivot)
- int pivot = arr[right];
-
- // i 是小于 pivot 的元素的索引
- int i = left - 1;
-
- for (int j = left; j < right; j++) {
- // 如果当前元素小于或等于 pivot
- if (arr[j] <= pivot) {
- // 增加 i
- i++;
- // 交换 arr[i] 和 arr[j]
- swap(arr, i, j);
- }
- }
-
- // 将基准值移到正确的位置
- swap(arr, i + 1, right);
- return i + 1;
- }
-
- // 交换数组中两个元素的位置
- private static void swap(int[] arr, int i, int j) {
- int temp = arr[i];
- arr[i] = arr[j];
- arr[j] = temp;
- }
-
- // 测试代码
- public static void main(String[] args) {
- int[] arr = {10, 7, 8, 9, 1, 5};
- quickSort(arr, 0, arr.length - 1);
- for (int num : arr) {
- System.out.print(num + " ");
- }
- }
- }
这个代码首先定义了一个quickSort
方法,它是快速排序的主要方法。该方法接受一个数组和左、右索引作为参数,并使用递归对数组进行排序。partition
方法是快速排序的核心,它选择一个基准值(在这个例子中是最右侧的元素),然后重新排列数组,使得所有小于基准值的元素都出现在基准值的左侧,所有大于基准值的元素都出现在基准值的右侧。最后,swap
方法用于交换数组中的两个元素。在main
方法中,我们创建了一个测试数组并调用quickSort
方法进行排序。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。