java 排序算法之快速排序(挖坑法)

2024-02-13 05:45| 来源: 网络整理| 查看: 265

快速排序是（挖坑法）是挖坑填数 + 分治来实现。

快速排序的基本思想：

1．先从数列中取出一个数作为基准数。

2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。

3．再对左右区间重复第二步，直到各区间只有一个数。

直接上代码：

package com.wang.sort; import java.util.Arrays; /** * 快速排序之填坑法(挖坑法) * 从数列中挑出一个元素，称为 “基准”（pivot） * 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面 * 相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区 * （partition）操作 * 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。 * @author wang * @Date 2018年4月16日 * */ public class QuickSort { public static void main(String[] args) { int[] arrays = {12,21,3,5,2,18,7,4,11,9,12}; System.out.println("快速排序之挖坑排序前的数组:" +Arrays.toString(arrays)); pothlingSort(arrays, 0 , arrays.length - 1); System.out.println("快速排序之挖坑排序后的数组:" +Arrays.toString(arrays)); } /** * 挖坑法 * @param arrays * @param low * @param high */ public static void pothlingSort(int[] arrays , int low , int high){ if(low < high){ //求每次分治的分割线 int divideIndex = getDivideIndex(arrays,low,high); //再递归分别对分割的俩个子数组进行递归排序 pothlingSort(arrays,low,divideIndex -1); pothlingSort(arrays,divideIndex + 1, high); } } private static int getDivideIndex(int[] arrays, int low, int high) { // 将数组最左端arrays[0]作为默认的基准值,将最左端的值放至基准值的坑内。 // 此时arrays[0]没有值了，需要从最右端找到一个比基准值小的数填至[0]这个坑。 // 再从左到右找到一个比基准值大的数填到刚才的坑。循环进行直到low=high // 将基准值填至刚才的low位置。再进行分治 int baseValue = arrays[low]; arrays[low] = 0 ; while (low < high){ while(low < high && arrays[high] >= baseValue){ high--; } arrays[low] = arrays[high] ; arrays[high] = 0 ; while(low < high && arrays[low]

【本文地址】

公司简介

联系我们