经典算法之快速排序(Quick Sort)

发表于 | 分类于

原理

快速排序(Quick Sort)使用分治法策略。
它的基本思想是：选择一个基准数，通过一趟排序将要排序的数据分割成独立的两部分；其中一部分的所有数据都比另外一部分的所有数据都要小。然后，再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

快速排序流程：
(1) 从数列中挑出一个基准值。
(2) 将所有比基准值小的摆放在基准前面，所有比基准值大的摆在基准的后面(相同的数可以到任一边)；在这个分区退出之后，该基准就处于数列的中间位置。
(3) 递归地把”基准值前面的子数列”和”基准值后面的子数列”进行排序。

时间复杂度

快速排序之所比较快，因为相比冒泡排序，每次交换是跳跃式的。每次排序的时候设置一个基准点，将小于等于基准点的数全部放到基准点的左边，将大于等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样每次只能在相邻的数之间进行交换，交换的距离就大的多了。因此总的比较和交换次数就少了，速度自然就提高了。当然在最坏的情况下，仍可能是相邻的两个数进行了交换。因此快速排序的最差时间复杂度和冒泡排序是一样的都是O(n^2 )，它的平均时间复杂度为O(N*logN)。

代码实现

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
34
35
import java.util.Arrays;
public class QuickSort_01 {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] nums = { 5, 4, 9, 1, 7, 6, 2, 3, 8 };
		quickSort(nums, 0, nums.length - 1);
		System.out.println(Arrays.toString(nums));
	}
	
	private static void quickSort(int[] nums, int low, int high) {
		if (low < high) {
			int index = getIndex(nums, low, high);
			// 进行迭代对index之前和之后的数组进行相同的操作使整个数组变成有序
			quickSort(nums, 0, index - 1);
			quickSort(nums, index + 1, high);
		}
	}

	private static int getIndex(int[] nums, int low, int high) {
		int base = nums[low];
		while (low < high) {
			// 当队尾的元素大于等于基准数据时,向前挪动high指针
			while (low < high && nums[high] > base) {
				high--;
			}
			nums[low] = nums[high];
			while (low < high && nums[low] < base) {
				low++;
			}
			nums[high] = nums[low];
		}
		nums[low] = base;
		return low; // 返回base的正确位置
	}
}