快速 排序

快速 排序

快速排序（Quicksort）是对冒泡排序的一种改进。

基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列

 

package com.wang;

import java.util.Arrays;

public class Test {
    public static void main(String[] args){
        int[] arr= {8,9,1,7,2,3,5,4,6,0};
        quick(arr, 0, arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
    public static void quick(int[] arr,int left,int right) {
		int l=left;
		int r=right;
		int pivot=(left+right)/2;
		int temp;
		//循环的目的是把比pivot小的数放到左边，大的数放到右边
		while(lpivot) {
				r--;
			}
			//结束整个循环
			if (l>=r) {
				break;
			}
			
			arr[l]=arr[l]^arr[r];
			arr[r]=arr[l]^arr[r];
			arr[l]=arr[l]^arr[r];

			//-1 -2 0 0如果是这种情况，上面的循环结束后指向的是0，得让它指向-2
			if (arr[l] == pivot) {
				l--;
			}
			
			if (arr[r] == pivot) {
				r++;
			}
		}
		//防止栈溢出
		if (l==r) {
			l++;
			r--;
		}
		//向左递归，使左边有序
		if (leftr) {
			quick(arr, l, right);
		}
	}
}