Java快速排序_快速排序java

快速排序是基于二分的思想，对冒泡排序的一种改进。主要思想是确立一个基数，将小于基数的数放到基数左边，大于基数的数字放到基数的右边，然后在对这两部分进一步排序，从而实现对数组的排序

优点
效率高：时间复杂度平均为O(N*logN)，顾名思义，最快的排序算法；耗费资源少：最优的情况下空间复杂度为：O(logn) ，每一次都平分数组的情况；代码较为简单。
缺点
不稳定，初始序列有序或基本有序时，时间复杂度降为O(n^2)。

图解
有一个无序数组，首先确认一个基数，一般都以第0个元素为基数，然后定义左右指针，我们以左指针所在的位置为基数。
将基数从数组中拿出来，基数所在的位置就会产生一个空位

如果基数在左，就先移动右指针，找到一个小于基数的值，将右指针的所指的值放在左指针所在位置

右指针被操作后移动左指针，找到一个大于基数的值，交换到右指针的位置，右指针自减

重复这个步骤

左右指针重合时，将基数插入到重合位置，比基数小的数都在基数左边，大的数都在右边

对左右数据重复上述步骤，直到排序结束。

代码实现

public static void main(String[] args) {
	int[] arr = new int[]{1, 8, 5, 7, 2, 3, 4, 9, 6, 10};
	quicksort(arr, 0, arr.length - 1);
}

public static void quicksort(int[] arr, int left, int right) {
	if (right >= left) {
		//保存基数
		int basic = arr[left];
		//定义左右指针
		int i = left;
		int j = right;
		while (i < j) {		//左指针小于右指针
			while (i < j && arr[j] > basic) {//操作右指针找到小于基数的下标
				j--;
			}
			if (i < j) {
				arr[i] = arr[j];	//将右指针对应小于基数的值放到左指针所指的位置
				i++;				//左指针自加
			}
			while (i < j && arr[i] < basic) {//相反，找到大于基数的下标
				i++;
			}
			if (i < j) {
				arr[j] = arr[i];	//大于基数的值赋给右指针所指的位置
				j--;				//右指针自减
			}
		}
		arr[i] = basic;				//将基数放入到指针重合处
		quicksort(arr, left, i - 1);	//重复调用，对左半部分数组进行排序
		quicksort(arr, i + 1, right);	//对右半部分数组进行排序
	}
}
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
30
31
32
33

排序结果