QuickSort
快速排序
在每一轮挑选一个基准元素，并让其他比它大的元素移动到数列一边，比它小的元素移动到数列的另一边，从而把数列拆解成了两个部分。
这种思路就叫做分治法。
每次把数列分成两部分，究竟有什么好处呢？
- 假如给定8个元素的数列，一般情况下冒泡排序需要比较8轮，每轮把一个元素移动到数列一端，时间复杂度是O（n^2）。在分治法的思想下，原数列在每一轮被拆分成两部分，每一部分在下一轮又分别被拆分成两部分，直到不可再分为止。这样一共需要多少轮呢？平均情况下需要logn轮，因此快速排序算法的平均时间复杂度是 O（nlogn）。
基准元素的选择
基准元素，英文pivot，用于在分治过程中以此为中心，把其他元素移动到基准元素的左右两边。
最简单的方式是选择数列的第一个元素：这种选择在绝大多数情况是没有问题的，但是对于一个已经存在顺序的数组这种效果就比较差了；
随机选择一个元素作为基准元素。这样一来，即使在数列完全逆序的情况下，也可以有效地将数列分成两部分。
元素的移动
1.挖坑法
- 首先，我们选定基准元素Pivot，并记住这个位置index，这个位置相当于一个“坑”。并且设置两个指针left和right，指向数列的最左和最右两个元素： 如下图
- 从right指针开始，把指针所指向的元素和基准元素做比较。如果比pivot大，则right指针向左移动；如果比pivot小，则把right所指向的元素填入坑中。
第一轮开始
Pivot = 3，left = 0, right = 7
algorithm-Fast-Sort-1.png
第二轮开始
Pivot = 8，left = 3, right = 7
algorithm-Fast-Sort-2.png
第三轮开始
Pivot = 7，left = 3, right = 5
algorithm-Fast-Sort-3.png
1.挖坑法代码实现如下
/**
*
*
* @description
* @see
* @author maozhengwei
* @data 2019-05-23 10:49
* @version V1.0.0
**/
public class QuickSort1 {
public static void quickSort(int[] arr, int startIndex, int endIndex) {
// 递归结束条件：startIndex大等于endIndex的时候
if(startIndex >= endIndex) {
return;
}
// 得到基准元素位置
int pivotIndex = partition(arr, startIndex, endIndex);
// 用分治法递归数列的两部分
quickSort(arr, startIndex, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, endIndex);
}
private static int partition(int[] arr, int startIndex, int endIndex) {
// 取第一个位置的元素作为基准元素
int pivot = arr[startIndex];
int left = startIndex;
int right = endIndex;
// 坑的位置，初始等于pivot的位置
int index = startIndex;
//大循环在左右指针重合或者交错时结束
while ( right >= left ){
//right指针从右向左进行比较
while ( right >= left ) {
if (arr[right] < pivot) {
arr[left] = arr[right];
index = right;
left++;
break;
}
right--;
}
//left指针从左向右进行比较
while ( right >= left ) {
if (arr[left] > pivot) {
arr[right] = arr[left];
index = left;
right--;
break;
}
left++;
}
}
arr[index] = pivot;
return index;
}
public static void main(String[] args) {
int[] arr = new int[] {4,7,6,5,3,2,8,1};
quickSort(arr, 0, arr.length-1);
System.out.println(Arrays.toString(arr));
}
}
2. 指针交换法
指针交换开始都填坑法是一样的，只是元素的交换方式不一样：
从right指针开始，把指针所指向的元素和基准元素做比较。如果大于等于pivot，则指针向左移动；如果小于pivot，则right指针停止移动，切换到left指针。
轮到left指针行动，把指针所指向的元素和基准元素做比较。如果小于等于pivot，则指针向右移动；如果大于pivot，则left指针停止移动：left和right指向的元素进行交换**。
下面是图解：
第一轮：
algorithm-Fast-Sort-4.png
第二轮：
algorithm-Fast-Sort-5.png
第三轮：
algorithm-Fast-Sort-6.png
代码实现：
/**
* 指针交换
* @see
* @author mzw
* @data 2019-05-23 14:42
* @version V1.0.0
**/
public class QuickSort2 {
public static void quickSort2(int[] arr, int startIndex, int endIndex) {
// 递归结束条件：startIndex大等于endIndex的时候
if(startIndex >= endIndex) {
return;
}
// 得到基准元素位置
int pivotIndex = partition(arr, startIndex, endIndex);
// 根据基准元素，分成两部分递归排序
quickSort2(arr, startIndex, pivotIndex - 1);
quickSort2(arr, pivotIndex + 1, endIndex);
}
private static int partition(int[] arr, int startIndex, int endIndex) {
// 取第一个位置的元素作为基准元素
int pivot = arr[startIndex];
int left = startIndex;
int right = endIndex;
while ( right != left ){
//right指针从右向左进行比较,小于则终止循环
while ( left < right && arr[right] > pivot ) {
right--;
}
//left指针从左向右进行比较，大于则准则循环
while ( left < right && arr[left] <= pivot ) {
left++;
}
if (left < right) {
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
}
//指针重合
int p = arr[left];
arr[left] = arr[startIndex];
arr[startIndex] = p;
return left;
}
public static void main(String[] args) {
int[] arr = new int[] {4,7,6,5,3,2,8,1};
quickSort2(arr, 0, arr.length-1);
System.out.println(Arrays.toString(arr));
}
}
