1 package sort; 2  3 public class BubbleSort { 4 public static void swap(int[] source,int x,int y){ 5     int temp=source[y]; 6     source[y]=source[x]; 7     source[x]=temp; 8 } 9 /*10  * 每次将最大的气泡沉底，需要(n-1)趟扫描，每次扫描(n-i)次11  * 复杂度O(n2)12  * 稳定13  */14 public static void sort(int[] source){15     for(int i=source.length-1;i>0;i--){16         for(int j=0;j<i;j++){17             if(source[j]>source[j+1])18                 swap(source, j, j+1);19         }20     }21 }22 23 public static void main(String[] args) {24     int[] source={9,3,6,2,1,8,4,5};25     sort(source);26     for (int i = 0; i < source.length; i++) {27         System.out.print(source[i]);28     }29 }30 }

 1 package sort; 2  3 public class AdvancedBubbleSort { 4 public static void swap(int[] source,int x,int y){ 5     int temp=source[y]; 6     source[y]=source[x]; 7     source[x]=temp; 8 } 9 10 public static void sort(int[] source){11     for(int i=source.length-1;i>0;i--){12         boolean exchange=false;13         for(int j=0;j<i;j++){14             if(source[j]>source[j+1]){15                 swap(source, j, j+1);16                 exchange=true;17             }18         }19         if(!exchange)//如果本轮没有发生交换，则终止排序20             return;21     }22 }23 24 public static void main(String[] args) {25     int[] source={9,3,6,2,1,8,4,5};26     sort(source);27     for (int i = 0; i < source.length; i++) {28         System.out.print(source[i]);29     }30 }31 }

 1 package sort; 2  3 public class SelectionSort { 4     public static void swap(int[] source,int x,int y){ 5         int temp=source[y]; 6         source[y]=source[x]; 7         source[x]=temp; 8     } 9     //第n轮扫描选择没有排序的序列（即n后边的）中最小的数值与第n处交换10     //复杂度O(n2)11     //不稳定12     public static void sort(int[] source){13         for(int i=0;i<source.length-1;i++){14             for(int j=i+1;j<source.length;j++){15                 if(source[j]<source[i])16                     swap(source, i, j);17             }18         }19     }20     21     public static void main(String[] args) {22         int[] source={9,3,6,2,1,8,4,5,0,7};23         sort(source);24         for (int i = 0; i < source.length; i++) {25             System.out.print(source[i]);26         }27     }28 }

 1 package sort; 2  3 public class InsertSort { 4     public static void swap(int[] source,int x,int y){ 5         int temp=source[y]; 6         source[y]=source[x]; 7         source[x]=temp; 8     } 9     /*10      * 注意和选择排序的区别，选择排序是每次在剩下没排序序列中选择一个最小的放到当前位置11      * 插入排序是每次将当前位置（待排序）的放到前边已排序序列中的合适位置12      * 复杂度O(n2):这么想，要扫描n-1轮，每轮n-i次13      * 适合数据量级小于千14      */15     public static void sort(int[] source){16         for(int i=0;i<source.length-1;i++){17             for(int j=i+1;j>0;j--){18                 if(source[j]<source[j-1])19                     swap(source, j, j-1);20                 else 21                     break;22             }23         }24     }25     26     public static void main(String[] args) {27         int[] source={9,3,6,2,1,8,4,5,0,7};28         sort(source);29         for (int i = 0; i < source.length; i++) {30             System.out.print(source[i]);31         }32     }33 }

 1 package sort; 2  3 public class ShellSort { 4     public static void swap(int[] source,int x,int y){ 5         int temp=source[y]; 6         source[y]=source[x]; 7         source[x]=temp; 8     } 9     /*所谓的分组插入排序，开始时分组多，组内数据少，直接插入排序较快；10      * 逐渐分组少，组内数据量大，但组内数据接近有序状态，所以总体快于直接插入排序11      * O(n2)?12      * 不稳定13      */14     public static void shellPass(int[] source, int d){15         for(int i=d;i<source.length;i++){//from 016             if(source[i]<source[i-d]){17                 swap(source, i, i-d);18             }19         }20     }21     22     public static void sort(int[] source){23         int increment=source.length/2+1;  //保证首次分两组才能保证充分排序24         while(increment>1){25             shellPass(source, increment);26             increment=increment/3+1;      //除以3保证不会再增量等于2时无限循环27             if(increment==1)              //保证最后增量=1，单独处理28                 shellPass(source, 1);29         }    30     }31     32     public static void main(String[] args) {33         int[] source={49,38,65,97,76,13,27,49,55,4,18,0,74,06};34         sort(source);35         for (int i = 0; i < source.length; i++) {36             System.out.print(source[i]+" ");37         }38     }39 }

 1 package sort; 2  3 public class BinSort { 4 /*不要与二分搜索混淆，只是对直接插入排序的改进，每一次在已排序的序列中使用二分查找找到合适位置插入当前待排序那个数值 5  * 注意找到位置后该位置全部后移，由于数组实现，所以后移时是倒着进行，这时当前待排序数值会被抹掉，所以temp记住它 6  * 查找O(nlog(n)),元素移动次数O(n2),故时间O(n2) 7  */ 8 public static void sort(int[] source){ 9     int low,high,mid;10     int temp;11     for(int i=0;i<source.length;i++){12         temp=source[i];13         low=0;14         high=i-1;15         while(low<=high){16             mid=(low+high)/2;17             if(source[mid]>temp){18                 high=mid-1;//要排序元素在已经排过序的数组左边19             }else{20                 low=mid+1;21             }22         }23         for(int j=i-1;j>high;j--){//找到了要插入的位置，然后将这个位置以后的所有元素向后移动24             source[j+1]=source[j];25         }26         source[high+1]=temp;27     }28     29 }30 31 public static void main(String[] args) {32     int[] source={49,38,65,97,76,13,27,49,55,4,18,0,74,06};33     sort(source);34     for (int i = 0; i < source.length; i++) {35         System.out.print(source[i]+" ");36     }37 }38 }

 1 package sort; 2  3 public class QuickSort { 4     /*第一趟将起始位置值作为基准，从后向前扫描，找出小于povit的值，替换左边值 5      * 立刻从左边开始扫描，查找大于povit的值，替换右边，知道将所有值分到povit两边 6      * 不稳定 7      * 平均时间复杂度O(nlogn),最差复杂度O(n2) 8      */ 9     public static void sort(int[] source, int low, int high){10         int h=high;11         int l=low;12         int povit=source[low];13         14         while(l<h){15             16             while(l<h&&source[h]>=povit){17                 h--;18                 System.out.println("h="+h);19             }20             21             if(l<h){22                 int temp=source[h];23                 source[h]=source[l];24                 source[l]=temp;25                 l++;//加的是左边，因为只能保证左边加入一个不大于povit的值26             }27             28             while(l<h&&source[l]<=povit){29                 l++;30             }31             32             if(l<h){33                 int temp=source[h];34                 source[h]=source[l];35                 source[l]=temp;36                 h--;//同理，减得右边37             }38         }39         System.out.print("l="+(l+1)+"h="+(h+1)+"povit="+povit+"\n");40         //此时一定有l=h41         if(l>low)42             sort(source, low, h-1);43         if(h<high)44             sort(source, h+1, high);45     }46     47     public static void main(String[] args) {48         int[] source={49,38,65,97,76,13,27,49,55,4,18,0,74,06};49         sort(source,0,source.length-1);50         for (int i = 0; i < source.length; i++) {51             System.out.print(source[i]+" ");52         }53     }54 }

 1 package sort; 2  3 public class MergeSort { 4  5 //将有二个有序数列a[first,...,mid]和a[mid+1,...,last]合并。 6 public static void mergeArray(int a[], int first, int mid, int last, int temp[]){ 7     int i=first; 8     int j=mid+1; 9     int k=0;10     11     while(i<=mid&&j<=last){12         if(a[i]<a[j])13             temp[k++]=a[i++];14         else15             temp[k++]=a[j++];16     }17     18     while(i<=mid){19         temp[k++]=a[i++];20     }21     while(j<=last){22         temp[k++]=a[j++];23     }24     25     for(i=0;i<k;i++)//copy26         a[first+i]=temp[i];27 }28 29 /*先分割再合并，当数组只有一个元素时为有序，有序数组之间合并得到有序数组30  * 稳定31  * O(nlogn)32  */33 public static void mergeSort(int a[],int first,int last,int temp[]){34     if(first<last){35         int mid=(first+last)/2;36         mergeSort(a, first, mid, temp);//左边有序37         mergeSort(a, mid+1, last, temp);//右边有序38         mergeArray(a, first, mid, last, temp); //再将二个有序数列合并  39     }40 }41 42 public static void main(String[] args) {43     int[] source={49,38,65,97,76,13,27,49,55,4,18,0,74,06};44     int[] temp=new int[source.length];45     mergeSort(source,0,source.length-1,temp);46     for (int i = 0; i < source.length; i++) {47         System.out.print(source[i]+" ");48     }49 }50 }