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

思想：快速排序，关键为划分
（１）定轴值：直接使用第一个值；也可使用三点中值法进行优化。
（２）指针移动：可以使用单向扫描，也可以使用双向扫描法。
代码如下：

import java.util.Arrays;
import java.util.Random;
import java.util.Scanner;
public class QuickSort {
    //快排之双指针一遍扫描法，只对一个指针进行移动
    //快排之关键--划分  单向扫描法
    public static int partition(int[] a,int st,int end){
        int target=a[st];//定好基准值
        int sp=st+1;//开始指针
        while (sp<=end){
            if (a[sp]<=target) sp++;
            else {//若大于基准值，则和末尾指针元素交换元素
                int temp=a[sp];
                a[sp]=a[end];
                a[end]=temp;
                end--;
            }
        }
        a[st]=a[end];//将基准值定位道最终的位置上
        a[end]=target;
        return end;
    }
    public static void quicksort(int[] a,int st,int end){//采用分治法，划分问题，然后递归解决
        if (st<end) {//递归出口
            int p = partition(a, st, end);
            quicksort(a, st, p - 1);
            quicksort(a, p + 1, end);
        }
    }
    //快排之关键--划分  双向扫描法
    //快排的优化思路：对于轴值的选择上，(1)可以选择三点中值法（Arrays.sort便是使用这种方法）
    //(2)也可以使用绝对中值法，但绝对中值的寻找也会比较麻烦
    //(3)对于个数小于8个的数组，可以使用插入排序
    public static int partition1(int[] a,int st,int end){
        int mid=st+((end-st)>>1);//中值下标
        int midvalue=-1;//找到中值的下标
        if ((a[st]<=a[mid]&&a[st]>=a[end])||(a[st]>=a[mid]&&a[st]<=a[end])){//st位置即为中值的位置
            midvalue=st;
        }else if ((a[mid]<=a[st]&&a[mid]>=a[end])||(a[mid]>=a[st]&&a[mid]<=a[end])){//mid位置即为中值的位置
            midvalue=mid;
        }else {midvalue=end;}
        if (st!=midvalue){//mid下标和st不一致时,交换mid下标的元素和第一个元素
        int temp = a[st];
        a[st] = a[midvalue];
        a[midvalue] = temp;
        }
        int target=a[st];//定好基准值
        int sp=st+1;//开始指针
        boolean flag1=false;//设置标志位判断是否已经到达两端的临界值
        boolean flag2=false;
        while (sp<=end){
            if (a[sp]<=target) sp++;
            else flag1=true;
            if (a[end]>target)end--;
            else flag2=true;
            if (flag1&&flag2){
                int temp=a[sp];
                a[sp]=a[end];
                a[end]=temp;
                sp++;
                end--;
                flag1=false;//记得及时回复标志位
                flag2=false;
            }
        }
        a[st]=a[end];//将基准值定位道最终的位置上
        a[end]=target;
        return end;
    }
    public static void quicksort1(int[] a,int st,int end){//采用分治法，划分问题，然后递归解决
        if (st<end) {//递归出口
            int p = partition1(a, st, end);
            quicksort1(a, st, p - 1);
            quicksort1(a, p + 1, end);
        }
    }
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        System.out.println("请输入数组的长度");
        int len=scanner.nextInt();
        int[] a=new int[len];
        for (int i = 0; i <len ; i++) {
            a[i]=new Random().nextInt(20);
        }
        int[] b=Arrays.copyOf(a,a.length);
        System.out.println(Arrays.toString(a));
        quicksort(a,0,len-1);
        System.out.println(Arrays.toString(a));
        System.out.println("--------------");
        quicksort1(b,0,len-1);
        System.out.println(Arrays.toString(b));
    }
}