本章包含了插入排序中的直接插入排序希尔排序选择排序中的选择排序堆排序交换排序中的冒泡排序快速排序以及归并排序。插入排序1.直接插入排序public static void insertionSort(int[] arrays){//将后面的数字插入到前面排好的序列中 for(int i0;iarrays.length;i){ int tmparrays[i]; int mi; for(int ji-1;j0;j--){ if(arrays[j]tmp){ arrays[j1]arrays[j]; mj; } } arrays[m]tmp; } }2.希尔排序public static void shellsort(int[] arr){//直接插入排序的优化先分组按直接插入排序进行组别间距再逐渐减小直到变为1就变成同一组了 int gaparr.length; while(gap1){ for(int i0;iarr.length;i){//这里的i按减一进行就可以使得组别交替进行 int tmparr[i]; int mi; for(int ji-gap;j0;jj-gap){ if(arr[j]tmp){ arr[jgap]arr[j]; mj; } } arr[m]tmp; } gapgap/2; } }选择排序1.选择排序public static void chooseSort(int[] arr){//每次挑中未排序队列中最大的将它放置在未排序队列的最末尾 for(int i0;iarr.length;i){ int max0; int m0; for(int j0;jarr.length-i;j){ if(arr[j]max){ maxarr[j]; mj; } } int tmparr[arr.length-1-i]; arr[arr.length-1-i]max; arr[m]tmp; } }2.堆排序public static void heapSort(int[] arr){ int sizearr.length-1; creatHeap(arr,size); for(int i0;iarr.length;i){ int tmparr[size]; arr[size]arr[0]; arr[0]tmp; size--; creatHeap(arr,size); } } private static void creatHeap(int[] arr,int size) { for(int i(size-1)/2;i0;i--){ sifdown(arr,i,size); } } private static void sifdown(int[] arr, int p,int size) { int cp*21; while(csize){ if((c1)sizearr[c]arr[c1]){ c; } if(arr[p]arr[c]){ int tmparr[p]; arr[p]arr[c]; arr[c]tmp; } pc; cp*21; } }交换排序1.冒泡排序public static void BubbleSort(int[] arr){ for(int i0;i(arr.length-1);i){ for(int j0;j(arr.length-1-i);j){ if(arr[j]arr[j1]){ int tmparr[j]; arr[j]arr[j1]; arr[j1]tmp; } } } }2.快速排序public static void QuickSort(int[] arr){ Quick(arr,0,arr.length-1); } public static void Quick(int[] arr,int start,int end){ if(startend){ return; } int index pattern(arr,start,end); Quick(arr,start,index-1); Quick(arr,index1,end); } private static int pattern(int[] arr, int start, int end) { int topstart; int lateend; int tmparr[start]; while(toplate){ while(toplatearr[late]tmp){ late--; } while (toplatearr[top]tmp){ top; } int harr[top]; arr[top]arr[late]; arr[late]h; } arr[start]arr[top]; arr[top]tmp; return top; }归并排序public static void mergeSort(int[] arr) { if (arr null || arr.length 2) { return; } int[] temp new int[arr.length]; mergeSort(arr, 0, arr.length - 1, temp); } private static void mergeSort(int[] arr, int left, int right, int[] temp) { if (left right) { return; } int mid left (right - left) / 2; mergeSort(arr, left, mid, temp); mergeSort(arr, mid 1, right, temp); merge(arr, left, mid, right, temp); } private static void merge( int[] arr, int left, int mid, int right, int[] temp) { int i left; int j mid 1; int index left; while (i mid j right) { if (arr[i] arr[j]) { temp[index] arr[i]; } else { temp[index] arr[j]; } } while (i mid) { temp[index] arr[i]; } while (j right) { temp[index] arr[j]; } for (int k left; k right; k) { arr[k] temp[k]; } }
经典排序算法
本章包含了插入排序中的直接插入排序希尔排序选择排序中的选择排序堆排序交换排序中的冒泡排序快速排序以及归并排序。插入排序1.直接插入排序public static void insertionSort(int[] arrays){//将后面的数字插入到前面排好的序列中 for(int i0;iarrays.length;i){ int tmparrays[i]; int mi; for(int ji-1;j0;j--){ if(arrays[j]tmp){ arrays[j1]arrays[j]; mj; } } arrays[m]tmp; } }2.希尔排序public static void shellsort(int[] arr){//直接插入排序的优化先分组按直接插入排序进行组别间距再逐渐减小直到变为1就变成同一组了 int gaparr.length; while(gap1){ for(int i0;iarr.length;i){//这里的i按减一进行就可以使得组别交替进行 int tmparr[i]; int mi; for(int ji-gap;j0;jj-gap){ if(arr[j]tmp){ arr[jgap]arr[j]; mj; } } arr[m]tmp; } gapgap/2; } }选择排序1.选择排序public static void chooseSort(int[] arr){//每次挑中未排序队列中最大的将它放置在未排序队列的最末尾 for(int i0;iarr.length;i){ int max0; int m0; for(int j0;jarr.length-i;j){ if(arr[j]max){ maxarr[j]; mj; } } int tmparr[arr.length-1-i]; arr[arr.length-1-i]max; arr[m]tmp; } }2.堆排序public static void heapSort(int[] arr){ int sizearr.length-1; creatHeap(arr,size); for(int i0;iarr.length;i){ int tmparr[size]; arr[size]arr[0]; arr[0]tmp; size--; creatHeap(arr,size); } } private static void creatHeap(int[] arr,int size) { for(int i(size-1)/2;i0;i--){ sifdown(arr,i,size); } } private static void sifdown(int[] arr, int p,int size) { int cp*21; while(csize){ if((c1)sizearr[c]arr[c1]){ c; } if(arr[p]arr[c]){ int tmparr[p]; arr[p]arr[c]; arr[c]tmp; } pc; cp*21; } }交换排序1.冒泡排序public static void BubbleSort(int[] arr){ for(int i0;i(arr.length-1);i){ for(int j0;j(arr.length-1-i);j){ if(arr[j]arr[j1]){ int tmparr[j]; arr[j]arr[j1]; arr[j1]tmp; } } } }2.快速排序public static void QuickSort(int[] arr){ Quick(arr,0,arr.length-1); } public static void Quick(int[] arr,int start,int end){ if(startend){ return; } int index pattern(arr,start,end); Quick(arr,start,index-1); Quick(arr,index1,end); } private static int pattern(int[] arr, int start, int end) { int topstart; int lateend; int tmparr[start]; while(toplate){ while(toplatearr[late]tmp){ late--; } while (toplatearr[top]tmp){ top; } int harr[top]; arr[top]arr[late]; arr[late]h; } arr[start]arr[top]; arr[top]tmp; return top; }归并排序public static void mergeSort(int[] arr) { if (arr null || arr.length 2) { return; } int[] temp new int[arr.length]; mergeSort(arr, 0, arr.length - 1, temp); } private static void mergeSort(int[] arr, int left, int right, int[] temp) { if (left right) { return; } int mid left (right - left) / 2; mergeSort(arr, left, mid, temp); mergeSort(arr, mid 1, right, temp); merge(arr, left, mid, right, temp); } private static void merge( int[] arr, int left, int mid, int right, int[] temp) { int i left; int j mid 1; int index left; while (i mid j right) { if (arr[i] arr[j]) { temp[index] arr[i]; } else { temp[index] arr[j]; } } while (i mid) { temp[index] arr[i]; } while (j right) { temp[index] arr[j]; } for (int k left; k right; k) { arr[k] temp[k]; } }
