目录
1.基本思想
1.1 基本思想
- 快速排序是基于分治策略的一种排序
-
基本思想
- 1．基准：先从数列中取出一个数作为基准数。
- 2．分区过程：将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
- 3．再对左右区间重复第一、二步，直到各区间只有一个数。
- 注意：快速排序在分的时候，就进行了“排序”处理
1.2 使用分治策略的三个步骤分析快速排序
- 1.分解：将数组A[p..r]划分为两个（可能为空）子数组A[p...q-1]和A[q+1...r]，使得A[p...q-1]中的每一个元素都小于等于A[q]，而A[q]也小于等于A[q+1...r]中的每个元素
- 2.解决：通过递归调用快速排序，对子数组A[p...q-1]和A[q+1...r]进行排序
- 3.合并：因为子数组都是原址排序的，所以不需要合并操作：数组A[p...r]已经有序
1.3 归并排序与快速排序比较
- 归并排序将数组分成连个子数组分别排序，并将有序的子数组归并以将整个数组排序；而快速排序是当两个子数组都有序时，整个数组也就自然有序了
- 归并排序在分的时候不进行任何处理，而快速排序在分的时候，要进行元素交换，保正左边元素小于基准值，右边元素大于基准值
- 归并排序递归调用发生在处理整个数组之前，快速排序递归调用发生在处理整个数组之后
- 归并排序在合并的时候完成排序，快速排序在分的时候完成排序，合并时，什么都不做
- 在归并排序中，一个数组被等分为两半，在快速排序中，切分的位置取决于数组的内容
2.图解原理
3.代码实现
关键词解释
- pivot：基准元素
- partition：将整个数组进行切分
3.1 实现方式1：选取中间值作为基准值
public class QuickSort extends Sort {
/**
* sort方法为外界提供了统一的调用“接口”
* @param arr
*/
@Override
public void sort(Comparable[] arr) {
quickSort(arr,0,arr.length-1);
}
private void quickSort(Comparable[] arr,int left,int right){
if(left >= right){
return;
}
//经过切分后基准值最终索引
int pivot = partition(arr,left,right);
//对pivot左边进行递归切分
quickSort(arr,left,pivot-1);
//对pivot右边进行递归切分
quickSort(arr,pivot+1,right);
}
/**
* 切分数组，切分为左边小于pivot，右边大于pivot
* @param arr
* @param left
* @param right
* @return 返回中间基准值pivot的索引值
*/
private int partition(Comparable[] arr,int left,int right){
//我们这里取中间值基准值，
Comparable pivot = arr[(left+right)/2];
//定义两个指针指向两边
int move_right = left;
int move_left = right;
/**
* 当两个指针相等或向右移动的指针大于向左移动的指针的时候，代表遍历完所有的元素
*
* while循环的目的是让比pivot小的元素在pivot的左边，比pivot大的元素在右边
*/
while(move_right < move_left){
/**
* 右移指针寻找大于等于pivot的值，
*
*
* 最后的情况就是pivot左边全部是小于pivot的，这时，找到的是pivot值
* 然后右边找到的是非pivot的话，就发生交换，等于pivot的话，move_right不一定等于move_left
*
* 因为有可能有多个重复的与pivot本身相同的值，所以交换后，我们也要让指针继续移动，
* 确保通过指针的相对大小判断循环结束，否则，在交换后，不移动指针，可能会形成死循环（两个指针同时指向两个相邻的pivot）
*
*/
while(arr[move_right].compareTo(pivot) < 0){
//右移指针指向的值小于pivot的值，不用交换，指针继续右移
move_right++;
}
/**
* 左移指针寻找小于等于pivot的值
*
* 同上，最后的情况就是找到pivot
*/
while (arr[move_left].compareTo(pivot) > 0){
//左移指针指向的值大于pivot的值，不用交换，指针继续左移
move_left--;
}
//两个指针遍历完所有元素，结束循环
if(move_right >= move_left)
break;
//交换两个指针指向的值
swap(arr,move_right,move_left);
/**
* 迭代，让指针移动
*
* 指针指向的值为pivot的时候，让另一个指针靠近自己，以最终结束循环
*/
//如果右移指针指向pivot，左移指针--
if(arr[move_right].compareTo(pivot) == 0){
move_left--;
}
//如果左移指针指向pivot，右移指针--
if(arr[move_left].compareTo(pivot) == 0){
move_right++;
}
}
/**
* 最终我们需要返回用于切分的基准值的最终索引
*
* 循环过后，两个指针总有一个是指向pivot的，通过以下判断，最终返回pivot的索引
*/
int pivotIndex;
if(arr[move_right] == pivot){
pivotIndex = move_right;
}else{
pivotIndex = move_left;
}
return pivotIndex;
}
}
import java.util.Arrays;
public class SortTest {
public static void main(String[] args) {
Integer[] arr = new Integer[]{8,9,1,7,2,3,5,5,4,4,5,6,0};
System.out.println("未排序的数组为:");
System.out.println(Arrays.toString(arr));
QuickSort quickSort = new QuickSort();
quickSort.sort(arr);
System.out.println("排序后的数组为:");
System.out.println(Arrays.toString(arr));
}
}
3.2 实现方式2：选取最右边的值作为基准值
public class QuickSort extends Sort {
/**
* sort方法为外界提供了统一的调用“接口”
*
* @param arr
*/
@Override
public void sort(Comparable[] arr) {
quickSort(arr, 0, arr.length - 1);
}
private void quickSort(Comparable[] arr, int left, int right) {
if (left >= right) {
return;
}
//经过切分后基准值最终索引
int pivot = partition(arr, left, right);
//对pivot左边进行递归切分
quickSort(arr, left, pivot - 1);
//对pivot右边进行递归切分
quickSort(arr, pivot + 1, right);
}
/**
* 切分数组，切分为左边小于pivot，右边大于pivot
*
* @param arr
* @param left
* @param right
* @return 返回中间基准值pivot的索引值
*/
private int partition(Comparable[] arr, int left, int right) {
//我们这里取最后一个值作为基准值，
Comparable pivot = arr[right];
//定义一个指针,右移记录，i指向小于等于pivot的最后一个值的下一个位置
int i = left; //初始化为起始位置
//遍历left到right-1之间的元素
for (int j = left; j <= right - 1; j++) {
if (arr[j].compareTo(pivot) <= 0) {
//当前遍历元素小于等于基准值
//交换小于等于pivot的最后一个值的下一个位置的值（无所谓它的大小）与当前遍历元素
swap(arr, i, j);
//此时小于等于pivot的最后一个值为交换后的值，所以i+1,在i前面的表示都小于等于pivot
i++;
}
}
//这样遍历完，小于等于pivot的值都被交换到了i位置的前面，最终i位置本身指向的是大于pivot的
//这时，交换i位置处的值和pivot，最终pivot左边是小于等于它的值，pivot右边是大于它的值
swap(arr, i, right);
//最终返回pivot最终的索引值，即i
return i;
}
}
import java.util.Arrays;
public class SortTest {
public static void main(String[] args) {
Integer[] arr = new Integer[]{8,9,1,7,2,3,5,5,4,4,5,6,0,0,343,6789};
System.out.println("未排序的数组为:");
System.out.println(Arrays.toString(arr));
QuickSort quickSort = new QuickSort();
quickSort.sort(arr);
System.out.println("排序后的数组为:");
System.out.println(Arrays.toString(arr));
}
}
4.性能分析
- 快速排序是一种最坏时间复杂度为O(n^2)的排序算法，
- 但是快速排序通常是实际排序应用中最好的选择，因为它的平均性能非常好——它期望的时间复杂度为O(nlgn)，而且O(nlgn)中隐含的常数因子非常小
- 快速排序是原址排序的，所以空间复杂度为O(1)
- 快速排序再虚存环境中也能很好地工作
代码演示示例：
public class SortPerformanceTest {
public static void main(String[] args) {
//创建100000个随机数据
Double[] arr1 = new Double[100000];
for (int i = 0; i < arr1.length; i++) {
arr1[i] = (Double) (Math.random() * 10000000); //这里使用10000000是为了让数据更分散
}
//创建排序类的对象
QuickSort quickSort = new QuickSort();
//使用希尔排序对arr1进行排序
long quickSort_start = System.currentTimeMillis();
quickSort.sort(arr1);
long quickSort_end = System.currentTimeMillis();
System.out.println("快速排序所用的时间为："+(quickSort_end - quickSort_start)+"ms");
}
}