目录
1.基本思想
1.1 基本思想
1.2 使用分治策略的三个步骤分析快速排序
1.3归并排序与快速排序比较
2.图解原理
3.代码实现
3.1 实现方式1：选取中间值作为基准值
3.2 实现方式2：选取最右边的值作为基准值
4.性能分析
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"); }}
来源：/content-1-442251.html
如果觉得《数据结构与算法——排序算法（5）——快速排序》对你有帮助，请点赞、收藏，并留下你的观点哦！
