[Java--常见排序算法]------冒泡、选择、快速排序

java常用的排序算法(冒泡、选择、快速等)

一、冒泡排序法（效率最低）
直接在代码中说明，他们可以直接在程序中运行
//冒泡排序
@Test
public void testBublle(){
/**
* 冒泡排序的基本思路是：
*           从头开始扫描待排序的元素，在扫描过程中依次对相邻元素进行比较，
*          将关键字值大的元素后移。每经过一趟排序后，关键字值最大的元素将移到末尾，
*          此时记下该元素的位置，下一趟排序只需要比较到此位置为止，直到所有元素都已有序排列。
*         对n个元素进行冒泡排序，最好情况总共需要进行n-1趟，最差需要n(n-1)/2（求一个等差数列的和）。
*         Sn=(n-1)+(n-2)+……+1;N=n-1
* */
//定义整型数组
int num[]={12,23,22,3,53,18};
int temp;
for(int i=0;i<num.length-1;i++){
for(int j=0;j<num.length-i-1;j++){
//如果当前数大于下一个数，交换位置，即把大的数移到右边（升序排序，降序是：num[j]<num[j+1]）
if(num[j]>num[j+1]){
temp=num[j];
num[j]=num[j+1];
num[j+1]=temp;
}
}
System.out.print("第"+(i+1)+"次:");
//遍历比较后的数组
for(int k=0;k<num.length;k++){
System.out.print(num[k]+"\t");
}
System.out.println();
}
/**
* 打印结果：
* 第1次:12  22 3 23 18 53
* 第2次:12  3 22 18 23 53
* 第3次:3  12 18 22 23 53
* 第4次:3  12 18 22 23 53
* 第5次:3  12 18 22 23 53
*/
/**
* 本文只分析第一次的结果，以后的结果可以依次类推
* 第二层的for循环需要循环次数：6-i-1=6-0-1=5
* num[0]=12
*       (1) num[0]=12>num[1]=23  false
*         12,23,22,3,53,18
*       (2)num[1]=23>num[2]=22   true
*       12,22,23,3,53,18
*       (3)num[2]=23>num[3]=3     true
*       12,22,3,23,53,18
*       (4)num[3]=23>num[4]=53   false
*       12,22,3,23,53,18
*       (5)num[4]=53>num[5]=18    true
*              12,22,3,23,18,53
*   所以，第一次循环比较完成后的结果是：12，22，3，23，18，53
*/
}
二、选择排序法
实现代码、相关说明如下：
//选择排序
@Test
public void testChoice(){
/**
* 基本思想：
* 每一趟从待排序的数据元素中选出最小（或最大）的一个元素，
* 顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。
* 
* 排序次数：最少排序次数n-1次   ，Sn=(n-1)+(n-1)+(n-1)+……+(n-1)=n(n-1)
* 
* */
//定义整型数组
int num[]={12,23,22,3,53,18};
int temp;
//开始排序
for(int i=0;i<num.length-1;i++){
for(int j=i+1;j<num.length;j++){
//把最小的数放在左边，升序排序；降序：num[i]<num[j]
if(num[i]>num[j]){
temp=num[i];
num[i]=num[j];
num[j]=temp;
}
}
System.out.print("第"+(i+1)+"次：");
for(int k=0;k<num.length;k++){
System.out.print(num[k]+"\t");
}
System.out.println();
}
/**
* 打印结果：
 第1次： 3 23 22 12 53 18第2次： 3 12 23 22 53 18
第3次： 3 12 18 23 53 22
第4次： 3 12 18 22 53 23
第5次： 3 12 18 22 23 53
* 结果分析：本文只分析第一次循环比较，其余次数依次类推
* 第一次：
* num[0]=12
* (1)num[0]=12> num[0+1]=23   false
* 12,23,22,3,53,18
* (2)num[0]=12>num[0+2]=22    false
* 12,23,22,3,53,18
* (3)num[0]=12>num[0+3]=3      true
* 3,23,22,12,53,18
* (4)num[0]=12>num[0+4]=53false
* 3,23,22,12,53,18
* (5)num[0]=12>num[0+5]=18    false
* 3,23,22,12,53,18
* 所以，第一次比较后的结果是：3,23,22,12,53,18
* 
* */
}
三、集合排序法
//集合的排序方法
@Test
public void testList(){
//定义整型数组
Integer num[]={12,23,22,3,53,18};//也可以使用快速的方法：Arrays.sort(num); 
/**
 * 也可以将数组转换成为列表，此方法方便
 *  List<Integer> list = Arrays.asList(num);
 */
List<Integer> list=new ArrayList<Integer>();
list.add(num[0]);
list.add(num[1]);
list.add(num[2]);
list.add(num[3]);
list.add(num[4]);
list.add(num[5]);
//降序排序
Collections.sort(list,Collections.reverseOrder());
System.out.println("倒序排序结果："+list);
//升序排序
Collections.sort(list);
System.out.println("降序排序结果："+list);
/**
 *  打印结果：
 *            倒序排序结果：[53, 23, 22, 18, 12, 3]
 *            降序排序结果：[3, 12, 18, 22, 23, 53]
 *            
 * 注意：如果比较的泛型对象不是基本类型，那么需要在相应的泛型类中实现compareTo方法           
 */
} 

 

四、快速排序法效率最高(常用,后面有一节专讲快速排序)
@Test
public void testQuik(){
//新建数组
int[] num ={12,23,22,3,53,18};
//升序排序
    quickSort(num, 0, num.length - 1);  
     //变量结果
      for (int i = 0; i < num.length; i++) {  
           System.out.print(num[i] + "\t");  
       }  
}
/** 
      *  
     * @param array 
       * @param left 
       * @param right 
         */  
     public static void quickSort(int[] array, int left, int right) {  
         int pivotKey;  
         if (left < right) {  
             pivotKey = partitionByPivotValue(array, left, right);  
             // 对左右数组递归调用快速排序，直到顺序完全正确  
             quickSort(array, left, pivotKey - 1);  
             quickSort(array, pivotKey + 1, right);  
         }  
     }  
   
     /** 
      * pivotValue作为枢轴，较之小的元素排序后在其左，较之大的元素排序后在其右 
      *  
      * @param array 
      * @param left 
      * @param right 
      * @return 
      */  
     public static int partitionByPivotValue(int[] array, int left, int right) {  
         int pivotValue = array[left];  
         // 枢轴选定后永远不变，最终在中间，前小后大  
         while (left < right) {  
             while (left < right && array[right] >= pivotValue) {  
                 --right;  
             }  
             // 将比枢轴小的元素移到低端，此时right位相当于空，等待低位比pivotkey大的数补上  
             array[left] = array[right];  
             while (left < right && array[left] <= pivotValue) {  
                 ++left;  
             }  
             // 将比枢轴大的元素移到高端，此时left位相当于空，等待高位比pivotkey小的数补上  
             array[right] = array[left];  
         }  
         // 当left == right，完成一趟快速排序，此时left位相当于空，等待pivotkey补上  
         array[left] = pivotValue;  
         return left;  
     }  

相等长度的数组下所用时间：
快速排序>集合排序>选择排序>冒泡排序