快速排序
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了快速排序,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2036字,纯文字阅读大概需要3分钟。
内容图文
![快速排序](/upload/InfoBanner/zyjiaocheng/1269/c7b2054462cb459f8056f2c95d11a0b0.jpg)
问题:
Input: s = 7, nums = [5,3,1,7,5,20,2,4,3,2,2,1,2,4,3] Output: [1, 1, 2, 2, 2, 2, 3, 3, 3, 4, 4, 5, 5, 7, 20] /* 例子: 3,8,7,1,2 2,8,7,1,3 2,3,7,1,8 2,1,7,3,8 2,1,3,7,8 1,2,3,7,8 */
状态码朴素写法:
import java.util.Arrays; public class test { public static void main(String[] args) { int[] nums= {5,3,1,7,5,20,2,4,3,2,2,1,2,4,3}; quicklySort(nums,0,nums.length-1); //Arrays.sort(nums); System.out.println(Arrays.toString(nums)); } publicstaticint[] quicklySort(int[] nums,int prefix,int suffix) { //问题出在相同元素时不好判断//解决:相同的时候将其向前移或后移 //问题出在换了一次之后,交换的顺序错误//解决:加入状态码int tempprefix=prefix; int tempsuffix=suffix; int status=0; if (prefix==suffix) return nums; while (prefix<suffix) { if (nums[prefix]>nums[suffix]) { swap(nums,prefix,suffix); status=status^1;//第一次交换状态为1if (status==1) { prefix++; }else { suffix--; } } else { if (status==1) { prefix++; }else { suffix--; } } } if (prefix==suffix) { quicklySort(nums, tempprefix,prefix-1); quicklySort(nums, suffix+1, tempsuffix); } return nums; } publicstaticvoid swap(int[] nums,int prefix,int suffix) { int temp=nums[prefix]; nums[prefix]=nums[suffix]; nums[suffix]=temp; } }
中值无状态码写法:
import java.util.Arrays; public class test { public static void main(String[] args) { int[] nums= {5,3,1,7,5,20,2,4,3,2,2,1,2,4,3}; nums=quicklySort(nums,0,nums.length-1); System.out.println(Arrays.toString(nums)); } publicstaticint[] quicklySort(int[] nums,int prefix,int suffix) { int centervalue=nums[(prefix+suffix)>>1]; if (prefix>=suffix) return nums; int tempprefix=prefix-1; int tempsuffix=suffix+1; while (tempprefix<tempsuffix) { do {tempprefix++;} while (centervalue>nums[tempprefix]); do {tempsuffix--;} while (centervalue<nums[tempsuffix]); if (tempprefix<tempsuffix) { int temp=nums[tempprefix]; nums[tempprefix]=nums[tempsuffix]; nums[tempsuffix]=temp; } } //System.out.println(Arrays.toString(nums)); quicklySort(nums, prefix,tempprefix-1); quicklySort(nums, tempsuffix+1, suffix); return nums; } }
户枢不蠹,流水不腐
原文:https://www.cnblogs.com/yunianzeng/p/13209147.html
内容总结
以上是互联网集市为您收集整理的快速排序全部内容,希望文章能够帮你解决快速排序所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。