排序算法——快速排序

107 阅读 0 评论 71 点赞

我是靠谱客的博主虚拟曲奇，这篇文章主要介绍排序算法——快速排序，现在分享给大家，希望可以做个参考。

快速排序：

排序过程如图：
各种排序算法时间复杂度和空间复杂度

(1)Java代码实现

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
	 * 快速排序：对冒泡排序的一种改进，基本思想是选取一个记录作为枢轴，经过一趟排序，将整段序列分为两个部分，
	 * 其中一部分的值都小于枢轴，另一部分都大于枢轴。然后继续对这两部分继续进行排序，从而使整个序列达到有序。
	 * @param arr	待排序数组
	 * @param begin	起始索引
	 * @param end	结束索引
	 */
	public static void quickSort(int[] arr,int begin,int end){
		if(begin >= end){
			return;
		}
		int key = arr[begin];
		int i = begin;
		int j = end;
		while(i<j){
			while(arr[j]>=key&&i<j){	//从后向前扫描
				j--;
			}
			arr[i]=arr[j];	//遇见小于key的，放到key的位置
			while(arr[i]<key&&i<j){	//从前向后遍历
				i++;
			}
			arr[j]=arr[i];//遇见大于key则放到end索引位置
		}
		arr[j]=key;
		quickSort(arr, begin, j-1);
		quickSort(arr, j+1, end);
	}