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 }
新闻热点
疑难解答
