JAVA语言快速排序实现教程
小标 2018-07-13 来源 : 阅读 950 评论 0

摘要:本文主要向大家介绍了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频道!

本文由 @小标 发布于职坐标。未经许可,禁止转载。
喜欢 | 1 不喜欢 | 1
看完这篇文章有何感觉?已经有2人表态,50%的人喜欢 快给朋友分享吧~
评论(0)
后参与评论

您输入的评论内容中包含违禁敏感词

我知道了

助您圆梦职场 匹配合适岗位
验证码手机号,获得海同独家IT培训资料
选择就业方向:
人工智能物联网
大数据开发/分析
人工智能Python
Java全栈开发
WEB前端+H5

请输入正确的手机号码

请输入正确的验证码

获取验证码

您今天的短信下发次数太多了,明天再试试吧!

提交

我们会在第一时间安排职业规划师联系您!

您也可以联系我们的职业规划师咨询:

小职老师的微信号:z_zhizuobiao
小职老师的微信号:z_zhizuobiao

版权所有 职坐标-一站式IT培训就业服务领导者 沪ICP备13042190号-4
上海海同信息科技有限公司 Copyright ©2015 www.zhizuobiao.com,All Rights Reserved.
 沪公网安备 31011502005948号    

©2015 www.zhizuobiao.com All Rights Reserved

208小时内训课程