排序算法-快速排序-蒲公英云

排序算法-快速排序

蔚落 2022-06-01 06:17 375阅读 0赞

快速排序是最高效、不占用空间的一种排序算法

快排的精髓是在于找到中间基数。
比中间基数小的放在左边，比中间基数大的放在右边
然后左右各自进行快排。

参考博客：http://developer.51cto.com/art/201403/430986.htm

这里写图片描述

首先以数组第一个数字作为基数
数组从最左是低位，最右是高位

刚开始低位就是基数
比较基数和高位如果基数比高位小高位减减
直到基数大于高位交换位置
然后比较低位和基数
低位小于基数低位加加
直到低位大于基数交换位置
又开始比较高位 ……

直到低位下标和高位下标重合（低位下标不小于高位）

然后将基数赋值给低位（或高位）

第一次比较结束比基数小的在左边比基数大的在右边

将基数下标返回迭代继续对左右两边进行排序

实现代码：

package quicksort;
import java.util.Arrays;
public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {
   34,45,12,89,25,76,44,90,1,62,59};
        quickSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
    public static int getMiddle(int[] arr,int low,int high){
        int tmp =arr[low];
        while(low<high){
            while (low<high && arr[high]>tmp){
                high--;
            }
            arr[low]=arr[high];
            while (low<high && arr[low]<tmp){
                low++;
            }
            arr[high]=arr[low];
        }
            arr[low] =tmp;
        return low;
    }
    public static void quickSort(int[] arr,int low,int high){
        if(low<high){
            int i = getMiddle(arr,low,high);  //将数组一分为二
            quickSort(arr,low,i-1);
            quickSort(arr,i+1,high);
        }
    }
}