算法–快速排序

交换排序

要了解快速排序，需要先来了解一下交换排序。所谓交换排序，就是根据序列中两个元素关键字的比较结果来对换两个记录在序列中的位置。

递归

方法1：左右指针法

方法2：前后指针法

public class QuickSort {
    public static void main(String[] args) {
        int[] a = {3,5,2,1,7,6,4};
        QuickSort(a,0,6);
        for(int a1:a){
            System.out.print(a1+"--");
        }
    }
    //左右指针
    public static int  Partition(int[] a,int low,int high){
        int i = low,j = high;
        int tmp = a[low];//找到本次要排序的数，这里用的不是算法导论上的，用的是数据结构上的
        while(i<j){
            // 必须先从右向左找,这里为啥
            while(i<j && a[j]>=tmp){
                j--;
            }
            if(i<j){
                a[i]=a[j];
                i++;
            }
            //这个顺序不能反
            while(i<j && a[i]<tmp)
                i++;
            if(i<j){
                a[j] = a[i];
                j--;
            }
        }
        //最后，index放到对应位置
        a[i] = tmp;
        return i;
    }
    public static void swap(int[] data, int a, int b) {
        int temp;
        temp = data[a]; data[a] = data[b]; data[b] = temp;
    }
    //前后指针，这里的变量和图上不太一致
    //high代表r
    //i代表p
    public static int Partition1(int[] a,int low,int high){
        int tmp =a[high];
        int p = low-1;
        //从第一个循环到倒数第二个（high-1）元素，和tmp进行比较
        for(int i=low;i<high;i++){
            if(a[i]<=tmp){
                p++;
                swap(a,p,i);
            }
        }
        swap(a,p+1,high);
        return p+1;
    }
    public static void QuickSort(int[] a,int low,int high){
        if(low<high){
            int pivot = Partition1(a,low,high);
            QuickSort(a,low,pivot-1);
            QuickSort(a,pivot+1,high);//这里好像可以剪枝操作
        }

    }
}

非递归

思路就是利用栈来保存左右区间

public static void GenerQuickSort(int[] arr, int left, int right) {
		//定义一个栈
		Stack<Integer> stack = new Stack<>();
		//前提条件就是left < right
		if(left < right) {
			stack.push(left);  //将left压进栈中
			stack.push(right);  //将right压进栈中
			while(!stack.isEmpty()) {  //当栈不为空时，进行以后的操作
				right = stack.pop();  //取出栈中第一位，我最后压进的是right，所以它是最末位的下标；
				left = stack.pop();  //最底下的是left的下标。到底哪个对应那个，要看你是怎么压进去的				
				int index = Partition(arr, left, right);  //得到基准数的下标
				if(index-1 > left) {   //判断基准数左边的数的下标与开始下标的大小
					stack.push(left);    //根据情况压进去以基准数分开的下标的左半边部分的低位
					stack.push(index -1);   //根据情况压进去以基准数分开的下标的左半边部分的高位
				}
				
				if(index+1 < right) {  //判断基准数右边的数的下标与开始下标的大小
					stack.push(index + 1);   //根据情况压进去以基准数分开的下标的右半边部分的低位
					stack.push(right);   //根据情况压进去以基准数分开的下标的右半边部分的高位
				}
			}
		}
	}

原文链接：https://blog.csdn.net/lzf_hlh/article/details/88775587
已做修改