[数据结构与算法]快速排序（java实现）

快速排序也是选择排序的一种，是冒泡排序的改进版

基础思想：

1.首先，会有一个基准值和一个左指针以及右指针

2.指针跟基准值比较，小的放在基准值左边，大的放右边

3.这样就会分成左边一个值小的分区和右边值大的分区

4.使用递归重复1，2的操作，直到每一个小分区只有1个数据

动图如下：

?

?看代码：

  public static void quicksot(int nums[],int left,int right){
//        递归退出条件
        if (left>right){
            return;
        }
//        因为后面交换中会更改两个指针，所以先保存
        int l=left;
        int r=right;
//        定义基准值
        int pivot=nums[left];
        while (l!=r){
//            从右边找到小于基准的值
            while (nums[r]>=pivot && l<r ){
                r--;
            }
//            从左边找到大于基准的值
            while ( nums[l]<=pivot && l<r ){
                l++;
            }
//            注：在这里还需要判断一次l<r
//            交换
            if (l<r){
                int temp=nums[l];
                nums[l]=nums[r];
                nums[r]=temp;
            }
        }
//        当l=r的时候，交换此时的值和基准的值
        nums[left]=nums[l];
        nums[l]=pivot;

//        递归重复
        quicksot(nums,left,r-1);
        quicksot(nums,r+1,right);
    }

测试：

        int num[]=new int[800000];
        for (int i = 0; i <num.length; i++) {
            num[i] = (int) (Math.random() * 800000);
        }
//        测试
        Date d1 = new Date();
        SimpleDateFormat s = new SimpleDateFormat("YY-MM-DD HH:mm:ss:SSS");
        String s1 = s.format(d1);
        System.out.println("排序前的时间；" + s1);

        quicksot(num,0, num.length-1);
//        System.out.println(Arrays.toString(num));
        Date d2 = new Date();
        String s2 = s.format(d2);
        System.out.println("优化排序后时间；" + s2);

?