1 package sorting;  2   3 import java.util.*;  4 //import java.util.Comparator;  5 //import java.util.PriorityQueue;  6 //import java.util.Queue;  7   8 public class Sorting {  9     /************************************序言**********************************************/ 10     /** 11      * 排序方法：冒泡排序，插入排序，希尔排序，堆排序(2)，归并排序(2)，快排(2)... 12      * */ 13      14     /** 15      * 最小值函数 16      * */ 17     private static <AnyType extends Comparable<? super AnyType>> AnyType min(AnyType a, AnyType b){ 18         if(a.compareTo(b) <= 0) 19             return a; 20         else  21             return b; 22     } 23      24     /** 25      * 交换函数 26      * */ 27     private static <AnyType extends Comparable<? super AnyType>> void swap(AnyType [] a, int m, int n){ 28         AnyType tmp = a[n]; 29         a[n] = a[m]; 30         a[m] = tmp;         31     } 32     /**********************************BubleSort*****************************************/ 33     /** 34      * 冒泡排序：BubleSort 35      * 每次内层循环最大的都被滤到最后 36      * */ 37     public static <AnyType extends Comparable<? super AnyType>> void bubleSort(AnyType [] a){ 38         for(int i=0;i<a.length;i++){   39             for(int j=0;j<a.length-1-i;j++){   40                 if(a[j].compareTo(a[j+1]) > 0){   //如果后一个数小于前一个数交换   41                     AnyType tmp=a[j];   42                     a[j]=a[j+1];   43                     a[j+1]=tmp;   44                 }   45             }   46         }              47     } 48     /*************************SelectSort*************************************************/ 49     /*** 50      * 选择排序：SelectSort 51      * 每次内层循环最小的被滤到最前 52      */ 53      public static <AnyType extends Comparable<? super AnyType>> void selectSort(AnyType[] a) { 54             int minIndex;      55             for (int i = 0; i < a.length; i++) { 56                 minIndex = i;                 57                 for (int j = i + 1; j < a.length; j++) {                    58                     if ((a[j].compareTo(a[minIndex])) < 0) { 59                         minIndex = j; 60                     } 61                 }                 62                 swap(a, i, minIndex); 63             } 64         } 65  66     /*************************InsertionSort**********************************************/     67     /*** 68      * 插入排序：InsertionSort  69      * @param a 70      * 插入排序的实质是从a[1]~a[a.length-1]开始，逐个比较a[p]（p=1,2,...,a.length-1）与a[j-1]的值，直至找到a[p]的位置。 71      */      72     public static <AnyType extends Comparable<? super AnyType>> void insertionSort(AnyType [] a){ 73         int j; 74         for(int p = 1; p < a.length; p++){ 75             AnyType tmp = a[p]; //务必使用tmp变量，否则可能第一轮比较过后啊a[p]也即a[j]的值被覆盖 76             for(j = p; j > 0 && tmp.compareTo(a[j - 1])<0;j--){//等于就不挪了，省一次操作 77                 a[j] = a[j-1]; 78             } 79             a[j] = tmp; 80              81         } 82     } 83     /*************************ShellSort**********************************************/ 84     /** 85      * 希尔排序：ShellSort 最坏情形:O(N2) 86      * @param a 87      * 希尔排序（即间隔排序）的作用：对于间隔k，希尔排序即对k个独立的子数组的一次插入排序 88      */ 89     public static <AnyType extends Comparable<? super AnyType>> void shellSort(AnyType [] a){ 90         int j; 91         for(int gap = a.length / 2; gap > 0; gap /= 2 ){ 92             //同时对k个子数组进行间隔排序，相当于和并单独子数组排序的两个for循环 for(int i=0;i<gap;i++){for(int p=i;i<a.length;p+=gap){}} 93             for(int i = gap;i < a.length;i++){ 94                 //每个子数组的插入排序 95                 AnyType tmp = a[i]; 96                 for(j = i;j >= gap && tmp.compareTo(a[j-gap])<0;j-=gap){//等于就不挪了，省一次操作 97                     a[j] = a[j-gap]; 98                 } 99                 a[j] = tmp;100             }101         }102     }103     /*************************HeapSort**********************************************/104     /**105      * 堆排序：HeapSort1   最坏情形:O(Nlog(N)) 堆排序要比希尔排序要慢106      * @param a107      * 堆排序使用优先队列java.util.PriorityQueue实现108      */        109     public static <AnyType extends Comparable<? super AnyType>> void heapSort1(AnyType [] a){110         Comparator<AnyType> comparator = new Comparator<AnyType>(){111             public int compare(AnyType left, AnyType right){112                 return left.compareTo(right) ;113              }114         };115         Queue<AnyType> heap = new PriorityQueue<AnyType>(a.length,comparator);116         for(AnyType e:a){117             heap.add(e);118         }119         int i = 0;120         while(!heap.isEmpty()){121             a[i++] = heap.poll();122         }        123     }124     /****************************************************************************************/125     /**126      * 堆排序：HeapSort2 最坏情形:O(Nlog(N))127      * @param a128      * 使用基础代码实现，建堆，排序129      */130     /**131      * 求左子节点132      * */133     private static int leftChild(int i){134         return 2 * i + 1;135     }136     /**137      * 下滤函数：deleteMin(deleteMax)时候使用138      * 对于大根堆下滤期间，大数被逐次滤上去（一步一步），小数被一直滤到它该到的位置（for结束后）139      * @param a 堆数组140      * @param i 开始下滤的起点141      * @param n 堆的有效数组长度，随着不断deleteMax操作，堆中元素会不断减少，有效数组长度n也会逐渐减小142      */143      private static <AnyType extends Comparable<? super AnyType>> void percolateDown(AnyType[] a, int i, int n){144          int child;//左右子中较小的那个节点145          AnyType tmp = a[i];146          147          for(; leftChild(i)< n; i = child){//leftChild(i)< n 判断是否到达最后一个叶子节点148              child = leftChild(i);149              //如果只有一个左子节点，那么不必判断那个更大了150              if(child != n-1 && a[child].compareTo( a[child + 1] ) < 0)//child!=n-1为了确定是否有两个子节点151                  child++;//将两个儿子中大的那个滤上去152              if(tmp.compareTo( a[child]) < 0 ){//等于就不挪了，省一次操作153                  a[i]=a[child];//大数被逐次滤上去（一步一步）154              }else155                  break;156          }157          a[i]=tmp;//小数被for一直滤下来         158      }159 160     /**161      * 排序结果：升序 ，使用大根堆162      * 建立大根堆，deleteMin操作，得到排序数组163      * 下虑操作：在建立二叉堆和deleteMin中都有使用164      * */165     public static <AnyType extends Comparable<? super AnyType>> void heapSort2(AnyType [] a){166         /*  在无序数组上直接下滤建立大根堆167          *  从低向上开始下滤，即最后一个节点的父节点下滤即a[length/2]168          *  堆从数组索引0开始，因此左子节点为2*i+1,右子节点为2*i+2  169          *  */170         for(int i = a.length/2; i >= 0; i--){171             percolateDown(a, i, a.length);172         }173         /*  堆排序：不断deleteMax将堆中最大的元素放置于数组a的末端174          *  */175         for(int j = a.length-1; j >= 0; j--){176             //deleteMax177             AnyType tmp = a[j];178             a[j] = a[0];179             //将队尾元素放置堆根处，开始下滤180             a[0] = tmp;181             percolateDown(a, 0, j);//初始时刻j为a.length-1182         }183     }184     /*************************MergeSort**********************************************/185     /**186      * 归并排序：MergeSort1  最坏运行时间O(Nlog(N)) 对空间有要求，线性内存    比较次数最少187      * 注意： 归并排序严重依赖于比较元素和数组中移动元素的相对开销，是语言相关的。188      *               其中：java中，执行一次泛型排序（Comparator）时 ，比较（不容易内嵌，动态调度）的的开销要大于移动元素（引用赋值）；由于比较次数最少，是标准java类库中泛型排序所使用的算法。189      *     而 C++则相反，其泛型排序中如果对象庞大，拷贝对象开销大，比较相对省时。C++库中使用快速排序方法。190      * @param a191      * 实现方式：递归，本质就是一直讲待排序的数组二分下去，直至每一半均只有一个元素然后依次合并，完成排序。192      * */193     194     /**195      * 实际完成归并排序的过程的程序196      * */197     private static <AnyType extends Comparable<? super AnyType>> void merge(AnyType [] a, AnyType [] tmpArray, int leftPos, int rightPos, int rightEnd){198         int leftEnd = rightPos - 1;199         int tmpPos = leftPos;200         int numElements = rightEnd - leftPos + 1;201         202         while(leftPos <= leftEnd && rightPos <= rightEnd){203             if(a[leftPos].compareTo(a[rightPos]) <= 0)//等不等于都得拷贝204                 tmpArray[tmpPos++] = a[leftPos++];205             else206                 tmpArray[tmpPos++] = a[rightPos++];207         }        208         while(leftPos <= leftEnd){209             tmpArray[tmpPos++] = a[leftPos++];210         }211         while(rightPos <= rightEnd){212             tmpArray[tmpPos++] = a[rightPos++];213         }214         for(int i = numElements; i >0; i--){215             a[rightEnd] = tmpArray[rightEnd];216             rightEnd--;//注意rightEnd要单独拿出来自减，否则在上个语句中会自减两次217         }218     }219     220     /**221      * 主递归程序222      * */223     private static <AnyType extends Comparable<? super AnyType>> void mergeSort(AnyType [] a, AnyType [] tmpArray, int left, int right){224         if(left < right){225             int center = (left + right)/2;226             mergeSort(a, tmpArray, left, center);227             mergeSort(a, tmpArray, center + 1, right);228             merge(a, tmpArray, left, center + 1, right);//实际完成排序过程229         }230     }231     232     /**233      * 归并排序驱动程序234      * */235     public static <AnyType extends Comparable<? super AnyType>> void MergeSort1(AnyType [] a){236         AnyType [] tmpArray = (AnyType[]) new Comparable[a.length];237         mergeSort(a, tmpArray, 0, a.length - 1);238     }    239     240     /********************************************************************************/241     /**242      * 归并排序：MergeSort2  最坏运行时间O(Nlog(N))243      * @param a244      * 实现方式：非递归，从单个元素开始归并合成小组，然后小组之间归并直至归并成一个完整的数组，依旧使用MergeSort1使用的merge函数245      * */    246     public static <AnyType extends Comparable<? super AnyType>> void MergeSort2(AnyType [] a){247         int n = a.length;248         AnyType[] tmpArray = (AnyType[]) new Comparable[n]; 249         for(int subList = 1; subList < n; subList *=2){250             int leftPos = 0;251             while(leftPos + subList < n){252                 int rightPos = leftPos + subList;253 //                int leftEnd = rightPos - 1;254                 int rightEnd = min(n-1, rightPos + subList - 1); //一定要注意不能越界 min255                 merge(a, tmpArray, leftPos, rightPos, rightEnd);256                 leftPos = rightEnd + 1;  //等同于leftPos += 2 * subList;                257             }258         }259     }260     /*************************QuickSort**********************************************/261     /**262      * 快速排序：QuickSort1  平均运行时间：O(NlogN) 最坏运行时间：O(N2)263      * 使用三数中值分割法选取枢纽元264      * 由于对于小数组（N<=20），快速排序的递归会不如插入排序，因此该程序调用插入排序函数。截止范围CUTOFF=10265      * */266     private static final int CUTOFF = 10;267     268     /**269      * 三数中值分割法：取左端，右端，中心位置的三个元素的中值作为枢纽元270      * 排序后最小的将位于a[left]，最大的位于a[right]，枢纽元即中间值a[center]将被放置于a[right-1](亦即交换a[center]与a[right-1])271      * 这样在分隔阶段，i,j将从left+1和right-2开始比较272      * 三数中值分割法的好处：a[left]比枢纽元小，将作为j的警戒标记；而a[right-1]存放着枢纽元，则自然作为i的警戒标记。273      * */274     private static <AnyType extends Comparable<? super AnyType>> AnyType median3(AnyType [] a, int left, int right){275         int center = (left +  right)/2;276         if(a[center].compareTo(a[left]) < 0)277             swap(a, center, left);278         if(a[right].compareTo(a[left]) < 0)279             swap(a, right, left);280         if(a[right].compareTo(a[center]) < 0)281             swap(a, right, center);282         //将枢纽元至于a[right - 1]的位置上283         swap(a, center, right - 1);284         return a[right - 1];        285     }286     /**287      * 快速排序递归程序，主体程序，遇到跟pivot枢纽元值相等的值要停下288      * */289     private static <AnyType extends Comparable<? super AnyType>> void quickSort(AnyType [] a, int left, int right){290         //利用截止范围判断数据量291         if(left + CUTOFF <= right){292             //获取枢纽元293             AnyType pivot = median3(a, left, right);294             //由于pivot放置在了a[right - 1]的位置(暂存pivot)，因此i,j的取值应该为 left + 1，和right - 2295             int i = left, j = right - 1;296             for(;;){297                 //在遇到i,j处值都等于pivot时候停下，但是还得继续道，j<i才算结束，因此while编写要格外注意298                 while(a[++i].compareTo(pivot) < 0){}//遇到跟pivot枢纽元值相等的值要停下,否则N2效率低下299                 while(a[--j].compareTo(pivot) > 0){}300                 if(i < j)301                     swap(a, i, j);302                 else303                     break;                304             }305 //            for(;;){306 //                while(a[i].compareTo(pivot) < 0){i++;}307 //                while(a[j].compareTo(pivot) > 0){j--;}308 //                if(i < j){309 //                    swap(a, i, j);310 //                    i++;j--;311 //                }312 //                else313 //                    break;                314 //            }315             //因为i左边都比pivot小，i及i右边除了right-1除存放着pivot外都比pivot大，因此将i处值与right-1处值交换316             //即得到i左边都比其小，右边都比其大，i即pivot排序好的正确位置（换回pivot）317             swap(a, i, right - 1);318             //i已排好序319             quickSort(a, left, i - 1);320             quickSort(a, i + 1, right);321         }else322             insertionSort(a);323     }324     /**325      * 快速排序驱动程序326      * */327     public static <AnyType extends Comparable<? super AnyType>> void QuickSort(AnyType [] a){328         quickSort(a, 0, a.length - 1);329     }330     331     /*********************************QuickSort2***************************************/332     /**333      * 使用数组第一位作为枢纽元334      * */335     private static <AnyType extends Comparable<? super AnyType>> void quickSort2(AnyType [] a, int start, int end){336         if(start < end){337             int i = start, j = end;338             AnyType base = a[start];            339             while(i < j ){340                 while((a[j].compareTo(base) > 0) && (j > i))341                     j--;342                 if(i < j){343                     a[i] = a[j];344                     i++;//345                 }346                 while((a[i].compareTo(base) < 0) && (i < j))347                     i++;348                 if(i < j){349                     a[j] = a[i];350                     j--;//351                 }            352                         353             }//while354             a[i] = base;355             356             quickSort2(a, start, i-1);357             quickSort2(a, i+1, end);358         }359         360     }361     /**362      * 驱动程序363      * 使用数组第一位作为枢纽元364      * */365     public static <AnyType extends Comparable<? super AnyType>> void QuickSort2(AnyType [] a){366         quickSort2(a, 0, a.length-1);367     }368     /*********************************QuickSort3***************************************/369     /**370      * 使用非递归的快速排序371      * */372     public static <AnyType extends Comparable<? super AnyType>> void QuickSort3(AnyType [] a){373         374     }375     376 377     /*-----------------------------------------main-------------------------------------------------*/378     public static void main(String[] args) {379         // TODO Auto-generated method stub380         /**381          * Test case: Sort the array.382          * */        383 //        Integer[] a ={3,1,4,1,5,9,2,6,142,543,123,65,453,879,572,434,111,242,811,102};384         Integer[] a ={3,1,4,1,5,9,2,6};385         System.out.println("Before sorting:");386         for(Integer i:a){387             System.out.print(i+",");388         }389         System.out.println();390         391         Sorting.selectSort(a);//排序方法调用392         System.out.println("After sorting:");393         for(Integer i:a){394             System.out.print(i+",");395         }396         System.out.println();397 398         399     }400 401 }