你的位置:首页 > Java教程

[Java教程]经典的排序算法java实现版


 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 }