Java|java教程
快速排序,算法
Java-java教程
cms .net 源码,vscode 调试工程,scp链接ubuntu,tomcat有几个节点,异形爬虫,solr php 使用,seo站群怎么操作,虚拟主机换不了网站源码,小说写主题模板lzw
语音小说app源码,技德 盒子 ubuntu,pathon 爬虫淘宝商品,php性能探测,兴宁seo优化lzw
概念
网页播放器源码下载,vscode自动修改标签,安装器ubuntu,搭建tomcat容器,sqlite3 增加外键,基于爬虫的数据分析论文,php 消耗内存,石家庄小学seo培训,网站源码编写,下载好123网页,织梦html5自适应模板lzw
快速排序属于交换排序,主要步骤是使用基准元素进行比较,把小于基准元素的移动到一边,大于基准元素的移动到另一边。从而把数组分成两部分,然后再从这两部分中选取出基准元素,重复上面的步骤。过程如下:
(推荐视频:java视频教学)
这种思路叫做分治法。
基准元素
基准元素的选取可随机选取。下面使用中我会使用第一位的元素作为基准元素。
排序过程
排序拆分过程如下图:
第一轮
第二轮
第三轮
如上图所示:
若元素个数为n,因为排序过程中需要和全部元素都比较一遍,所以时间复杂度为O(n),
而平均情况下排序轮次需要logn轮,因此快速排序的平均时间复杂度为O(nlogn)。
排序的实现方法
实现方法有双边循环法和单边循环法
双边循环法
首选选取基准元素(pivot)4,并设置指针left和right,指向数组最左和最右两个元素,如下:
第一轮指针移动完后,得到如下结构:
然后 left和right指向的元素进行交换:
第一轮循环结束,重新切换到right指针,重复上述步骤。
第二轮循环后,得:
第三轮循环后,得:
第四轮循环后,得:
判断到left和right指针指向同一个元素,指针停止移动,使pivot和指针元素进行交换,得:
宣告该轮循环结束,并根据Pivot元素切分为两部分,这两部分的数组再根据上述步骤进行操作。
实现代码
public class DoubleSort { public static void quickSort(int[] arr, int startIndex, int endIndex) { //递归结束条件 if (startIndex >= endIndex) { return; } // 基准元素位置 int pivotIndex = partition(arr, startIndex, endIndex); // 根据基准元素,分成两部分进行递归排序 quickSort(arr, startIndex, pivotIndex - 1); quickSort(arr, pivotIndex + 1, endIndex); } public static int partition(int[] arr, int startIndex, int endIndex) { // 取第一个元素为基准元素,也可以随机抽取 int pivot = arr[startIndex]; int left = startIndex; int right = endIndex; while (left != right) { // 控制right指针比较并左移 while (left = pivot) {right--; } // 控制left指针比较并右移 while (left < right && arr[left] <= pivot) {left++; } // 交换left和right指针所指向的元素 if (left < right) {int temp = arr[right];arr[right] = arr[left];arr[left] = temp; } } arr[startIndex] = arr[left]; arr[left] = pivot; return left; } 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)); }}
单边循环法
双边循环法从数组的两边比较并交换元素,而单边循环法则从数组的一边遍历,一直往后比较和交换,实现起来更加的简单。
过程如下:
原始数组如下:
遍历到元素3时,因为3 < 4,所以mark右移
然后交换元素
然后就继续遍历,根据上面的步骤进行判断,后面的过程就不写了。
实现代码
public class SingleSort { public static void quickSort(int[] arr, int startIndex, int endIndex) { //递归结束条件 if (startIndex >= endIndex) { return; } // 基准元素位置 int pivotIndex = partition(arr, startIndex, endIndex); // 根据基准元素,分成两部分进行递归排序 quickSort(arr, startIndex, pivotIndex - 1); quickSort(arr, pivotIndex + 1, endIndex); } /*** 分治(单边循环法)* @param arr* @param startIndex* @param endIndex* @return*/ public static int partition(int[] arr, int startIndex, int endIndex) { // 取第一个元素为基准元素,也可以随机抽取 int pivot = arr[startIndex]; int mark = startIndex; for(int i = startIndex + 1; i< arr.length; i++) { if (pivot < arr[i]) {continue; } mark ++; int temp = arr[mark]; arr[mark] = arr[i]; arr[i] = temp; } arr[startIndex] = arr[mark]; arr[mark] = pivot; return mark; } 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)); }}
总结
本人也是初次接触算法,慢慢的去理解算法的思路和实现过程后,真是为自己以往写的算法感到羞愧。该文章也是为了加深自己对快排算法的印象,若文章有不足之处,恳请各位在下方留言补充。感谢各位的阅读。Thanks♪(・ω・)ノ。
参考资料:《小灰的算法之旅》 第四章。
本文来自php中文网,java教学栏目,欢迎学习!