算法java快速排序的两种方法（单边循环、双边循环）

快速排序

1、平均时间复杂度是nlog2n，最坏时间复杂度n2
2、数据量较大时，优势非常明显
3、属于不稳定排序

快速排序的两种方法（单边循环、双边循环）
1、单边循环

package cn.itcast.algorithm.suanFa;
/**
 * 快速排序____单边循环
 */

import java.util.Arrays;


public class MainS15 {
    public static void main(String[] args) {
        int[] a = {5, 3, 7, 2, 9, 8, 1, 4};
        quick(a, 0, a.length -1);
    }

    //对quick进行递归
    private static void quick(int[] a, int l, int h){
        if (l >= h){ //区间里面只有一个或者没有元素的时候停止
            return;
        }
        int p = partition(a, l, h);
        quick(a, l, p-1);//左边分区的范围确定
        quick(a, p+1, h);//右边分区的范围确定
    }

    private static int partition(int[] a, int l, int h) {
        int pv = a[h];//选择最右元素作为基准点元素
        int i = l;
        for (int j = l;j < h;j++){  //j指针负责找到比基准点小的元素，找到则与i进行交换
            if (a[j] < pv){
                if (i != j) {
                    swap(a, i, j);
                }
                i++;
            }
        }
        if (i != h) {
            swap(a, h, i);   //最后基准点与i进行交换，i即为分区位置
        }
        System.out.println(Arrays.toString(a)+" i = " + i);
        //返回值代表了基准点元素所在的正确索引，用它确定下一轮分区的边界
        return i;
    }

    private static void swap(int[] a, int s, int i) {
        int temp = a[s];
        a[s] = a[i];
        a[i] = temp;
    }
}

2、双边循环

package cn.itcast.algorithm.suanFa;

import java.util.Arrays;

/**
 * 快速排序____双边循环
 */
public class MainS16 {
    public static void main(String[] args) {
        int[] a = {5, 3, 7, 2, 9, 8, 1, 4};
        System.out.println(Arrays.toString(a));
        quick(a, 0, a.length -1);
    }

    //对quick进行递归
    private static void quick(int[] a, int l, int h){
        if (l >= h){ //区间里面只有一个或者没有元素的时候停止
            return;
        }
        int p = partition(a, l, h);
        quick(a, l, p-1);//左边分区的范围确定
        quick(a, p+1, h);//右边分区的范围确定
    }

    private static int partition(int[] a, int l, int h) {
        int pv = a[l];//选择最左元素作为基准点元素,必须先j后i的查找
        int i = l;
        int j = h;
        while(i < j){
            //j 从右找小的
            //j 指针负责从右向左找比基准点小的元素
            while(i < j && a[j] > pv){
                j--;
            }
            //i 从左找大的
            //i 指针负责从左向右找比基准点大的元素
            while(i < j && a[j] <= pv){
                i++;
            }
            //找到之后二者交换,直至i,j相交，循环停止
            swap(a, i, j);
        }
        swap(a, l, j);
        System.out.println(Arrays.toString(a)+" j = " + j);
        return j;
    }

    private static void swap(int[] a, int s, int i) {
        int temp = a[s];
        a[s] = a[i];
        a[i] = temp;
    }
}