title: 算法基础——快速排序
categories:

• Algorithms
  tags:
• 排序算法
  abbrlink: 254341469
  date: 2019-11-29 16:41:37

排序

快速排序

• 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

思路

1. 一个 arr[N]的数组，首先确定一个分界值，一般的我们选择 arr[0]
2. 然后将后续的元素分别与 arr进行比较，小的集中到数组的左边，大的集中到数组的右边
3. 对两个集合分别重复1 、2步骤，当左右两部分都排序好，整个数组就排序好了

算法

1. 设置两个变量ij,排序开始时，i = 0 ,j =arr.length-1
2. 以第一个数组元素作为分界值，赋值给pivot,pivot =arr[i];
3. 从j开始搜索，从后往前的搜索 j–，找到第一个小于 key的值，将 arr[j] 与arr[i]交换
4. 从i开始搜索，从前往后的搜索 i++，找到第一个大于key的值，将arr[i] 与 arr[j]交换
5. 重复3.4步骤，直到 i==j

代码

public static int[] quickSort(int[] arr, int start, int end) {
		int pivot = arr[start];
		int i = start;
		int j = end;
		int temp;
		while (i < j) {
			while (i < j && arr[j] > pivot) {
				j--;
			}
			temp = arr[i];
			arr[i] = arr[j];
			arr[j] = temp;
			while (i < j && arr[i] < pivot) {
				i++;
			}
			temp = arr[j];
			arr[j] = arr[i];
			arr[i] = temp;
		}
		if (i - 1 > start) {
			arr = quickSort(arr, start, i - 1);
		}
		if (j + 1 < end) {
			arr = quickSort(arr, j + 1, end);
		}
		return arr;
	}

笔记

• 快速排序的一次划分算法从两头交替搜索，直到low和high重合，因此其时间复杂度是O(n)
• 可以证明，快速排序的平均时间复杂度也是O(nlog2n)。因此，该排序方法被认为是目前最好的一种内部排序方法