摘要:本文主要向大家介绍了JAVA语言快速排序实现教程,通过具体的内容向大家展示,希望对大家学习JAVA语言有所帮助。
本文主要向大家介绍了JAVA语言快速排序实现教程,通过具体的内容向大家展示,希望对大家学习JAVA语言有所帮助。
快速排序,顾名思义,是一种速度快,效率高的排序算法。
快排原理:
在要排的数(比如数组A)中选择一个中心值key(比如A[0]),通过一趟排序将数组A分成两部分,其中以key为中心,key右边都比key大,key左边的都key小,然后对这两部分分别重复这个过程,直到整个有序。
整个快排的过程就简化为了一趟排序的过程,然后递归调用就行了。
一趟排序的方法:
1,定义i=0,j=A.lenght-1,i为第一个数的下标,j为最后一个数下标
2,从数组的最后一个数Aj从右往左找,找到第一小于key的数,记为Aj;
3,从数组的第一个数Ai 从左往右找,找到第一个大于key的数,记为Ai;
4,交换Ai 和Aj
5,重复这个过程,直到 i=j
6,调整key的位置,把A[i] 和key交换
假设要排的数组为:A[8] ={ 5 2 8 9 2 3 4 9 }
选择 key = 5, 开始时 i=0,j=7
index 0 1 2 3 4 5 6 7
开始: 5 2 8 9 2 3 4 9
i j
第一次找 5 2 8 9 2 3 4 9
i j
交换: 5 2 4 9 2 3 8 9
i j
第二次找 5 2 4 9 2 3 8 9
i j
交换: 5 2 4 3 2 9 8 9
i j
第三次找 5 2 4 3 2 9 8 9
ij
调整key: 2 5 4 3 5 9 8 9
ij
以下为代码:
[java] view plain copy
1. <code class="language-java">package com.quicksort;
2.
3. import java.util.Arrays;
4.
5. public class QuickSort {
6. public static void main(String[] args) {
7. int[] a = {1, 2, 4, 5, 7, 4, 5 ,3 ,9 ,0};
8. System.out.println(Arrays.toString(a));
9. quickSort(a);
10. System.out.println(Arrays.toString(a));
11. }
12.
13. public static void quickSort(int[] a) {
14. if(a.length>0) {
15. quickSort(a, 0 , a.length-1);
16. }
17. }
18.
19. private static void quickSort(int[] a, int low, int high) {
20. //1,找到递归算法的出口
21. if( low > high) {
22. return;
23. }
24. //2, 存
25. int i = low;
26. int j = high;
27. //3,key
28. int key = a[ low ];
29. //4,完成一趟排序
30. while( i< j) {
31. //4.1 ,从右往左找到第一个小于key的数
32. while(i<j && a[j] > key){
33. j--;
34. }
35. // 4.2 从左往右找到第一个大于key的数
36. while( i<j && a[i] <= key) {
37. i++;
38. }
39. //4.3 交换
40. if(i<j) {
41. int p = a[i];
42. a[i] = a[j];
43. a[j] = p;
44. }
45. }
46. // 4.4,调整key的位置
47. int p = a[i];
48. a[i] = a[low];
49. a[low] = p;
50. //5, 对key左边的数快排
51. quickSort(a, low, i-1 );
52. //6, 对key右边的数快排
53. quickSort(a, i+1, high);
54. }
55. }
56.
57.
58.
59.
60.
61. </code>
本文由职坐标整理并发布,希望对同学们有所帮助。了解更多详情请关注编程语言JAVA频道!
您输入的评论内容中包含违禁敏感词
我知道了
请输入正确的手机号码
请输入正确的验证码
您今天的短信下发次数太多了,明天再试试吧!
我们会在第一时间安排职业规划师联系您!
您也可以联系我们的职业规划师咨询:
版权所有 职坐标-一站式IT培训就业服务领导者 沪ICP备13042190号-4
上海海同信息科技有限公司 Copyright ©2015 www.zhizuobiao.com,All Rights Reserved.
沪公网安备 31011502005948号