常用的几种排序算法总结
package com.sort2;import java.util.Arrays;public class SortUtil{//直接查找排序public static void insertSort(int []value){int i,j,temp;//从第二个数开始，插入前面的有序序列for( i=1;i<=value.length-1;i++){//记录将要插入的记录temp=value[i];//从该记录前面的一条记录开始比较，如果比前面的数小，那么不断后移for(j=i-1;j>=0;j--){//快速排序是稳定的，关键在于这里if(temp<value[j]){value[j+1]=value[j];}else break;}value[j+1]=temp;}}//希尔排序public static void shellSort(int[]value,int distance){//依次缩小间距,shell有四次循环，由于直接插入排序对于大致有序的序列效率比较高，所以shell排序的出发点是先让序列大致有序，其本质就是插入排序//希尔排序时不稳定的while(distance>=1){for(int i=0;i<distance;i++){for(int j=i+distance;j<value.length;j+=distance){int temp=value[j];int k;for(k=j-distance;k>=i;k-=distance){if(temp<value[k])value[k+distance]=value[k];elsebreak;}value[k+distance]=temp;}}if(distance==1){return;}distance=distance/3+1;}}//冒泡排序public static void bubbleSort(int []value){//for(int i=1;i<value.length;i++){for(int j=0;j<value.length-i;j++){if(value[j]>value[j+1]){int temp=value[j];value[j]=value[j+1];value[j+1]=temp;}}}}//快速排序public static void quickSort(int []value){quickSort(value,0,value.length-1);}public static void quickSort(int []value,int begin,int end){if(begin<end){int low=begin;int height=end;int temp=value[low];while(low<height){while(low<height && value[height]>=temp){height--;}if(low<height){value[low++]=value[height];}while(low<height && value[low]<=temp){low++;}if(low<height){value[height--]=value[low];}}value[low]=temp;quickSort(value,begin,low-1);quickSort(value,low+1,end);}}//选择排序public static void selectSort(int[]value){for(int i=0;i<value.length-1;i++){int min=i;for(int j=i+1;j<value.length;j++){if(value[min]>value[j]){min=j;}}if(min!=i){int t=value[min];value[min]=value[i];value[i]=t;}}}//堆排序//先进行调整堆，建立堆是在调整堆的基础之上的/** * value：带排序的数列 * i:待调整的节点，i是从0开始计数 */public static void adjustHeap(int []value,int i,int size){//由于数组的下标是从0开始的int left=2*i+1;int right=2*i+2;int temp=i;if(i<size/2){if(left<size && value[left]>value[i] ){temp=left;int t=value[left];value[left]=value[i];value[i]=t;adjustHeap(value,left,size);}if(right<size && value[right]>value[i] ){temp=right;int t=value[right];value[right]=value[i];value[i]=t;adjustHeap(value,left,size);}}}//建立一个堆public static void buildHeap(int []value){for(int i=value.length/2-1;i>=0;i--){adjustHeap(value,i,value.length);}System.out.println(Arrays.toString(value));}//最后进行堆排序public static void heapSort(int []value){buildHeap(value);for(int i=value.length-1;i>=1;i--){int t=value[i];value[i]=value[0];value[0]=t;adjustHeap(value, 0, i);}}//归并排序public static void mergeArray(int []a,int first,int mid,int last,int[]temp){int i,j,k;i=first;j=mid+1;k=0;while(i<=mid && j<=last){if(a[i]<a[j]){temp[k++]=a[i++];}else{temp[k++]=a[j++];}}while(i<=mid){temp[k++]=a[i++];}while(j<=last){temp[k++]=a[j++];}for(int t=0;t<k;t++){a[first+t]=temp[t];}}//public static void mergeSort(int []a,int first,int last,int []temp){int mid;if(first<last){mid=(first+last)/2;mergeSort(a,first,mid,temp);mergeSort(a,mid+1,last,temp);mergeArray(a,first,mid,last,temp);}}public static void Merge(int []a,int []temp){mergeSort(a,0,a.length-1,temp);}}