快速排序算法
1.选择第一个元素（a）作为一个坑，把它保存下来，然后先从右边开始找一个比它大的元素，将它们的位置互换
2.从右边找一个比a小的元素，然后交换它们的位置
3.依次类推，最后得到a为数组的中间元素
4.最后对a两边进行递归遍历得出数组

package datastructure.sort;

/*
    @CreateTime 2021/9/14 20:30
    @CreateBy cfk
   
*/

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

public class QuickSorting {

    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));

        // 测试80000条数据 冒泡排序所需要的时间 1s
        // int[] arr = new int[80000];
        // for (int i = 0; i < 80000; i++) {
        //     arr[i] = (int) (Math.random()*8000000);
        // }
        //
        // SimpleDateFormat sdf = new SimpleDateFormat("yy-MM-dd HH:mm:ss");
        // String s1 = sdf.format(new Date());
        // System.out.println(s1);
        //
        //
        // quickSort(arr,0,arr.length-1);
        //
        //
        // String s2 = sdf.format(new Date());
        // System.out.println(s2);


    }


    public static void quickSort(int[] arr, int left, int right){

        //判断左节点要小于右节点 否则递归的时候 会出现数组越界
        if (left < right) {

            int l = left;
            int r = right;
            //定义一个临时变量存储第一个元素
            int x = arr[l];

            //当左节点小于右节点时运行程序
            while (l < r) {
                //从右边开始寻找比第一个元素小的元素
                while (l < r && x <= arr[r]){
                    r--;
                }
                //找到后 把第一个元素赋值为找的元素 并且把指针右移
                if (l < r) {
                    arr[l] = arr[r];
                    l++;
                }
                //从左边开始寻找比第一个元素大的元素
                while (l < r && x > arr[l]){
                    l++;
                }
                //找到后 把倒数第一个元素赋值为找的元素 并且把指针左移
                if (l < r) {
                    arr[r] = arr[l];
                    r--;
                }
            }
            //最后把最后一个位置填上第一个元素 此时此元素的左边全部小于它 右边全部大于它
            //但是左右两边元素并不保证有序
            arr[l] = x;
            //递归遍历左边所有的元素
            quickSort(arr,left,l-1);
            //递归遍历右边所有的元素
            quickSort(arr,l+1, right);
        }

    }
}