黑马程序员技术交流社区

标题: 关于排序的学习 [打印本页]
作者: luodim    时间: 2015-6-16 18:32
标题: 关于排序的学习
排序是一个非常重要的功能。
由于排序是如此常用的操作，在学习Arrays工具类及Collections工具类时，这两个工具类均提供了静态sort( )方法，可以直接调用方法实现排序。
虽然调用方法可以快速方便的实现排序，但在面试中面试官可能要求面试者自己编写代码实现数组排序，此时一般会采用冒泡排序及选择排序实现
冒泡排序的实现如下图所示


基本思想为：相邻元素两两比较，大的往后走。第一次完成后，最大值出现在最大索引处。第一次结束，最后那个元素不需要再参与比较。
代码实现为：
  1. <font face="Arial">public class bubbleSort {  
  2. public  bubbleSort(){  
  3.      int a[]={49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,56,17,18,23,34,15,35,25,53,51};  
  4.     int temp=0;  
  5.     for(int i=0;i<a.length-1;i++){  
  6.         for(int j=0;j<a.length-1-i;j++){  
  7.         if(a[j]>a[j+1]){  
  8.             temp=a[j];  
  9.             a[j]=a[j+1];  
  10.             a[j+1]=temp;  
  11.         }  
  12.         }  
  13.     }  
  14.     for(int i=0;i<a.length;i++)  
  15.         System.out.println(a[i]);     
  16. }  
  17. }  </font>
复制代码
由于冒泡排序每一轮中每次比较都会改变比较者与被比较者的位置（索引改变），比较而言选择排序在每轮比较中仅仅改变了被比较者的位置，而比较者的位置不变，可消耗较少的资源实现排序
选择排序的实现如下图所示：

基本思想为：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。每次比较仅做一次交换。
代码的实现为：
  1. public class selectSort {  
  2.   
  3.     public selectSort(){  
  4.   
  5.        int a[]={1,54,6,3,78,34,12,45};  
  6.   
  7.        int position=0;  
  8.   
  9.        for(int i=0;i<a.length;i++){  
  10.   
  11.             
  12.   
  13.            int j=i+1;  
  14.   
  15.            position=i;  
  16.   
  17.            int temp=a[i];  
  18.   
  19.            for(;j<a.length;j++){  
  20.   
  21.            if(a[j]<temp){  
  22.   
  23.               temp=a[j];  
  24.   
  25.               position=j;  
  26.   
  27.            }  
  28.   
  29.            }  
  30.   
  31.            a[position]=a[i];  
  32.   
  33.            a[i]=temp;  
  34.   
  35.        }  
  36.   
  37.        for(int i=0;i<a.length;i++)  
  38.   
  39.            System.out.println(a[i]);  
  40.   
  41.     }  
  42.   
  43. }  
复制代码
排序的方法有很多种，冒泡与选择排序效率并不算高，但容易理解。而JDK 1.7后，Arrays.sort()封装了快速排序DualPivotQuicksort（具体可参考：http://www.tuicool.com/articles/BfY7Nz）
此外常见的一些排序，如希尔排序等诸君亦可在闲暇时参阅学习。



冒泡排序.png (46.14 KB, 下载次数: 4)

冒泡排序实现

冒泡排序实现
作者: candy_xue    时间: 2015-6-16 21:09
看了下快速排序  更优



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2