您现在的位置是：首页 > 后台技术 > 数据结构与算法数据结构与算法

快速排序法(图文)

第十三双眼睛2022-06-21【数据结构与算法】人已围观

简介快速排序法

快速排序法的思路：

package com.xingchen.day006;
import java.util.Arrays;
public class QuickSort {
public static void main(String[] args) {
int[] arr = {-9,78,0,23,-567,70};
quickSort(arr,0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
public static void quickSort(int[] arr,int left,int right) {
int l = left; //左边得下标
int r = right; // 右边得下标
int pivot = arr[(left + right)/2];
int temp = 0;// 临时变量，交换时使用
// 让比中间值大的数字放到右边，小的值放到左边
while (l < r) {
// 从左边找比中间值大的数
while (arr[l] < pivot) {
l += 1;
}
// 从右边找比中间值小的数字
while (arr[r] > pivot) {
r -= 1;
}
// 如果l >= r说明中间值左边的数字全部小于中间值，右边的值全部大于等于中间值
if (l >= r) {
break;
}
// 交换
temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
// 如果交换完后发现 arr[l] 等于povit 前移
if (arr[l] == pivot) {
r --;
}
if (arr[r] == pivot) {
l ++;
}
}
// 如果l = r,需要让l ++ r -- 否则会栈溢出
if (l ==r) {
l += 1;
r -= 1;
}
// 向左递归
if (left < r) {
quickSort(arr, left, r);
}
// 向右递归
if (right > l) {
quickSort(arr, l, right);
}
}
}

Tags：

很赞哦！ ()

上一篇：希尔排序法(图文)

下一篇：归并排序法(图文)