冒泡、插入、归并、堆排序、快速排序的Java实现代码
浏览数：18 /
时间：2015年06月08日
详细课程就不表了，看代码吧
1 import java.util.Arrays; 2 3 public class Sort { 4 5 6 static int swapTimes=0; 7 public static void main(String[] args) { 8 int[] numbers = { 7, 6, 5, 3, 1, 8, 9, 7, 1, 2 ,5}; 9 //*** BubbleSort Test *** 10 //bubbleSort(numbers); 11 12 //*** InsertSort Test *** 13 //insertSort(numbers); 14 15 //*** MergeSort Test *** 16 //mergeSort(numbers); 17 18 //*** HeapSort Test *** 19 //heapSort(numbers); 20 21 //*** QuickSort Test *** 22 23 quickSort(numbers); 24 System.out.println("result:"+Arrays.toString(numbers)); 25 26 } 27 28 /* 29 * 插入排序 30 */ 31 public static void insertSort(int[] numbers) { 32 System.out.println("InsertSort:"+Arrays.toString(numbers)); 33 if (numbers == null) { 34 System.out.println("Invalid input!"); 35 return; 36 } 37 for (int i = 1; i < numbers.length; i++) { 38 int temp=numbers[i]; 39 int j=i-1; 40 for (; j >= 0&&numbers[j]>temp; j--) { //这个数大于比较数，就把这个数右移 41 numbers[j + 1] = numbers[j]; 42 System.out.println(Arrays.toString(numbers)+"---temp="+temp); 43 } 44 numbers[j+1]=temp; //把比较数赋值到正确位置 45 System.out.println(Arrays.toString(numbers)); 46 } 47 } 48 49 /* 50 * 冒泡排序 51 */ 52 public static void bubbleSort(int[] numbers) { 53 System.out.println("BubbleSort:"); 54 if (numbers == null) { 55 System.out.println("Invalid input!"); 56 return; 57 } 58 for (int i = numbers.length - 1; i > 0; i--) { 59 for (int j = 0; j < i; j++) { 60 if (numbers[j] > numbers[j + 1]) { 61 swap(numbers, j, j + 1); 62 } 63 } 64 } 65 System.out.println("result:"); 66 } 67 /* 68 * 归并排序 69 */ 70 public static void mergeSort(int[] numbers){ 71 if(numbers==null){ 72 System.out.println("Invalid input!"); 73 return; 74 } 75 mergeSort(numbers,0,numbers.length-1); 76 } 77 78 private static void mergeSort(int[] numbers, int start, int end) { 79 if(start>=end){ 80 return; 81 } 82 int mid=(start+end)>>1; 83 mergeSort(numbers, start, mid); 84 mergeSort(numbers, mid+1, end); 85 merge(numbers,start,mid,end); 86 System.out.println(Arrays.toString(numbers)+"---mid="+mid); 87 } 88 /* 89 * 合并两个有序数组 90 */ 91 private static void merge(int[] numbers, int start, int mid, int end) { 92 int leftLength=mid-start+1; 93 int rightLength=end-mid; 94 int[] leftNumbers=new int[leftLength]; 95 int[] rightNumbers=new int[rightLength]; 96 for (int i = 0; i < leftLength; i++) {//将左边的元素赋给left数组 97 leftNumbers[i]=numbers[start+i]; 98 } 99 for (int j = 0; j < rightLength; j++) {//同理 100 rightNumbers[j]=numbers[mid+j+1]; 101 } 102 int pLeft=0; 103 int pRight=0; 104 for(int index=start;index<=end;index++){//开始merge左右数组 105 if(pLeft==leftLength){ //当left数组合并完了，就直接赋值right数组 106 numbers[index]=rightNumbers[pRight++]; 107 }else if(pRight==rightLength){ 108 numbers[index]=leftNumbers[pLeft++]; 109 }else{ //左右数组都没赋值完，就要比较大小 110 if(leftNumbers[pLeft]<=rightNumbers[pRight]){ 111 numbers[index]=leftNumbers[pLeft++]; 112 }else{ 113 numbers[index]=rightNumbers[pRight++]; 114 } 115 } 116 } 117 } 118 /* 119 * 堆排序 120 */ 121 public static void heapSort(int[] numbers){ 122 if(numbers==null){ 123 System.out.println("Invalid input!"); 124 return; 125 } 126 int[] heap=buildHeap(numbers); //构造小顶堆 127 System.out.println("build Heap:"+Arrays.toString(heap)); 128 int index=0; 129 while(!isHeapEmpty(heap)){ 130 //注意，这里不能在前面的index++，因为会先算左括号内的++，造成传入的index+1 131 numbers[index]=popHeapTop(heap,index++); 132 133 } 134 } 135 //将堆顶元素pop出来 136 private static int popHeapTop(int[] heap,int index) { 137 int temp=heap[0]; 138 int end=heap.length-1-index; 139 heap[0]=heap[end]; //将最后一个数移至堆顶 140 heap[end]=Integer.MAX_VALUE; 141 adjustHeap(heap, 0); //调整堆 142 System.out.println("current Heap:"+Arrays.toString(heap)); 143 return temp; 144 } 145 146 private static boolean isHeapEmpty(int[] heap) { 147 if(heap[0]==Integer.MAX_VALUE){ 148 return true; 149 } 150 return false; 151 } 152 /* 153 * 构造小顶堆 154 */ 155 private static int[] buildHeap(int[] numbers) { 156 int[] heap=new int[numbers.length]; 157 for(int i=0;i<heap.length;i++){ 158 heap[i]=numbers[i]; 159 } 160 for(int j=(heap.length>>1)-1;j>=0;j--){ //从有孩子的结点开始，从底向上维护堆 161 adjustHeap(heap,j); 162 } 163 return heap; 164 } 165 /* 166 * 维护堆 167 */ 168 private static void adjustHeap(int[] heap, int j) { 169 int left=j<<1; 170 int right=(j<<1)+1; 171 int largest=j; 172 if(left<heap.length //该左孩子下标必须在数组内 173 &&heap[left]!=Integer.MAX_VALUE //该元素必须未被覆盖 174 &&heap[j]<heap[left]){ 175 largest=left; 176 } 177 if(right<heap.length 178 &&heap[right]!=Integer.MAX_VALUE 179 &&heap[largest]<heap[right]){ 180 largest=right; 181 } 182 183 if(largest!=j){ 184 swap(heap, j, largest); 185 adjustHeap(heap, largest); //继续往下调整 186 } 187 188 } 189 190 /* 191 * 快速排序 192 */ 193 public static void quickSort(int[] numbers){ 194 if(numbers==null){ 195 System.out.println("Invalid input!"); 196 return; 197 } 198 System.out.println("QuickSort:"); 199 quickSort(numbers,0,numbers.length-1); 200 } 201 private static void quickSort(int[] numbers, int start, int end) { 202 if(start<end){ 203 int mid=patition(numbers,start,end); 204 quickSort(numbers, start, mid-1); 205 quickSort(numbers, mid+1, end); 206 } 207 208 } 209 /* 210 * 选一个数，将小于它的数放在左边，大于它的放在右边 211 */ 212 private static int patition(int[] numbers, int start, int end) { 213 int small=start-1; 214 int index=start; 215 int temp=numbers[end]; //选择数组最后一个元素作为比较数 216 while(index<=end){ 217 if(numbers[index]<temp){ 218 small++; 219 if(index!=small){ 220 swap(numbers, small, index); 221 } 222 } 223 index++; 224 } 225 swap(numbers, small+1, end); 226 return small+1; 227 } 228 /* 229 * 交换数组的两个元素 230 */ 231 private static void swap(int[] numbers, int a, int b) { 232 int temp = numbers[a]; 233 numbers[a] = numbers[b]; 234 numbers[b] = temp; 235 System.out.println("current numbers:" + //记录交换次数 236 ""+Arrays.toString(numbers)+"----swap times:"+(++swapTimes)); 237 } 238 239 240 241 }
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
