请选择 进入手机版 | 继续访问电脑版

学JAVA网

 找回密码
 立即注册

Java版本快速排序的简单实现。

[复制链接]
发表于 2018-11-28 09:15:37 |显示全部楼层
快速排序的原理:选择一个关键值作为基准值。比基准值小的都在左边序列(一般是无序的),比基准值大的都在右边(一般是无序的)。一般选择序列的第一个元素。
一次循环:从后往前比较,用基准值和最后一个值比较,如果比基准值小的交换位置,如果没有继续比较下一个,直到找到第一个比基准值小的值才交换。找到这个值之后,又从前往后开始比较,如果有比基准值大的,交换位置,如果没有继续比较下一个,直到找到第一个比基准值大的值才交换。直到从前往后的比较索引>从后往前比较的索引,结束第一次循环,此时,对于基准值来说,左右两边就是有序的了。
接着分别比较左右两边的序列,重复上述的循环
Java版本快速排序的简单实现。

  1. public class C{

  2.     public static void main(String []args){
  3.        System.out.println("Hello World");
  4.        int[] a = {12,20,5,16,15,1,30,45,23,9};
  5.        int start = 0;
  6.        int end = a.length-1;
  7.        sort(a,start,end);
  8.        for(int i = 0; i<a.length; i++){
  9.             System.out.println(a[i]);
  10.         }
  11.       
  12.     }
  13.    
  14.     public static void sort(int[] a,int low,int high){
  15.         int start = low;
  16.         int end = high;
  17.         int key = a[low];
  18.         
  19.         
  20.         while(end>start){
  21.             //从后往前比较
  22.             while(end>start&&a[end]>=key)  //如果没有比关键值小的,比较下一个,直到有比关键值小的交换位置,然后又从前往后比较
  23.                 end--;
  24.             if(a[end]<=key){
  25.                 int temp = a[end];
  26.                 a[end] = a[start];
  27.                 a[start] = temp;
  28.             }
  29.             //从前往后比较
  30.             while(end>start&&a[start]<=key)//如果没有比关键值大的,比较下一个,直到有比关键值大的交换位置
  31.                start++;
  32.             if(a[start]>=key){
  33.                 int temp = a[start];
  34.                 a[start] = a[end];
  35.                 a[end] = temp;
  36.             }
  37.         //此时第一次循环比较结束,关键值的位置已经确定了。左边的值都比关键值小,右边的值都比关键值大,但是两边的顺序还有可能是不一样的,进行下面的递归调用
  38.         }
  39.         //递归
  40.         if(start>low) sort(a,low,start-1);//左边序列。第一个索引位置到关键值索引-1
  41.         if(end<high) sort(a,end+1,high);//右边序列。从关键值索引+1到最后一个
  42.     }
  43.    
  44. }
复制代码
EN

快速排序.png


D
您需要登录后才可以回帖 登录 | 立即注册

Archiver|手机版|学JAVA网

GMT+8, 2018-12-16 20:18 , Processed in 0.184128 second(s), 24 queries .

Powered by Discuz! X2.5

© 2001-2012 Comsenz Inc.

Copyright © 2015-2018 xuejava网 / 鲁ICP备17054568号-1
回顶部