java实现排序的一些方法，来自：

 

1 package sort;    2      3 import java.util.Random;    4      5 /**   6  * 排序测试类   7  *    8  * 排序算法的分类如下： 1.插入排序（直接插入排序、折半插入排序、希尔排序）； 2.交换排序（冒泡泡排序、快速排序）；   9  * 3.选择排序（直接选择排序、堆排序）； 4.归并排序； 5.基数排序。  10  *   11  * 关于排序方法的选择： (1)若n较小(如n≤50)，可采用直接插入或直接选择排序。  12  * 当记录规模较小时，直接插入排序较好；否则因为直接选择移动的记录数少于直接插人，应选直接选择排序为宜。  13  * (2)若文件初始状态基本有序(指正序)，则应选用直接插人、冒泡或随机的快速排序为宜；  14  * (3)若n较大，则应采用时间复杂度为O(nlgn)的排序方法：快速排序、堆排序或归并排序。  15  *   16  */  17 /**  18  * @corporation 北京环亚  19  * @author HDS  20  * @date Nov 19, 2009 10:43:44 AM  21  * @path sort  22  * @description JAVA排序汇总  23  */  24 public class SortTest {   25     26     // //==============================产生随机数==============================///   27     /**  28      * @description 生成随机数  29      * @date Nov 19, 2009  30      * @author HDS  31      * @return int[]  32      */  33     public int[] createArray() {   34         Random random = new Random();   35         int[] array = new int[10];   36         for (int i = 0; i < 10; i++) {   37             array[i] = random.nextInt(100) - random.nextInt(100);// 生成两个随机数相减，保证生成的数中有负数   38         }   39         System.out.println("==========原始序列==========");   40         printArray(array);   41         return array;   42     }   43     44     /**  45      * @description 打印出随机数  46      * @date Nov 19, 2009  47      * @author HDS  48      * @param data  49      */  50     public void printArray(int[] data) {   51         for (int i : data) {   52             System.out.print(i + " ");   53         }   54         System.out.println();   55     }   56     57     /**  58      * @description 交换相邻两个数  59      * @date Nov 19, 2009  60      * @author HDS  61      * @param data  62      * @param x  63      * @param y  64      */  65     public void swap(int[] data, int x, int y) {   66         int temp = data[x];   67         data[x] = data[y];   68         data[y] = temp;   69     }   70     71     /**  72      * 冒泡排序----交换排序的一种  73      * 方法：相邻两元素进行比较，如有需要则进行交换，每完成一次循环就将最大元素排在最后（如从小到大排序），下一次循环是将其他的数进行类似操作。  74      * 性能：比较次数O(n^2),n^2/2；交换次数O(n^2),n^2/4  75      *   76      * @param data  77      *            要排序的数组  78      * @param sortType  79      *            排序类型  80      * @return  81      */  82     public void bubbleSort(int[] data, String sortType) {   83         if (sortType.equals("asc")) { // 正排序，从小排到大   84             // 比较的轮数   85             for (int i = 1; i < data.length; i++) { // 数组有多长,轮数就有多长   86                 // 将相邻两个数进行比较，较大的数往后冒泡   87                 for (int j = 0; j < data.length - i; j++) {
   // 每一轮下来会将比较的次数减少   88                     if (data[j] > data[j + 1]) {   89                         // 交换相邻两个数   90                         swap(data, j, j + 1);   91                     }   92                 }   93             }   94         } else if (sortType.equals("desc")) { // 倒排序，从大排到小   95             // 比较的轮数   96             for (int i = 1; i < data.length; i++) {   97                 // 将相邻两个数进行比较，较大的数往后冒泡   98                 for (int j = 0; j < data.length - i; j++) {   99                     if (data[j] < data[j + 1]) {  100                         // 交换相邻两个数  101                         swap(data, j, j + 1);  102                     }  103                 }  104             }  105         } else {  106             System.out.println("您输入的排序类型错误！");  107         }  108         printArray(data);// 输出冒泡排序后的数组值  109     }  110    111     /** 112      * 直接选择排序法----选择排序的一种 方法：每一趟从待排序的数据元素中选出最小（或最大）的一个元素， 113      * 顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。 性能：比较次数O(n^2),n^2/2 交换次数O(n),n 114      * 交换次数比冒泡排序少多了，由于交换所需CPU时间比比较所需的CUP时间多，所以选择排序比冒泡排序快。 115      * 但是N比较大时，比较所需的CPU时间占主要地位，所以这时的性能和冒泡排序差不太多，但毫无疑问肯定要快些。 116      *  117      * @param data 118      *            要排序的数组 119      * @param sortType 120      *            排序类型 121      * @return 122      */ 123     public void selectSort(int[] data, String sortType) {  124         if (sortType.endsWith("asc")) {
   // 正排序，从小排到大  125             int index;  126             for (int i = 1; i < data.length; i++) {  127                 index = 0;  128                 for (int j = 1; j <= data.length - i; j++) {  129                     if (data[j] > data[index]) {  130                         index = j;  131                     }  132                 }  133                 // 交换在位置data.length-i和index(最大值)两个数  134                 swap(data, data.length - i, index);  135             }  136         } else if (sortType.equals("desc")) { // 倒排序，从大排到小  137             int index;  138             for (int i = 1; i < data.length; i++) {  139                 index = 0;  140                 for (int j = 1; j <= data.length - i; j++) {  141                     if (data[j] < data[index]) {  142                         index = j;  143                     }  144                 }  145                 // 交换在位置data.length-i和index(最大值)两个数  146                 swap(data, data.length - i, index);  147             }  148         } else {  149             System.out.println("您输入的排序类型错误！");  150         }  151         printArray(data);// 输出直接选择排序后的数组值  152     }  153    154     /** 155      * 插入排序 方法：将一个记录插入到已排好序的有序表（有可能是空表）中,从而得到一个新的记录数增1的有序表。 性能：比较次数O(n^2),n^2/4 156      * 复制次数O(n),n^2/4 比较次数是前两者的一般，而复制所需的CPU时间较交换少，所以性能上比冒泡排序提高一倍多，而比选择排序也要快。 157      *  158      * @param data 159      *            要排序的数组 160      * @param sortType 161      *            排序类型 162      */ 163     public void insertSort(int[] data, String sortType) {  164         if (sortType.equals("asc")) { // 正排序，从小排到大  165             // 比较的轮数  166             for (int i = 1; i < data.length; i++) {  167                 // 保证前i+1个数排好序  168                 for (int j = 0; j < i; j++) {  169                     if (data[j] > data[i]) {  170                         // 交换在位置j和i两个数  171                         swap(data, i, j);  172                     }  173                 }  174             }  175         } else if (sortType.equals("desc")) { // 倒排序，从大排到小  176             // 比较的轮数  177             for (int i = 1; i < data.length; i++) {  178                 // 保证前i+1个数排好序  179                 for (int j = 0; j < i; j++) {  180                     if (data[j] < data[i]) {  181                         // 交换在位置j和i两个数  182                         swap(data, i, j);  183                     }  184                 }  185             }  186         } else {  187             System.out.println("您输入的排序类型错误！");  188         }  189         printArray(data);// 输出插入排序后的数组值  190     }  191    192     /** 193      * 反转数组的方法 194      *  195      * @param data 196      *            源数组 197      */ 198     public void reverse(int[] data) {  199         int length = data.length;  200         int temp = 0;// 临时变量  201         for (int i = 0; i < length / 2; i++) {  202             temp = data[i];  203             data[i] = data[length - 1 - i];  204             data[length - 1 - i] = temp;  205         }  206         printArray(data);// 输出到转后数组的值  207     }  208    209     /** 210      * 快速排序 快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。 步骤为： 211      * 1. 从数列中挑出一个元素，称为 "基准"（pivot）， 2. 212      * 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分割之后，该基准是它的最后位置。这个称为分割（partition）操作。 213      * 3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。 214      * 递回的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递回下去，但是这个算法总会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。 215      *  216      * @param data 217      *            待排序的数组 218      * @param low 219      * @param high 220      * @see SortTest#qsort(int[], int, int) 221      * @see SortTest#qsort_desc(int[], int, int) 222      */ 223     public void quickSort(int[] data, String sortType) {  224         if (sortType.equals("asc")) { // 正排序，从小排到大  225             qsort_asc(data, 0, data.length - 1);  226         } else if (sortType.equals("desc")) { // 倒排序，从大排到小  227             qsort_desc(data, 0, data.length - 1);  228         } else {  229             System.out.println("您输入的排序类型错误！");  230         }  231     }  232    233     /** 234      * 快速排序的具体实现，排正序 235      *  236      * @param data 237      * @param low 238      * @param high 239      */ 240     private void qsort_asc(int data[], int low, int high) {  241         int i, j, x;  242         if (low < high) { // 这个条件用来结束递归  243             i = low;  244             j = high;  245             x = data[i];  246             while (i < j) {  247                 while (i < j && data[j] > x) {  248                     j--; // 从右向左找第一个小于x的数  249                 }  250                 if (i < j) {  251                     data[i] = data[j];  252                     i++;  253                 }  254                 while (i < j && data[i] < x) {  255                     i++; // 从左向右找第一个大于x的数  256                 }  257                 if (i < j) {  258                     data[j] = data[i];  259                     j--;  260                 }  261             }  262             data[i] = x;  263             qsort_asc(data, low, i - 1);  264             qsort_asc(data, i + 1, high);  265         }  266     }  267    268     /** 269      * 快速排序的具体实现，排倒序 270      *  271      * @param data 272      * @param low 273      * @param high 274      */ 275     private void qsort_desc(int data[], int low, int high) {  276         int i, j, x;  277         if (low < high) { // 这个条件用来结束递归  278             i = low;  279             j = high;  280             x = data[i];  281             while (i < j) {  282                 while (i < j && data[j] < x) {  283                     j--; // 从右向左找第一个小于x的数  284                 }  285                 if (i < j) {  286                     data[i] = data[j];  287                     i++;  288                 }  289                 while (i < j && data[i] > x) {  290                     i++; // 从左向右找第一个大于x的数  291                 }  292                 if (i < j) {  293                     data[j] = data[i];  294                     j--;  295                 }  296             }  297             data[i] = x;  298             qsort_desc(data, low, i - 1);  299             qsort_desc(data, i + 1, high);  300         }  301     }  302    303     /** 304      * 二分查找特定整数在整型数组中的位置(递归) 查找线性表必须是有序列表 305      *  306      * @paramdataset 307      * @paramdata 308      * @parambeginIndex 309      * @paramendIndex 310      * @returnindex 311      */ 312     public int binarySearch(int[] dataset, int data, int beginIndex,  313             int endIndex) {  314         int midIndex = (beginIndex + endIndex) >>> 1; // 相当于mid = (low + high)  315                                                         // / 2，但是效率会高些  316         if (data < dataset[beginIndex] || data > dataset[endIndex]  317                 || beginIndex > endIndex)  318             return -1;  319         if (data < dataset[midIndex]) {  320             return binarySearch(dataset, data, beginIndex, midIndex - 1);  321         } else if (data > dataset[midIndex]) {  322             return binarySearch(dataset, data, midIndex + 1, endIndex);  323         } else {  324             return midIndex;  325         }  326     }  327    328     /** 329      * 二分查找特定整数在整型数组中的位置(非递归) 查找线性表必须是有序列表 330      *  331      * @paramdataset 332      * @paramdata 333      * @returnindex 334      */ 335     public int binarySearch(int[] dataset, int data) {  336         int beginIndex = 0;  337         int endIndex = dataset.length - 1;  338         int midIndex = -1;  339         if (data < dataset[beginIndex] || data > dataset[endIndex]  340                 || beginIndex > endIndex)  341             return -1;  342         while (beginIndex <= endIndex) {  343             midIndex = (beginIndex + endIndex) >>> 1; // 相当于midIndex =  344                                                         // (beginIndex +  345                                                         // endIndex) / 2，但是效率会高些  346             if (data < dataset[midIndex]) {  347                 endIndex = midIndex - 1;  348             } else if (data > dataset[midIndex]) {  349                 beginIndex = midIndex + 1;  350             } else {  351                 return midIndex;  352             }  353         }  354         return -1;  355     }  356    357     // /===================================测试====================//  358     public static void main(String[] args) {  359         SortTest ST = new SortTest();  360         int[] array = ST.createArray();  361         System.out.println("==========冒泡排序后(正序)==========");  362         ST.bubbleSort(array, "asc");  363         System.out.println("==========冒泡排序后(倒序)==========");  364         ST.bubbleSort(array, "desc");  365    366         array = ST.createArray();  367         System.out.println("==========选择排序后(正序)==========");  368         ST.selectSort(array, "asc");  369         System.out.println("==========选择排序后(倒序)==========");  370         ST.selectSort(array, "desc");  371            372         array = ST.createArray();  373         System.out.println("==========插入排序后(正序)==========");  374         ST.insertSort(array, "asc");  375         System.out.println("==========插入排序后(倒序)==========");  376         ST.insertSort(array, "desc");  377    378         array = ST.createArray();  379         System.out.println("==========快速排序后(正序)==========");  380         ST.quickSort(array, "asc");  381         ST.printArray(array);  382         System.out.println("==========快速排序后(倒序)==========");  383         ST.quickSort(array, "desc");  384         ST.printArray(array);  385         System.out.println("==========数组二分查找==========");  386         System.out.println("您要找的数在第" + ST.binarySearch(array, 74)+ "个位子。（下标从0计算）");  387    388     }  389    390 }