Java-快速排序的学习使用与注意事项

快速排序

讲解：

简单的来说就是选择一个基准数（相当于一个参考对象）把大于基准数的数都放在他的左边，小于它的数都放在右边然后进行左右两边再次进行相同操作（递归），最后得到从小到大的有序的数。在这不详细讲解，大概详情如下图（该图来自《啊哈！算法》，感兴趣的朋友也可以去看一下，在这阿夜主要是想记录下下面的注意事项）。

注意：

基准数选择与左右指针移动的先后顺序有关，如我们的基准数的选择更偏向于较小的数的那边，则我们应该先移动比基准数大的那边的指针。（不懂的话可以根据下面代码实现好好想想，也可以试一试看交换后面两个while的顺序后的结果）

package algorithm;

import java.util.Arrays;

import org.junit.Test;

public class QuickSort {
	static int num = 0;
	public void quickSort(int[] arr, int left, int right) {		
		
		//递归出口   是否大于等于效率更高。
		if (left >= right ) {
			return;
		}
		
		int i = left;
		int j = right;
		num++;
		//基准数  相当于参照物
		int pivot = arr[i];
		while (i < j) {
			//注意：此时一定时要先往左移动右边的指针，不然会出现错误。因为我们基准数选取的
			//左边的位置，以为左边的数都比基准数小，为了确保最后i=j的时候的数也比基准数小
			//就只不能先把大于基准的数排完留下的才一定是满足与基准数交换的比他小的数。
			
			
			//如果j位置的元素大于或者等于基数，则向左移动
			while (arr[j] >= pivot && i < j) {
				j--;
			}
			//如果i位置的元素小于或者等于基数，则向右移
			while (arr[i] <= pivot && i < j) {
				i++;
			}
			//交换i位置和j位置的元素
			
			int temp = arr[i];
			arr[i] = arr[j];
			arr[j] = temp;
			
		}
		//当i和j相遇，与基准数交换该位置元素
		arr[left] = arr[i];
		arr[i] = pivot;
		
		quickSort(arr, left, i - 1);
		quickSort(arr, j + 1, right);
	}
	
	@Test
	public void test(){
		int[] a = {6, 1, 2, 7, 9, 8, 4, 5, 10, 8};
		quickSort(a, 0, a.length-1);
		System.out.println(Arrays.toString(a));
		System.out.println(System.currentTimeMillis());
		System.out.println(num);
	}
}