1 /**  2  *   3  * @author yuzhiping  4  * @version 1.0  5  * 功能說明:計算機領域經典的算法  6  *  7  */  8 public class sortAlgorithm<T extends Comparable<T>> {  9      10     //交換索引i和索引j的值 11     PRivate void swap(T [] data ,int i,int j){ 12         T tmp; 13         tmp=data[i]; 14         data[i]=data[j]; 15         data[j]=tmp; 16     } 17      18      19     //-----堆排序 時間復雜度O(nlogn)----- 20      21     public void heapSort(T [] data){ 22         int arrayLength=data.length; 23         //循環件堆 24         for(int i=0;i<arrayLength-1;i++){ 25             // 建堆 26             builMaxdHeap(data, arrayLength - 1 - i); 27             // 交換堆頂和最后一個元素 28             swap(data, 0, arrayLength - 1 - i); 29  30         } 31     } 32      33     // 對data數組從0到lastIndex建大頂堆 34     private void builMaxdHeap(T[] data, int lastIndex) { 35         // 從lastIndex處節點（最后一個節點）的父節點開始 36         for (int i = (lastIndex - 1) / 2; i >= 0; i--) { 37             // k保存當前正在判斷的節點 38             int k = i; 39             // 如果當前k節點的子節點存在 40             while (k * 2 + 1 <= lastIndex) { 41                 // k節點的左子節點的索引 42                 int biggerIndex = 2 * k + 1; 43                 // 如果biggerIndex小于lastIndex，即biggerIndex + 1 44                 // 代表的k節點的右子節點存在 45                 if (biggerIndex < lastIndex) { 46                     // 如果右子節點的值較大 47                     if (data[biggerIndex].compareTo(data[biggerIndex + 1]) < 0) { 48                         // biggerIndex總是記錄較大子節點的索引 49                         biggerIndex++; 50                     } 51                 } 52                 // 如果k節點的值小于其較大子節點的值 53                 if (data[k].compareTo(data[biggerIndex]) < 0) { 54                     // 交換它們 55                     swap(data, k, biggerIndex); 56                     // 將biggerIndex賦給k，開始while循環的下一次循環， 57                     // 重新保證k節點的值大于其左、右子節點的值。 58                     k = biggerIndex; 59                 } else { 60                     break; 61                 } 62             } 63         } 64     } 65       66     //-----冒泡排序法 時間復雜度O(n^2)----- 67     public void bubbleSort(T[] data){ 68         int i,j; 69         for(i=0;i<data.length-1;i++){ 70             for(j=0;j<data.length-i-1;j++){ 71                 if(data[j].compareTo(data[j+1]) > 0){ 72                     swap(data,j+1,j); 73                 } 74             } 75         } 76     } 77       78     //-----選擇排序法 時間復雜度O(n^2)----- 79     public void selectSort(T[] data){ 80         int i,j;     81           82         for(i=0;i<data.length-1;i++){ 83             for(j=i+1;j<data.length;j++){ 84                 if (data[i].compareTo(data[j]) > 0){ 85                     swap(data,i,j); 86                 } 87             } 88         } 89     } 90       91     //-----快速排序法  時間復雜度為O(log2n)----- 92     public void quickSort(T[] data){ 93         subQuickSort(data,0,data.length-1); 94     } 95       96     private void subQuickSort(T[] data,int start,int end){ 97         if( start < end ){ 98             //以第一個元素作為分界值 99             T base = data[start];100             //i從左邊開始搜索大于分界值元素的索引101             int i = start;102             //j從右邊開始搜索小于分界值元素的索引103             int j = end + 1;104             while(true){105                 //左邊跳過比base小的元素106                 while(i < end && data[++i].compareTo(base) <= 0);107                 //右邊跳過比base大的元素108                 while(j > start && data[--j].compareTo(base) >= 0);109                  110                 if(j > i){111                     swap(data,i,j);112                 }else{113                     break;114                 }115             }116             //將分界值還原117             swap(data,start,j);118              119             //遞歸左邊序列120             subQuickSort(data,start,j-1);121             //遞歸右邊序列122             subQuickSort(data,j+1,end);123         }124     }125      126     //-----插入排序法 時間復雜度O(n^2)-----127     public void insertSort(T[] data){128         int arrayLength = data.length;129          130         for(int i=1;i<arrayLength;i++){131             //當整體后移時保證data[i]的值不會丟失132             T tmp = data[i];133             //i索引處的值已經比前面所有值都大,表明已經有序,無需插入134             //i-1處索引之前的數值已經有序,i-1處索引處元素的值也是最大值135             if(data[i].compareTo(data[i-1]) < 0){136                 int j = i-1;137                 //整體后移一個138                 while(j>=0 && data[j].compareTo(tmp) > 0){139                     data[j+1] = data[j];140                     j--;141                 }142             data[j+1] = tmp;143             }144         }145     }146      147     //-----折半插入排序法 時間復雜度-----148     public void binaryInsertSort(T[] data) {149         int arrayLength = data.length;150  151         for (int i = 1; i < arrayLength; i++) {152             if (data[i - 1].compareTo(data[i]) > 0) {153                 // 緩存i處的元素值154                 T tmp = data[i];155  156                 // 記錄搜索范圍的左邊界157                 int low = 0;158                 // 記錄搜索范圍的右邊界159                 int high = i - 1;160  161                 while (high >= low) {162                     // 記錄中間位置163                     int mid = (high + low) / 2;164                     // 比較中間位置數據和i處數據大小，以縮小搜索范圍165  166                     if (tmp.compareTo(data[mid]) > 0) {167                         low = mid + 1;168                     } else {169                         high = mid - 1;170                     }171                 }172                 // 將low~i處數據整體向后移動1位173                 for (int j = i; j > low; j--) {174                     data[j] = data[j - 1];175                 }176                 data[low] = tmp;177  178             }179         }180     }181      182     //-----希爾排序法 時間復雜度O(nlogn)O(n^2)具體看h的值-----183     public void shellSort(T[] data){184         int arrayLength = data.length;185         //h保存可變增量186          187         int h = 1;188         while(h<=arrayLength/3){189             h = h * 3 + 1;190         }191          192         while(h > 0){193             //System.out.println(Arrays.toString( data )+"h="+h);194              195             for(int i=h;i<arrayLength;i++){196                 //當整體后移時,保證data[i]的值不丟失197                 T tmp = data[i];198                 //i索引處的值已經比前面所有的值大199                 //(i-1索引之前的值已經有序的,i-1索引處元素的值就是最大值)200                 if(data[i].compareTo(data[i-h]) < 0){201                     int j = i-h;202                     //整體后移一格203                     while(j>=0 && data[j].compareTo(tmp) > 0){204                         data[j+h] = data[j];205                         j-=h;206                     }207                      208                     //最后將tmp值插入合適的位置209                     data[j+h] = tmp;210                 }211             }212             h = (h-1)/3;213         }214          215     }216      217     //-----歸并排序法 時間復雜度為O(nlog2n)-----218     public void mergeSort(T[] data){219         subMergeSort(data,0,data.length-1);220     }221      222     private void subMergeSort(T[] data,int left,int right){223         if(right > left){224             //找出中間索引225             //System.out.println(  Arrays.toString(data) );226             int center = (left + right)/2;227             //對左邊數組進行遞歸228             subMergeSort(data,left,center);229             //對右邊數組進行遞歸230             subMergeSort(data,center+1,right);231             //合并232             merge(data,left,center,right);233         }234     }235      236     @SuppressWarnings("unchecked")237     private void merge(T[] data, int left, int center, int right) {238         Object[] tmpArr = new Object[data.length];239         int mid = center + 1;240         // third記錄中間處索引241         int third = left;242         int tmp = left;243  244         while (left <= center && mid <= right) {245             // 從兩個數組中取出最小的放入中間數組246             if (data[left].compareTo(data[mid]) <= 0) {247                 tmpArr[third++] = data[left++];248             } else {249                 tmpArr[third++] = data[mid++];250             }251         }252          253         // 剩余部分依次放入中間數組254         while (mid <= right) {255             tmpArr[third++] = data[mid++];256         }257         while (left <= center) {258             tmpArr[third++] = data[left++];259         }260          261         // 將中間數組的內容復制拷回原數組262         // (原left~right范圍內德內容被復制回原數組)263         while (tmp <= right) {264             data[tmp] = (T) tmpArr[tmp++];265         }266     }267      268 269 270     public static void main(String[] args) {271         // TODO Auto-generated method stub272 273     }274 275 }