你的位置:首页 > Java教程

[Java教程]java数据结构之排序


排序是我们在程序中经常要用到的一种算法,好的排序可以极大的提高我们的工作效率,本篇主要介绍几种常见的排序算法;(未完待续)

1、冒泡排序:

2、选择排序:

3、插入排序:

4、希尔排序:

 

 

 1 package cn.Link; 2  3 public class Sort{ 4   //测试主函数 5   public static void main(String[] args){ 6     int n = 20;     //数组长度 7     int[] num = new int[n];   //要排序的数组 8     num[0] = 0;       //数组首位不进行排序操作,仅作为临时变量或者是哨兵 9     for(int i = 1; i < n; i ++){ 10       num[i] = (int)(Math.random()*100); //随机生成一个数作为数组元素 11     } 12  13     System.out.println("排序前的数组:"); 14     Print_num(num); 15  16     //冒泡排序1 17     int[] num_1 = (int[]) num.clone(); 18     BubbleSort_1(num_1); 19     System.out.print("\n冒泡排序1排序后的结果"); 20     Print_num(num_1); 21  22     //冒泡排序2 23     int[] num_2 = (int[]) num.clone(); 24     BubbleSort_2(num_2); 25     System.out.print("\n冒泡排序2排序后的结果:"); 26     Print_num(num_2); 27  28     //冒泡排序3 对冒泡排序2的优化 29     int[] num_3 = (int[]) num.clone(); 30     BubbleSort_3(num_3); 31     System.out.print("\n冒泡排序3排序后的结果:"); 32     Print_num(num_3); 33  34     //选择排序 35     int[] num_4 = (int[]) num.clone(); 36     SelectSort(num_4); 37     System.out.print("\n选择排序排序后的结果:"); 38     Print_num(num_4); 39  40     //插入排序 41     int[] num_5 = (int[])num.clone(); 42     InsertSort(num_5); 43     System.out.print("\n插入排序排序后的结果"); 44     Print_num(num_5); 45      46     //希尔排序 47     int[] num_6 = (int[])num.clone(); 48     InsertSort(num_6); 49     System.out.print("\n希尔排序排序后的结果"); 50     Print_num(num_6); 51   } 52  53   //交换数组中的两个数 54   public static void Swap(int[]num,int i,int j){ 55     int num_x; 56     num_x = num[i]; 57     num[i] = num[j]; 58     num[j] = num_x; 59   } 60  61   //遍历输出一个数组 62   public static void Print_num(int[] num){ 63     System.out.println(); 64     for(int u:num){ 65       System.out.print(u+" "); 66     } 67   } 68  69   //冒泡排序1 最简单的两两比较,反序则交换的排序 70   public static void BubbleSort_1(int[]num){ 71     for(int i = 1; i < num.length; i++){ 72       for(int j = i+1; j < num.length; j++){ 73         if(num[i] > num[j]){ 74           Swap(num,i,j); 75         } 76       } 77     } 78   } 79  80   //冒泡排序2 最正宗的冒泡排序,i每循环一次,最小的数就像气泡一样慢慢浮到水面上 81   public static void BubbleSort_2(int[] num){ 82     for(int i = 1; i < num.length; i++){ 83       for(int j = num.length-1; j > i; j--){ 84         if(num[j-1] > num[j]){ 85           Swap(num,j-1,j); 86         } 87       } 88     } 89   } 90  91   //冒泡排序3 对冒泡排序的优化 92   public static void BubbleSort_3(int[] num){ 93     boolean flag = true; 94     for(int i = 1; i < num.length && flag; i++){ 95       flag = false;          //flag初始化为假 96       for(int j = num.length-1; j>i ; j--){ 97         if(num[j-1] > num[j]){ 98           Swap(num,j-1,j); 99           flag = true;100         }101       }102     }103   }104 105   //选择排序106   public static void SelectSort(int[] num){107     int min;108     for(int i = 1; i < num.length; i++){109       min = i;110       for(int j = i + 1; j <num.length; j++){111         if(num[min] > num[j]){112           min = j;113         }114       }115       if(i != min){116         Swap(num,i,min);117       }118     }119   }120 121   //插入排序122   public static void InsertSort(int[] num){123     int j;               124     for(int i = 2; i < num.length; i++){125       if(num[i] < num[i-1]){126         num[0] = num[i];127         for( j = i-1; num[j] > num[0]; j--){128           num[j+1] = num[j];     //记录右移129         }130         num[j+1] = num[0]; //插入到正确位置131         num[0] = 0;     //把num[0] 置为0,还回到初始值132       }133     }134 135   }136   //希尔排序137   public static void ShellSort(int[] num){138     int n = num.length; 139     int j;140     do{141       n = n/3 + 1;142       for(int i = n; i < num.length; i++){143         if(num[i] < num[i-n]){     //需要将num[i]插入到有序增量子表中144           num[0] = num[i];145           for(j = i - n; j > 0 && num[0] < num[j];j = n){146             num[j+n] = num[j];147           }148           num[j+n] = num[0];149         }150       }151     }while(n > 1);152   }153 }