java数据结构与算法基础-----排序------快速排序

1. 快速排序是冒泡排序的改进版。依然采用分治思想，先通过一趟排序将数据分割成两部分，其中一部分的所有数据要比另一部分的所有数据要小，然后再按此方法，对这两部分数据分别进行快速排序，整个过程可以用递归实现。
2. 就是拿到一组数据，先找一个数，作为中间数（你可以直接拿序列中间的数，或者拿最后一个数，或者第一个数），然后依据此数，先排成两组，不用有序，就是比中间数大的，分为一组，比中间数小的，分为一组，中间数最后归哪组，随意，不归任何一组也可以。然后分别对这两组再进行快速排序（就像冒泡一样，每次把中间数冒出去）
   
3. 实现思路与运行效果

1. 首先，我们选择中间数（基准数），我们这里指定序列的第一个数是基准数，将基准数保存。然后创建两个下标，分别位于序列的最左面和最右面，依次从右边找大于中间数的值，将其放在左边，左边找小于中间数的值，放在右边，最后，左边下标最后的位置，就是中间，将中间数放进去即可
   

4. 代码第一版

import java.util.Arrays;
import java.util.Date;

public class Test {
    public static void main(String[] args) {
        int arr[]= {8,9,1,7,2,3,5,4,6,0};
        int arr1[]={-9,78,0,23,-567,70, -1,900, 4561};

        System.out.println("原序列为:"+ Arrays.toString(arr));

        quickSort(arr,0,arr.length-1);
        print(arr);

        System.out.println("原序列为:"+ Arrays.toString(arr1));

        quickSort(arr1,0,arr1.length-1);
        print(arr1);

        System.out.println("=================================80000组数据测试======================");
        int array[] = new int[80000];
        for (int i = 0 ;i<80000;i++){//生成80000个[0,8000000)的随机数
            array[i] = (int) (Math.random()*800000);
        }
        long start = new Date().getTime();
        quickSort(array,0,array.length-1);
        long end = new Date().getTime();
        System.out.println("消耗时间"+(end-start));

    }

    /**
     * 快速排序
     */
    public static void quickSort(int[] a, int left, int right) {
         if (left < right) {//如果l>r表示已经排完，可以出递归了
                 int l = left;//左下标
                 int r = right;//右下标
                 int temp = a[l];//保存一个指标变量
                 while (l < r) {//如果l>=r时，退出循环，表示排完

                     while(l < r && a[r] > temp)//从右向左遍历找小于temp的数，但是不能越过l
                         r--; // 从右向左找第一个小于temp的数

                     if(l < r)//如果上面循环结束，依然l<r，表示满足交换条件
                         a[l++] = a[r];//将右边第一个小于temp的数放在左边，因为上面temp保存了值，不用担心覆盖。相当于a[l]=a[r];     l++;  两条语句的简写形式，

                     while(l < r && a[l] < temp)//从左向右遍历找大于temp的数，但是不能越过r
                         l++; // 从左向右找第一个大于temp的数

                     if(l < r)//如果上面循环结束，依然r>l,表示满足交换条件
                         a[r--] = a[l]; //将左边第一个大于temp的数，放在右边，因为它的值已经移动到左边了，不用担心覆盖
                 }
                 a[l] = temp;//最后l下标所在位置，就是temp最终可以确定的位置
                 quickSort(a, left, l-1); /* 递归调用 */
                 quickSort(a, l+1,right); /* 递归调用 */
            }
     }
    /**
     * 打印
     */
    public static void print(int arr[]){
        System.out.print("排序后为：");
        for(int i = 0;i<arr.length;i++){
            System.out.print(arr[i]+" ");
        }
        System.out.println();
    }
}

5. 代码第二版

/**快速排序，不稳定，时间复杂度O(n * logn) 空间复杂度O(n*logn)
     * 这里是快排入口
     */
    public void quickSort(int arr[]){
        quickSort(arr,0,arr.length-1);
    }

    /**
     * 递归主要用于分割左右两个表
     */
    public void quickSort(int arr[],int low,int high){
        if(low<high){//如果左指针超过右指针，表示本次比较完成
            //快速排序，每一趟都会确定一个元素的最终位置，用pivot表示，pivot是枢纽的意思
            int pivotPosition = quickSortPartition(arr, low, high);
            //由pivot为分界点，分成左右两个表
            quickSort(arr,low,pivotPosition-1);//左表排序
            quickSort(arr,pivotPosition+1,high);//右表排序
        }
    }

    /**
     * 这里是每一趟的快速排序代码，指定一个元素作为枢纽pivot，然后以它为中心，小的元素放在它左边，大的放在它右边
     */
    public int quickSortPartition(int arr[],int low,int high){
        int pivot = arr[low];//指定枢纽
        while (low<high){
            while(low<high && arr[high]>=pivot) --high;//从右边找到比枢纽小的
            arr[low] = arr[high];//放在左边
            while(low<high && arr[low]<=pivot) ++low;//从左找到比枢纽大的
            arr[high] = arr[low];//放在右边
        }
        arr[low] = pivot;//最终将枢纽放到它最终的位置
        return low;//最终low指向枢纽最终位置
    }