详解Java常用排序算法-快速排序_快速排序算法资源-CSDN文库

需积分: 1 144 浏览量 2023-08-26 15:57:33 上传评论收藏 15KB DOCX 举报

资源推荐

资源详情

资源评论

快速排序（Quick Sort）

快速排序是一种分治思想的排序算法，它的基本思想是通过一趟排序将待排记录分隔成独立

的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，然后再分别对这两部分

记录继续进行排序，以达到整个序列有序的目的。

import org.junit.jupiter.api.Assertions;

import java.util.Arrays;

public class Quick {

// 接收一个数组 arr，一个低索引 low ，和一个高索引 high 作为参数

public static void quickSort(int[] arr, int low, int high) {

// 检查 low 是否小于 high。如果不是，则意味着数组只有一个元素或为空，因此

不需要排序

if (low < high) {

int pivot = partition(arr, low, high);

quickSort(arr, low, pivot - 1);

quickSort(arr, pivot + 1, high);

}

}

private static int partition(int[] arr, int low, int high) {

// 将最后一个元素作为枢轴元素（ arr[high] ）

int pivot = arr[high];

// 将 i 初始化为 low - 1，用于跟踪较小元素的索引

int i = low - 1;

for (int j = low; j < high; j++) {

if (arr[j] < pivot) {

// 如果当前元素 arr[j] 小于枢轴元素，则增加 i 并交换 arr[i] 和 arr[j]

// 较小元素索引+1

i++;

// 将当前元素 arr[j] 放在较小元素索引位置

swap(arr, i, j);

}

// 其他情况，则较小元素索引没有增加，说明当前元素应该放在右边

}

// 将枢轴元素（ arr[high] ）与索引 i + 1 处的元素交换。

// 确保枢轴元素左边是较小元素，右边是较大元素

swap(arr, i + 1, high);

// 将 i + 1 作为枢轴索引返回

return i + 1;

}

private static void swap(int[] arr, int i, int j) {

int temp = arr[i];

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余1页未读，立即下载

内容反馈

烈日下的奔跑

粉丝: 1070
资源: 232

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip