快速排序 java实现

原理

　　快速排序的原理：选择一个关键值作为基准值。比基准值小的都在左边序列（一般是无序的），比基准值大的都在右边（一般是无序的）。一般选择序列的第一个元素。

　　一次循环：从后往前比较，用基准值和最后一个值比较，如果比基准值小的交换位置，如果没有继续比较下一个，直到找到第一个比基准值小的值才交换。找到这个值之后，又从前往后开始比较，如果有比基准值大的，交换位置，如果没有继续比较下一个，直到找到第一个比基准值大的值才交换。直到从前往后的比较索引>从后往前比较的索引，结束第一次循环，此时，对于基准值来说，左右两边就是有序的了。接着分别比较左右两边的序列，重复上述的循环。

例如: 数组 int[] arr={5,2,8,4,9,1}; 第一趟排序：选 5 为关键字,low=0,high=5 从 high 开始由，后向前找，找到比 5 小的第一个数 a[5]=1,进行替换 排序结果为:1 2 8 4 9 5 从 low 开始向后搜索,找到比 5 小的,交换 1 2 5 4 9 8 从 high 开始由，后向前找，找到比 5 小,交换 1 2 4 5 9 8 直至 low 与 high 相遇重合,第一趟排序结束 以关键字为界,分成左右两个子序列,左边都比 5 小,右边都比 5 大 排序结果:1 2 4 5 9 8

第二趟排序： 以相同的方式排序左子序列 1 2 4 选 1 为关键字 ,low=0,high=2 从 high 开始由，后向前找,找到比 1 小,没有,直至 low 与 high 相遇重合,第二趟 排序结束 第二趟以 1 为界,将左子序列分为两个序列,左边没有数据,右边 2,4 两个序列 排序结果: 1 2 4 5 9 8

以相同的方式排序子序列 2 4 选 2 位关键字 ,low=1,high=2 从 high 开始由，后向前找,找到比 2 小,没有,直至 low 与 high 相遇重合,第三趟 排序结束 第三趟以 2 为界,将子序列分为两个序列,左边没有数据,右边 4 两个序列 排序结果: 1 2 4 5 9 8

第四趟排序： 以相同的方式排序子序列 9,8 选 9 位关键字 ,low=4,high=5 从 high 开始由，后向前找,找到比 9 小,交换 8,9 第四趟以 9 为界,将子序列分为两个序列,左边 8,右边没有数据 排序结果: 1 2 4 5 8 9 快速排序是递归思想,可以采用递归的方式进行排序

Java代码

public static  void quickSort(int array[],int start,int end) {
		int left = start;
		int right = end;
		int key = array[start];
		while (left < right) {
			//从后往前找，找到比key小的数，就交换位置
			while (left < right && key <= array[right]) {
				right--;
			}
			if (key > array[right]) {
				int temp = array[left];
				array[left] = array[right];
				array[right] = temp;
			}
			
			//从前往后比较，找到比key大的数，交换位置
			while (right > left && key >= array[left]) {
				left++;
			}
			if (key < array[left]) {
				int temp = array[left];
				array[left] = array[right];
				array[right] = temp;
			}
		}
		
		if (left > start){
			quickSort(array, start, left - 1);//左边序列,第一个索引位置到关键字索引-1
		}
		if (right < end){
			quickSort(array, right + 1, end);//右边序列,从关键字索引+1到最后一个位置
		}
}

忘记了就来看一下。