需要掌握的基础排序
一、插入排序 1)直接插入排序2)希尔排序
二、交换排序 1)冒泡排序2)快速排序
三、选择排序 1)简单选择排序2)堆排序
四、归并排序
一、插入排序
简单的理解就是遍历整个数组，在过程中对每个数都跟前面进行比较只要比它小就往前挪。
1) 直接插入排序实现
public static void directInsert(int [] data) { int temp=0; int len=data.length; for(int i=1;i<len;i++) { temp=data[i]; int j=i-1; while(j>-1 && temp<data[j]) { data[j+1]=data[j]; j--; } data[j+1]=temp; } }
2）希尔排序
理解：http://blog.csdn.net/morewindows/article/details/6668714
按照n/2,n/4,n/8,,,,1的间隔对数组进行直接插入排序。当数组基本有序时，插入排序比较的次数最少，间隔为1的时候基本有序，最后一次执行插入排序效果最好。
public static void shellInsert(int [] data) { int temp=0; int len=data.length; for(int gap=len/2;gap>0;gap/=2)//最外围的缩小增量 { for(int i=gap;i<len;i++)//间隔排序比如13579 246810 这样的等间隔分组 直接插入排序 { temp=data[i]; int j=i-gap; while(j>-1 && temp<data[j]) { data[j+gap]=data[j]; j-=gap; } data[j+gap]=temp; System.out.println(Arrays.toString(data)); } } }
二、交换排序
1)冒泡排序
相邻的两个数比较大小，直到交换完成。
第一趟把最大的数换到了最右边，第二趟第二大的换到了倒数第二个，每次对前n-i个数进行排序。
public static void bubble(int [] data) { int len=data.length; int cnt=0;//交换次数。假如为0，排序完成跳出 int temp=0; for(int i=1;i<len;i++)//进行n-1趟排序 { for(int j=0;j<len-i;j++) { if(data[j]>data[j+1]) { temp=data[j]; data[j]=data[j+1]; data[j+1]=temp; cnt++; } } if(cnt==0) break; cnt=0; } }
2)快速排序
选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描，将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。
public static void quickSort(int [] data,int left,int right) { if(left<right) { int middle=getMiddle(data, left,right);//获取中间位置 quickSort(data, left, middle-1);//左边排序 quickSort(data, middle+1, right);//右边排序 } } public static int getMiddle(int [] data,int left,int right) { int pivot=data[left];//以左边为基准数 while(left<right)//假如左小于右 { while(left<right && data[right]>pivot)//先在右边找出一个小于基准数的数让在最左边 { right--; } data[left]=data[right]; while(left<right && data[left]<pivot)//再在左边找出一个大于基准数的数放在right的位置上 { left++; } data[right]=data[left]; } data[left]=pivot;//当left==right相等时跳出，然后将基准数放在这个地方 return left; }
三、选择排序
1)简单选择排序
选择排序总共需要n-1次遍历，每次排序都找出最小的值。
public static void selectSort(int [] data) { int len=data.length; for(int i=0;i<len-1;i++)//n-1次排序 { int min=i; for(int j=i+1;j<len;j++)//找出是否存在最小值，且比data[i]小 { if(data[j]<data[min]) min=j; } if(min!=i)//假如有，替换 { int temp=data[i]; data[i]=data[min]; data[min]=temp; } } }
2)堆排序
四、归并排序
1)归并排序
参考：http://blog.csdn.net/pzhtpf/article/details/7560312
归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
//递归实现 public static void mergeSort(int [] data,int low,int high) { int middle=(low+high)/2; if(low<high) { mergeSort(data, low, middle); mergeSort(data, middle+1, high); merge(data, low, middle, high); } } public static void merge(int []data,int low ,int middle,int high) { int temp[]=new int[high-low+1]; int i=low; int j=middle+1; int k=0; while(i<=middle && j<=high) //将分块中排好序 每上一层就是将两个排好序的进行归并 { if(data[i]<data[j]) { temp[k++]=data[i++]; } else { temp[k++]=data[j++]; } } while(i<=middle) { temp[k++]=data[i++]; } while(j<=high) { temp[k++]=data[j++]; } for(int m=0;m<k;m++) { data[low++]=temp[m]; } }
总结
各种内部排序方法的性能比较
| 方法 | 平均时间 | 最坏情况 | 辅助存储 |
|---|---|---|---|
| 简单排序 | O(n^2) | O(n^2) | O(1) |
| 快速排序 | O(nlogn) | O(n^2) | O(nlogn) |
| 堆排序 | O(nlogn) | O(nlogn) | O(1) |
| 归并排序 | O(nlogn) | O(nlogn) | O(n) |
结论：
1)从平均时间而言：快速排序最佳，最坏情况可能不如堆排序和归并排序
2)从算法简单性看：由于直接选择排序、直接插入排序和冒泡排序的算法比较简单，认为是简单排序，都包含在上图中的“简单排序”。对于希尔排序、快速排序、堆排序、归并排序是复杂排序。
3)从稳定性看：直接插入排序、冒泡排序和归并排序是稳定的；而希尔排序、直接选择排序、快速排序和堆排序是不稳定的。
4)从规模看：当n较小时，宜采用简单排序；当n较大时，宜采用改进排序。
综合来看
1)当n较大时，若要求排序稳定，则采用归并排序。
2)当n较大，关键字分布随机，且不要求稳定，则采用快速排序。
3)当n较大，关键字会出现正逆序情形，可采用堆排序或者归并排序。
4)当n较小，记录已接近有序或者随机分布，又要求排序稳定，可采用直接插入排序。
5)当n较小，不要求稳定，可采用直接选择排序。