Java实现快速排序

快速排序的原理：

选择一个基准数，让数组中的其他数与基准数做对比，比基准数小的放在它左边，比基准数大的放在它右边。之后对左边部分再进行如上得操作，对右边的部分也进行如上得操作，即递归调用这个方法。

蓝色是基准数，左边的绿色是low+1指针，右边是high指针。向右依次，将比基准数小的数与基准数交换到左边，同时low++，比基准数大的数与high指针的数交换，交换到最右端，同时high--。

63 9 2 4 0 7 81

以第一个数6为基准数，与3比较，6比3大，所以交换6和3

369 2 4 0 7 81

6与9对比，9比6大，所以将9与1交换

361 2 4 0 78 9

3 162 4 0 78 9

3 1 264 0 78 9

3 1 2 460 78 9

3 1 2 4 0678 9

3 1 2 4 068 7 9

到这里第一次Sort函数执行完成，以6为基准，左边的值比6小，右边的值比6大。

代码：

import java.util.Arrays;

public class Sort {
	public static void main(String[] args) {
		int[] arr = { 6 ,3 ,9 ,2, 4, 0 ,7 ,8 ,1};
		int k = 9;
		Quick(arr,0,arr.length-1);
		System.out.println(Arrays.toString(arr));
	}
	public static void Quick(int[] arr, int low, int high) {
		int p = arr[low];
		int tlow = low;
		int thigh = high;
		while(tlow<thigh) {
			if(arr[tlow+1]<p) {
				int temp = arr[tlow];
				arr[tlow] = arr[tlow+1];
				arr[tlow+1] = temp;
				tlow++;
			}
			else {
				int temp = arr[thigh];
				arr[thigh] = arr[tlow+1];
				arr[tlow+1] = temp;
				thigh--;
			}
			//System.out.println(Arrays.toString(arr));
		}
		arr[tlow]=p;
		//System.out.println(tlow);
		if(tlow-1>low) Quick(arr, low, tlow-1);
		if(high>tlow+1) Quick(arr, tlow+1, high);
	}

}

运行结果：

[0, 1, 2, 3, 4, 6, 7, 8, 9]

面试常问的两个问题：

1、快速排序如何优化？

快速排序如果碰到有序数组，性能很差。因为以开头或末尾作为基准时，快速排序无法分成两份。

换基准数等。

2、用快速排序找到数组中第k大的数？

在降序排序中，基准数的下标是k-1时即为第k大的数，如果不是的话继续递归。如果基准数中不存在k-1，那么就在排序后的数组中输出arr[k-1]。