1 package com.gxf.sort; 2  3 /** 4  * 将关键字封装一下 5  * @author xiangfei 6  * 7  */ 8 public class Rec { 9     int key;10     11     public Rec(int key){12         this.key = key;13     }14     public Rec(){15         16     }17     18     /**19      * 根据整型数组构造一个Rec[]数组20      * @param array21      * @return22      */23     public Rec[] getRecArray(int array[]){24         Rec rec[] = new Rec[array.length];25         for(int i = 0; i < array.length; i++){26             rec[i] = new Rec(array[i]);27         }28         29         return rec;30     }31 }

 1 package com.gxf.sort; 2  3 /** 4  * 排序类 5  * 这里主要实现三类简单的排序算法 6  * 直接插入排序、交换排序和选择排序中的 7  * 直接插入排序、冒泡排序和直接选择排序 8  * @author xiangfei 9  *10  */11 public class Sort {12     /**13      * 直接插入排序算法14      * 将后面的元素插入到前面的有序队列中n - 1趟15      * 每一趟需要将比rec[i].key更大的元素后移，找出合适的位置16      * 这里第一个元素不放值，用于暂存17      * 开始将第一个元素作为有序队列18      * @param rec19      */20     public void insSort(Rec rec[]){21         //rec[0]不放值22         for(int i = 1; i < rec.length;i++){23             int value = http://www.mamicode.com/rec[i].key;//需要插入的元素24             rec[0].key = rec[i].key;//这里需要保存要插入的元素，后面移动元素会覆盖25             int j = i - 1;26             while(value < rec[j].key){//后移元素，找到比value小或者等于的27                 rec[j + 1].key = rec[j].key;28                 j--;//前移29             }//j为比rec[i]小或者等于的元素的位置30             rec[j + 1].key = rec[0].key;//插入，完成一趟插入31         }32         //排完序后第一个元素置为033         rec[0].key = 0;34     }35     36     /**37      * 冒泡排序38      * 每一趟比较两个相邻元素的大小，大的元素往后移动，最大的元素移动到最后39      * 这样最多需要n - 1趟40      * 如果有正序的则不用排序，需要设置一个标志位，表明是否有交换41      * @param rec42      */43     public void bubbSort(Rec rec[]){44         boolean flag_exchange = false;//默认没有交换45         //这里至少需要n - 1趟46         for(int i = 0; i < rec.length - 1; i++){47             flag_exchange = false;//重置标志位没有交换48             for(int j = 0; j < rec.length - i - 1; j++){//每一趟的排序，范围逐渐缩小49                 if(rec[j].key > rec[j + 1].key){//前一个元素比后一个元素大，需要交换50                     Rec temp = rec[j];51                     rec[j] = rec[j + 1];52                     rec[j + 1] = temp;//交换53                     flag_exchange = true;//设置有交换54                 }                55             }56             if(!flag_exchange)57                 break;//没有交换，说明已经是正序，退出58         }59     }60     61     /**62      * 直接选择排序63      * 每次选出最小的放到最前面，需要n - 1趟64      * 每一趟从剩下的元素中选出最小的，放到最前面65      * @param rec66      */67     public void seleSort(Rec rec[]){68         //需要n - 1趟排序69         for(int i = 0; i < rec.length - 1;i++){70             int min = i;//最小值的下标，默认为第一个元素71             //从i ~ n - 1中找出最小的一个元素下标72             for(int j = i; j < rec.length; j++){73                 if(rec[j].key < rec[min].key)74                     min = j;//更新最小元素的下标75             }//找出最小元素的下标76             if(i != min){//如果最小元素不是第一个元素交换77                 Rec temp = rec[min];78                 rec[min] = rec[i];79                 rec[i] = temp;80             }//交换完成81         }82     }83     84     /**85      * 这里用一个方法来show数组里面的内容，看一下排序是否正确86      * @param rec87      */88     public void showRec(Rec rec[]){89         for(int i = 0; i < rec.length; i++){90             System.out.print(rec[i].key + " ");91         }92         System.out.println();93     }94 95 }

package com.gxf.sort;public class Test {    public static void main(String args[]){        Sort sort = new Sort();        Rec rec = new Rec();        int array[] = new int[]{0, 32, 1, 34, 54, 5, 6};        Rec array_test[] = rec.getRecArray(array);        System.out.println("直接插入排序:");        sort.showRec(array_test);//print org        sort.insSort(array_test);        sort.showRec(array_test);//print changed        System.out.println("冒泡排序:");        //bubblesort        array_test = rec.getRecArray(array);        sort.showRec(array_test);//print org        sort.bubbSort(array_test);        sort.showRec(array_test);//print changed        System.out.println("直接选择排序：");        //select        array_test = rec.getRecArray(array);        sort.showRec(array_test);//print org        sort.seleSort(array_test);        sort.showRec(array_test);//print changed                        }}