一、快速速排序采用了一种叫分治的思想
分治法的基本思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。
二、快速排序的原理
1、选择一个关键值作为基准值，比基准值小的都在左边序列（一般是无序的），比基准值大的都在右边序列（一般是无序的），一般选择序列的第一个元素作为基准值。
2、第一次循环：
（1）从后往前比较，用基准值和最后一个值比较，如果比基准值小，就交换位置，如果没有继续向前遍历，直到找到第一个比基准值小的值才交换。
（2）找到这个值后，从前往后遍历，如果比基准值大的，交换位置，如果没有向后遍历，直到找打第一个比基准值大的值才交换。
（3）直到从前往后的比较索引 > 从后往前比较的索引，结束第一轮次循环，此时，对于基准值来说，左右两边就是有序的了。 也就是当start == end时，第一轮排序完成
三、快速排序图解
注意：上边的循环之后就得到了基准值左右两边的序列了，交换的是起始和结束的值，不是基准值
start是从前往后遍历的基准值的索引值
end是从后往前遍历的基准值的索引值
四、代码实现
五、完整代码
package cn.dzp.flyroc.day01; import java.util.Arrays; public class QuckSortDemo { public static void main(String[] args){ int[] arr ={12,20,5,16,15,1,30,45}; System.out.println("这是排序前的数："+Arrays.toString(arr)); quickSort(arr, 0, arr.length-1); System.out.println("这是快速排序后的结果："+ Arrays.toString(arr)); } //快速排序 public static void quickSort(int[] arr, int low, int high){ //定义数组，数组的第一个元素索引，数组的最后一个元素索引 int start = low; //定义从前往后的基准值的索引值 int end = high; //定义从后往前基准值的索引值 int key = arr[low]; //定义基准值为第一个元素 while (end > start){ //判断end > start，若是等于就说明基准值左边索引的元素小于右边所有的元素 //从后往前遍历 while (end > start && arr[end] >= key){ //判断后边的元素是否大于基准值，继续寻找 end--; } if (arr[end] < key){ //找到了比基准值小的元素 int temp = arr[end]; arr[end]= arr[start]; arr[start]= temp; } //从前往后遍历 while (end > start && arr[start] < key){ //判断前边的元素是否小于基准值，继续寻找 start++; } if (arr[start] > key){ //找到了比基准值大的元素 int temp = arr[start]; arr[start] = arr[end]; arr[end] = temp; } } //一轮结束，基准值的左边元素比基准值的右边元素都小 //递归 if (low < start){ //判断是左边序列（元素比基准值小的序列） quickSort(arr, low, start-1); //第一个索引位置到基准值索引-1 } if (end < high){ //判断是右边序列（元素比基准值大的序列） quickSort(arr, end+1, high); //基准值索引+1位置到最后一个索引位置 } } } 讯享网
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/52248.html