经典排序算法

本章包含了插入排序中的直接插入排序，希尔排序；选择排序中的选择排序，堆排序；交换排序中的冒泡排序，快速排序；以及归并排序。

插入排序

1.直接插入排序

public static void insertionSort(int[] arrays){//将后面的数字插入到前面排好的序列中 for(int i=0;i<arrays.length;i++){ int tmp=arrays[i]; int m=i; for(int j=i-1;j>=0;j--){ if(arrays[j]>tmp){ arrays[j+1]=arrays[j]; m=j; } } arrays[m]=tmp; } }

2.希尔排序

public static void shellsort(int[] arr){//直接插入排序的优化，先分组按直接插入排序进行，组别间距再逐渐减小，直到变为1，就变成同一组了 int gap=arr.length; while(gap>=1){ for(int i=0;i<arr.length;i++){//这里的i按减一进行，就可以使得组别交替进行 int tmp=arr[i]; int m=i; for(int j=i-gap;j>=0;j=j-gap){ if(arr[j]>tmp){ arr[j+gap]=arr[j]; m=j; } } arr[m]=tmp; } gap=gap/2; } }

选择排序

1.选择排序

public static void chooseSort(int[] arr){//每次挑中未排序队列中最大的将它放置在未排序队列的最末尾 for(int i=0;i<arr.length;i++){ int max=0; int m=0; for(int j=0;j<arr.length-i;j++){ if(arr[j]>max){ max=arr[j]; m=j; } } int tmp=arr[arr.length-1-i]; arr[arr.length-1-i]=max; arr[m]=tmp; } }

2.堆排序

public static void heapSort(int[] arr){ int size=arr.length-1; creatHeap(arr,size); for(int i=0;i<arr.length;i++){ int tmp=arr[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;i>=0;i--){ sifdown(arr,i,size); } } private static void sifdown(int[] arr, int p,int size) { int c=p*2+1; while(c<=size){ if((c+1)<size&&arr[c]<arr[c+1]){ c++; } if(arr[p]<arr[c]){ int tmp=arr[p]; arr[p]=arr[c]; arr[c]=tmp; } p=c; c=p*2+1; } }

交换排序

1.冒泡排序

public static void BubbleSort(int[] arr){ for(int i=0;i<(arr.length-1);i++){ for(int j=0;j<(arr.length-1-i);j++){ if(arr[j]>arr[j+1]){ int tmp=arr[j]; arr[j]=arr[j+1]; arr[j+1]=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(start>=end){ return; } int index= pattern(arr,start,end); Quick(arr,start,index-1); Quick(arr,index+1,end); } private static int pattern(int[] arr, int start, int end) { int top=start; int late=end; int tmp=arr[start]; while(top<late){ while(top<late&&arr[late]>=tmp){ late--; } while (top<late&&arr[top]<=tmp){ top++; } int h=arr[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]; } }