快排

快速排序

前面讲过冒泡排序、插入排序等，今天具体讲解一下排序效率最高的快排

快排基本思想

**********************  快排基本思想  **********************
1.找基准位temp
2.int i=start,j=end;
3.若temp<a[j];j--;若temp>a[j];a[i]=a[j];i++
4.循环上一步骤，直到 i=j ,则 a[i]=temp
5.出外层循环时递归调用(自己调自己)

代码演示快排

这里我们先利用随机数生成一个数组，然后通过快排将其按照从小到大的顺序排列

// 快排
public class QuickSort {
    public static void quick(int[]a,int start,int end){
        //把首位订位标准为tmp
        int i=start,j=end;
        if (i>=j)return;
        int tmp=a[start];
        //i=start;j=end;
        while (i<j){//循环条件i<j
            //循环内要有两个循环来重复i++和j--的过程
            while (a[j]>=tmp && i<j)j--;
            a[i]=a[j];
            while (a[i]<=tmp && i<j)i++;
            a[j]=a[i];
        }
        //出外层循环时把标准为插入在i出
        a[i]=tmp;
        //递归调用（自己调自己）
        quick(a,start,i-1);
        quick(a,i+1,end);
    }

    public static int[] randomArray(int length){
        int[]a=new int[length];
        for (int i = 0; i < a.length; i++) {
            //随机数生成
            Random r=new Random();
            a[i]=r.nextInt(10);
        }
        return a;
    }

    public static void main(String[] args) {
        int[]a=randomArray(10);
        long now=System.currentTimeMillis();
        System.out.println("排序前数组："+Arrays.toString(a));
        quick(a,0,a.length-1);
        System.out.println("排序后数组："+Arrays.toString(a));
        long used=System.currentTimeMillis()-now;
        System.out.println("排序所用时间："+used+"毫秒");
    }
}

首先利用随机数生成一个数组，然后快排结果如下：

这里演示数据较少，看不出快排的优势。下图是将数组长度调到1000000万后的运行结构，由于数量太多，故未打印数组

大家可以试试插入排序、冒泡排序等排列长度为1000000万的数组需要的时间，这样就可以很明显的看出快排的优势了
快速排序可以更快的将数组排序，因此应用也更为广泛，希望可以帮助大家掌握快排

本文地址：https://blog.csdn.net/qq_42578036/article/details/107676307