`
water84222
  • 浏览: 375111 次
  • 性别: Icon_minigender_1
  • 来自: 大连
社区版块
存档分类
最新评论

各种排序算法java实现

算法JavaJ#Blog 
阅读更多
原文地址 http://blog.csdn.net/lschou520/archive/2008/10/29/3176422.aspx
插入排序:
 
  1. package  org.rut.util.algorithm.support;
  2. import  org.rut.util.algorithm.SortUtil;
  4. public   class  InsertSort  implements  SortUtil.Sort{
  5.      /* (non-Javadoc)
  6.      * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
  7.      */
  8.      public   void  sort( int [] data) {
  9.          int  temp;
  10.          for ( int  i= 1 ;i<data.length;i++){
  11.              for ( int  j=i;(j> 0 )&&(data[j]<data[j- 1 ]);j--){
  12.                 SortUtil.swap(data,j,j- 1 );
  13.             }
  14.         }        
  15.     }
  16. }
冒泡排序:
 
  1. package  org.rut.util.algorithm.support;
  2. import  org.rut.util.algorithm.SortUtil;
  4. public   class  BubbleSort  implements  SortUtil.Sort{
  5.      /* (non-Javadoc)
  6.      * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
  7.      */
  8.      public   void  sort( int [] data) {
  9.          int  temp;
  10.          for ( int  i= 0 ;i<data.length;i++){
  11.              for ( int  j=data.length- 1 ;j>i;j--){
  12.                  if (data[j]<data[j- 1 ]){
  13.                     SortUtil.swap(data,j,j- 1 );
  14.                 }
  15.             }
  16.         }
  17.     }
  18. }
选择排序:
  1. package  org.rut.util.algorithm.support;
  2. import  org.rut.util.algorithm.SortUtil;
  4. public   class  SelectionSort  implements  SortUtil.Sort {
  5.      /*
  6.      * (non-Javadoc)
  7.      * 
  8.      * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
  9.      */
  10.      public   void  sort( int [] data) {
  11.          int  temp;
  12.          for  ( int  i =  0 ; i < data.length; i++) {
  13.              int  lowIndex = i;
  14.              for  ( int  j = data.length -  1 ; j > i; j--) {
  15.                  if  (data[j] < data[lowIndex]) {
  16.                     lowIndex = j;
  17.                 }
  18.             }
  19.             SortUtil.swap(data,i,lowIndex);
  20.         }
  21.     }
  22. }
Shell排序:
  1. package  org.rut.util.algorithm.support;
  2. import  org.rut.util.algorithm.SortUtil;
  4. public   class  ShellSort  implements  SortUtil.Sort{
  5.      /* (non-Javadoc)
  6.      * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
  7.      */
  8.      public   void  sort( int [] data) {
  9.          for ( int  i=data.length/ 2 ;i> 2 ;i/= 2 ){
  10.              for ( int  j= 0 ;j<i;j++){
  11.                 insertSort(data,j,i);
  12.             }
  13.         }
  14.         insertSort(data, 0 , 1 );
  15.     }
  16.      /**
  17.      * @param data
  18.      * @param j
  19.      * @param i
  20.      */
  21.      private   void  insertSort( int [] data,  int  start,  int  inc) {
  22.          int  temp;
  23.          for ( int  i=start+inc;i<data.length;i+=inc){
  24.              for ( int  j=i;(j>=inc)&&(data[j]<data[j-inc]);j-=inc){
  25.                 SortUtil.swap(data,j,j-inc);
  26.             }
  27.         }
  28.     }
  29. }
快速排序:
  1. package  org.rut.util.algorithm.support;
  2. import  org.rut.util.algorithm.SortUtil;
  4. public   class  QuickSort  implements  SortUtil.Sort{
  5.      /* (non-Javadoc)
  6.      * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
  7.      */
  8.      public   void  sort( int [] data) {
  9.         quickSort(data, 0 ,data.length- 1 );        
  10.     }
  11.      private   void  quickSort( int [] data, int  i, int  j){
  12.          int  pivotIndex=(i+j)/ 2 ;
  13.          //swap
  14.         SortUtil.swap(data,pivotIndex,j);
  15.         
  16.          int  k=partition(data,i- 1 ,j,data[j]);
  17.         SortUtil.swap(data,k,j);
  18.          if ((k-i)> 1 ) quickSort(data,i,k- 1 );
  19.          if ((j-k)> 1 ) quickSort(data,k+ 1 ,j);
  20.         
  21.     }
  22.      /**
  23.      * @param data
  24.      * @param i
  25.      * @param j
  26.      * @return
  27.      */
  28.      private   int  partition( int [] data,  int  l,  int  r, int  pivot) {
  29.          do {
  30.             while (data[++l]<pivot);
  31.             while ((r!= 0 )&&data[--r]>pivot);
  32.            SortUtil.swap(data,l,r);
  33.         }
  34.          while (l<r);
  35.         SortUtil.swap(data,l,r);        
  36.          return  l;
  37.     }
  38. }
改进后的快速排序:
  1. package  org.rut.util.algorithm.support;
  2. import  org.rut.util.algorithm.SortUtil;
  4. public   class  ImprovedQuickSort  implements  SortUtil.Sort {
  5.      private   static   int  MAX_STACK_SIZE= 4096 ;
  6.      private   static   int  THRESHOLD= 10 ;
  7.      /* (non-Javadoc)
  8.      * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
  9.      */
  10.      public   void  sort( int [] data) {
  11.          int [] stack= new   int [MAX_STACK_SIZE];
  12.         
  13.          int  top=- 1 ;
  14.          int  pivot;
  15.          int  pivotIndex,l,r;
  16.         
  17.         stack[++top]= 0 ;
  18.         stack[++top]=data.length- 1 ;
  19.         
  20.          while (top> 0 ){
  21.              int  j=stack[top--];
  22.              int  i=stack[top--];
  23.             
  24.             pivotIndex=(i+j)/ 2 ;
  25.             pivot=data[pivotIndex];
  26.             
  27.             SortUtil.swap(data,pivotIndex,j);
  28.             
  29.              //partition
  30.             l=i- 1 ;
  31.             r=j;
  32.              do {
  33.                  while (data[++l]<pivot);
  34.                  while ((r!= 0 )&&(data[--r]>pivot));
  35.                 SortUtil.swap(data,l,r);
  36.             }
  37.              while (l<r);
  38.             SortUtil.swap(data,l,r);
  39.             SortUtil.swap(data,l,j);
  40.             
  41.              if ((l-i)>THRESHOLD){
  42.                 stack[++top]=i;
  43.                 stack[++top]=l- 1 ;
  44.             }
  45.              if ((j-l)>THRESHOLD){
  46.                 stack[++top]=l+ 1 ;
  47.                 stack[++top]=j;
  48.             }
  49.             
  50.         }
  51.          //new InsertSort().sort(data);
  52.         insertSort(data);
  53.     }
  54.      /**
  55.      * @param data
  56.      */
  57.      private   void  insertSort( int [] data) {
  58.          int  temp;
  59.          for ( int  i= 1 ;i<data.length;i++){
  60.              for ( int  j=i;(j> 0 )&&(data[j]<data[j- 1 ]);j--){
  61.                 SortUtil.swap(data,j,j- 1 );
  62.             }
  63.         }       
  64.     }
  65. }
归并排序:
  1. package  org.rut.util.algorithm.support;
  2. import  org.rut.util.algorithm.SortUtil;
  4. public   class  MergeSort  implements  SortUtil.Sort{
  5.      /* (non-Javadoc)
  6.      * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
  7.      */
  8.      public   void  sort( int [] data) {
  9.          int [] temp= new   int [data.length];
  10.         mergeSort(data,temp, 0 ,data.length- 1 );
  11.     }
  12.     
  13.      private   void  mergeSort( int [] data, int [] temp, int  l, int  r){
  14.          int  mid=(l+r)/ 2 ;
  15.          if (l==r)  return  ;
  16.         mergeSort(data,temp,l,mid);
  17.         mergeSort(data,temp,mid+ 1 ,r);
  18.          for ( int  i=l;i<=r;i++){
  19.             temp[i]=data[i];
  20.         }
  21.          int  i1=l;
  22.          int  i2=mid+ 1 ;
  23.          for ( int  cur=l;cur<=r;cur++){
  24.              if (i1==mid+ 1 )
  25.                 data[cur]=temp[i2++];
  26.              else   if (i2>r)
  27.                 data[cur]=temp[i1++];
  28.              else   if (temp[i1]<temp[i2])
  29.                 data[cur]=temp[i1++];
  30.              else
  31.                 data[cur]=temp[i2++];            
  32.         }
  33.     }
  34. }
改进后的归并排序:
 
  1. package  org.rut.util.algorithm.support;
  2. import  org.rut.util.algorithm.SortUtil;
  4. public   class  ImprovedMergeSort  implements  SortUtil.Sort {
  5.      private   static   final   int  THRESHOLD =  10 ;
  6.      /*
  7.      * (non-Javadoc)
  8.      * 
  9.      * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
  10.      */
  11.      public   void  sort( int [] data) {
  12.          int [] temp= new   int [data.length];
  13.         mergeSort(data,temp, 0 ,data.length- 1 );
  14.     }
  15.      private   void  mergeSort( int [] data,  int [] temp,  int  l,  int  r) {
  16.          int  i, j, k;
  17.          int  mid = (l + r) /  2 ;
  18.          if  (l == r)
  19.              return ;
  20.          if  ((mid - l) >= THRESHOLD)
  21.             mergeSort(data, temp, l, mid);
  22.          else
  23.             insertSort(data, l, mid - l +  1 );
  24.          if  ((r - mid) > THRESHOLD)
  25.             mergeSort(data, temp, mid +  1 , r);
  26.          else
  27.             insertSort(data, mid +  1 , r - mid);
  28.          for  (i = l; i <= mid; i++) {
  29.             temp[i] = data[i];
  30.         }
  31.          for  (j =  1 ; j <= r - mid; j++) {
  32.             temp[r - j +  1 ] = data[j + mid];
  33.         }
  34.          int  a = temp[l];
  35.          int  b = temp[r];
  36.          for  (i = l, j = r, k = l; k <= r; k++) {
  37.              if  (a < b) {
  38.                 data[k] = temp[i++];
  39.                 a = temp[i];
  40.             }  else  {
  41.                 data[k] = temp[j--];
  42.                 b = temp[j];
  43.             }
  44.         }
  45.     }
  46.      /**
  47.      * @param data
  48.      * @param l
  49.      * @param i
  50.      */
  51.      private   void  insertSort( int [] data,  int  start,  int  len) {
  52.          for ( int  i=start+ 1 ;i<start+len;i++){
  53.              for ( int  j=i;(j>start) && data[j]<data[j- 1 ];j--){
  54.                 SortUtil.swap(data,j,j- 1 );
  55.             }
  56.         }
  57.     }
  58. }
堆排序:
  1. package  org.rut.util.algorithm.support;
  2. import  org.rut.util.algorithm.SortUtil;
  4. public   class  HeapSort  implements  SortUtil.Sort{
  5.      /* (non-Javadoc)
  6.      * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
  7.      */
  8.      public   void  sort( int [] data) {
  9.         MaxHeap h= new  MaxHeap();
  10.         h.init(data);
  11.          for ( int  i= 0 ;i<data.length;i++)
  12.             h.remove();
  13.         System.arraycopy(h.queue, 1 ,data, 0 ,data.length);
  14.     }
  16.       private   static   class  MaxHeap{
  17.          
  18.         
  19.          void  init( int [] data){
  20.              this .queue= new   int [data.length+ 1 ];
  21.              for ( int  i= 0 ;i<data.length;i++){
  22.                 queue[++size]=data[i];
  23.                 fixUp(size);
  24.             }
  25.         }
  26.          
  27.          private   int  size= 0 ;
  28.          private   int [] queue;
  29.                 
  30.          public   int  get() {
  31.              return  queue[ 1 ];
  32.         }
  33.          public   void  remove() {
  34.             SortUtil.swap(queue, 1 ,size--);
  35.             fixDown( 1 );
  36.         }
  37.          //fixdown
  38.          private   void  fixDown( int  k) {
  39.              int  j;
  40.              while  ((j = k <<  1 ) <= size) {
  41.                  if  (j < size && queue[j]<queue[j+ 1 ])
  42.                     j++; 
  43.                  if  (queue[k]>queue[j])  //不用交换
  44.                      break ;
  45.                 SortUtil.swap(queue,j,k);
  46.                 k = j;
  47.             }
  48.         }
  49.          private   void  fixUp( int  k) {
  50.              while  (k >  1 ) {
  51.                  int  j = k >>  1 ;
  52.                  if  (queue[j]>queue[k])
  53.                      break ;
  54.                 SortUtil.swap(queue,j,k);
  55.                 k = j;
  56.             }
  57.         }
  58.     }
  59. }
SortUtil:
  1. package  org.rut.util.algorithm;
  2. import  org.rut.util.algorithm.support.BubbleSort;
  3. import  org.rut.util.algorithm.support.HeapSort;
  4. import  org.rut.util.algorithm.support.ImprovedMergeSort;
  5. import  org.rut.util.algorithm.support.ImprovedQuickSort;
  6. import  org.rut.util.algorithm.support.InsertSort;
  7. import  org.rut.util.algorithm.support.MergeSort;
  8. import  org.rut.util.algorithm.support.QuickSort;
  9. import  org.rut.util.algorithm.support.SelectionSort;
  10. import  org.rut.util.algorithm.support.ShellSort;
  12. public   class  SortUtil {
  13.      public   final   static   int  INSERT =  1 ;
  14.      public   final   static   int  BUBBLE =  2 ;
  15.      public   final   static   int  SELECTION =  3 ;
  16.      public   final   static   int  SHELL =  4 ;
  17.      public   final   static   int  QUICK =  5 ;
  18.      public   final   static   int  IMPROVED_QUICK =  6 ;
  19.      public   final   static   int  MERGE =  7 ;
  20.      public   final   static   int  IMPROVED_MERGE =  8 ;
  21.      public   final   static   int  HEAP =  9 ;
  22.      public   static   void  sort( int [] data) {
  23.         sort(data, IMPROVED_QUICK);
  24.     }
  25.      private   static  String[] name={
  26.              "insert" , "bubble" , "selection" , "shell" , "quick" , "improved_quick" , "merge" , "improved_merge" , "heap"
  27.     };
  28.     
  29.      private   static  Sort[] impl= new  Sort[]{
  30.              new  InsertSort(),
  31.              new  BubbleSort(),
  32.              new  SelectionSort(),
  33.              new  ShellSort(),
  34.              new  QuickSort(),
  35.              new  ImprovedQuickSort(),
  36.              new  MergeSort(),
  37.              new  ImprovedMergeSort(),
  38.              new  HeapSort()
  39.     };
  40.      public   static  String toString( int  algorithm){
  41.          return  name[algorithm- 1 ];
  42.     }
  43.     
  44.      public   static   void  sort( int [] data,  int  algorithm) {
  45.         impl[algorithm- 1 ].sort(data);
  46.     }
  47.      public   static   interface  Sort {
  48.          public   void  sort( int [] data);
  49.     }
  50.      public   static   void  swap( int [] data,  int  i,  int  j) {
  51.          int  temp = data[i];
  52.         data[i] = data[j];
  53.         data[j] = temp;
  54.     }
  55. }
分享到：
| css
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    基于springboot教育资源共享平台源码数据库文档.zip

    基于springboot教育资源共享平台源码数据库文档.zip

    视频笔记linux开发篇

    linux开发篇，配套视频：https://www.bilibili.com/list/474327672?sid=4493702&spm_id_from=333.999.0.0&desc=1

    readera-24-09-08plus2020.apk

    ReadEra 这个阅读应用能够打开下列任何格式的文档： EPUB, PDF, DOC, RTF, TXT, DJVU, FB2, MOBI, 和 CHM. 基本上来说，你可以用它阅读你的设备内存中的任何书籍或者文本文档。 这个应用与划分成章节的文档兼。，有一个书签功能，可以在你阅读的时候，自动保存你的进度。另外，它让你更改页面模式，从几种不同的主题中进行挑选（夜间，白天，棕黑色调，还有控制台）。

    STM32单片机控制舵机旋转

    软件环境：KEIL4 硬件环境：STM32单片机+舵机 控制原理：通过控制输出信号的占空比调节舵机旋转的角度

    基于springboot仓库管理系统源码数据库文档.zip

    基于springboot仓库管理系统源码数据库文档.zip

    酒店管理系统源码C++实现的毕业设计项目源码.zip

    酒店管理系统源码C++实现的毕业设计项目源码.zip，个人大四的毕业设计、经导师指导并认可通过的高分设计项目，评审分98.5分。主要针对计算机相关专业的正在做毕设的学生和需要项目实战练习的学习者，也可作为课程设计、期末大作业。 酒店管理系统源码C++实现的毕业设计项目源码.zip，酒店管理系统源码C++实现的毕业设计项目源码.zip个人大四的毕业设计、经导师指导并认可通过的高分设计项目，评审分98.5分。主要针对计算机相关专业的正在做毕设的学生和需要项目实战练习的学习者，也可作为课程设计、期末大作业。酒店管理系统源码C++实现的毕业设计项目源码.zip酒店管理系统源码C++实现的毕业设计项目源码.zip酒店管理系统源码C++实现的毕业设计项目源码.zip，个人大四的毕业设计、经导师指导并认可通过的高分设计项目，评审分98.5分。主要针对计算机相关专业的正在做毕设的学生和需要项目实战练习的学习者，也可作为课程设计、期末大作业。酒店管理系统源码C++实现的毕业设计项目源码.zip，个人大四的毕业设计、经导师指导并认可通过的高分设计项目，评审分98.5分。主要针对计算机相关专业的正在做毕

    58商铺全新UI试客试用平台网站源码

    58商铺全新UI试客试用平台网站源码

    基于SpringBoot+Vue的轻量级定时任务管理系统.zip

    springboot vue3前后端分离 基于SpringBoot+Vue的轻量级定时任务管理系统.zip

    毕业设计&课设_微博情感分析，用 flask 构建 restful api，含相关算法及数据文件.zip

    该资源内项目源码是个人的课程设计、毕业设计，代码都测试ok，都是运行成功后才上传资源，答辩评审平均分达到96分，放心下载使用！ ## 项目备注 1、该资源内项目代码都经过严格测试运行成功才上传的，请放心下载使用！ 2、本项目适合计算机相关专业(如计科、人工智能、通信工程、自动化、电子信息等)的在校学生、老师或者企业员工下载学习，也适合小白学习进阶，当然也可作为毕设项目、课程设计、作业、项目初期立项演示等。 3、如果基础还行，也可在此代码基础上进行修改，以实现其他功能，也可用于毕设、课设、作业等。 下载后请首先打开README.md文件（如有），仅供学习参考, 切勿用于商业用途。

    4D毫米波雷达点云数据处理方法研究.caj

    4D毫米波雷达点云数据处理方法研究.caj

    S M 2 2 5 8 X T量产工具

    S M 2 2 5 8 X T 量产工具供大家下载使用

    基于springboot的文物管理系统源码数据库文档.zip

    基于springboot的文物管理系统源码数据库文档.zip

    基于springboot的电影院售票管理系统源码数据库文档.zip

    基于springboot的电影院售票管理系统源码数据库文档.zip

    Javaweb仓库管理系统项目源码.zip

    基于Java web 实现的仓库管理系统源码，适用于初学者了解Java web的开发过程以及仓库管理系统的实现。

    美容美发项目，使用django框架，前后端一体化项目

    美容美发项目，使用django框架，前后端一体化项目

    2023年中国在线票务行业市场规模约为24.99亿元，挖掘市场新机遇

    在线票务：2023年中国在线票务行业市场规模约为24.99亿元，挖掘市场蓝海新机遇 在数字浪潮的席卷下，传统的票务销售模式正经历着前所未有的变革。纸质门票逐渐淡出人们的视野，取而代之的是便捷、高效的数字和移动票务。这一转变不仅为消费者带来了前所未有的购票体验，更为在线票务平台开辟了广阔的发展空间和市场机遇。随着国民经济的持续增长和文体娱乐行业的蓬勃发展，中国在线票务行业正站在时代的风口浪尖，等待着每一位有志之士的加入。那么，这片蓝海市场究竟蕴藏着怎样的潜力？又该如何把握机遇，实现突破？让我们一同探索。 市场概况： 近年来，中国在线票务行业市场规模持续扩大，展现出强劲的增长势头。据QYResearch数据显示，2023年中国在线票务行业市场规模约为24.99亿元，尽管受到宏观经济的影响，市场规模增速放缓，但整体趋势依然向好。这一增长主要得益于国民人均收入的不断提高、电影及演出行业的快速发展以及政府政策的支持。例如，2023年财政部、国家电影局发布的《关于阶段性免征国家电影事业发展专项资金政策的公告》，为电影行业注入了强劲动力，进而推动了在线票务市场规模的扩大。 技术创新与趋势： 技术进步

    基于SpringBoot的养老院管理系统源码数据库文档.zip

    基于SpringBoot的养老院管理系统源码数据库文档.zip

    毕业设计&课设_含构建设置及相关操作，基于特定技术，具体功能未详细说明.zip

    该资源内项目源码是个人的课程设计、毕业设计，代码都测试ok，都是运行成功后才上传资源，答辩评审平均分达到96分，放心下载使用！ ## 项目备注 1、该资源内项目代码都经过严格测试运行成功才上传的，请放心下载使用！ 2、本项目适合计算机相关专业(如计科、人工智能、通信工程、自动化、电子信息等)的在校学生、老师或者企业员工下载学习，也适合小白学习进阶，当然也可作为毕设项目、课程设计、作业、项目初期立项演示等。 3、如果基础还行，也可在此代码基础上进行修改，以实现其他功能，也可用于毕设、课设、作业等。 下载后请首先打开README.md文件（如有），仅供学习参考, 切勿用于商业用途。

    Go语言入门指南：基础语法、并发编程详解

    内容概要：本文档是一份详细的Go语言教程，从基础概念介绍到高级主题均有覆盖。主要内容包括Go语言的基础语法、数据类型、控制结构、函数、结构体、接口和并发编程等方面。通过具体示例介绍了如何使用Go语言进行开发。 适合人群：初学者和有一定经验的程序员都可以从这篇教程中受益，特别是那些想要快速掌握Go语言并应用于实际项目的开发者。 使用场景及目标：适用于初学者系统学习Go语言的基础知识和常用功能；也可以作为已有开发经验者的参考资料，帮助他们解决具体的编程问题，提高开发效率。 其他说明：本教程不仅包含了Go语言的基本知识点，还重点讲解了其独特的并发编程模型。读者在学习过程中应该注重理论与实践相结合，通过实际编写代码来加深理解和记忆。

Magicbox
Global site tag (gtag.js) - Google Analytics