今天理理排序算法
算法最好最坏平均空间复杂度什么情况下发挥最好什么情况下发挥最坏稳定属于什么排序直接插入排序O(n)O(n2)O(n^2)1初始正序初始反序√插入排序二分插入排序O(n^2)O(n)O(n^2)1n比较大n小，初始排好序√插入排序希尔排序O(nlogn)1×插入排序简单选择排序O(n^2)1×选择排序堆排序O(nlogn)1×选择排序冒泡排序O(n)O(n^2)O(n^2)1初始正序初始反序√交换排序快速排序O(nlogn)O(logn)n较大时序列基本有序时×交换排序归并排序O(nlogn)O(n)一般用于对总体无序，但是各子项相对有序的数列√基数排序O(d(n+r)),d为位数，r为基数√表格目前先这样，还有可以完善的地方。
总结：
一、稳定性:
稳定：冒泡排序、插入排序、归并排序和基数排序
不稳定：选择排序、快速排序、希尔排序、堆排序
二、平均时间复杂度
O(n^2):直接插入排序，简单选择排序，冒泡排序。
在数据规模较小时（9W内），直接插入排序，简单选择排序差不多。当数据较大时，冒泡排序算法的时间代价最高。性能为O(n^2)的算法基本上是相邻元素进行比较，基本上都是稳定的。
O(nlogn):快速排序，归并排序，希尔排序，堆排序。
其中，快排是最好的， 其次是归并和希尔，堆排序在数据量很大时效果明显。
三、排序算法的选择
1.数据规模较小
（1）待排序列基本序的情况下，可以选择直接插入排序；
（2）对稳定性不作要求宜用简单选择排序，对稳定性有要求宜用插入或冒泡
2.数据规模不是很大
（1）完全可以用内存空间，序列杂乱无序，对稳定性没有要求，快速排序，此时要付出log（N）的额外空间。
（2）序列本身可能有序，对稳定性有要求，空间允许下，宜用归并排序
3.数据规模很大
（1）对稳定性有求，则可考虑归并排序。
（2）对稳定性没要求，宜用堆排序
4.序列初始基本有序（正序），宜用直接插入，冒泡
快速排序（最爱考，最爱用）
public void quickSort(int[] a, int low, int high) { if(low<high){ //如果不加这个判断递归会无法退出导致堆栈溢出异常 int middle = getMiddle(a,low,high); quickSort(a, low, middle-1); quickSort(a, middle+1, high); } } //比基准元素小的放到基准元素的左边，大的放到右边 private int getMiddle(int[] a, int low, int high) { int pivot = a[low];//基准元素 while(low<high){ while(low<high && a[high]>=pivot ){ high--; } if(low<high) a[low++] = a[high]; while(low<high && a[low]<=pivot ){ low++; } if(low<high) a[high--] = a[low]; } a[low] = pivot ; return low; }冒泡排序：
public void bubbleSort(int[] a){ for (int i = 0; i < a.length; i++) { for(int j = 0; j<a.length-i-1; j++){ //这里-i主要是每遍历一次都把最大的i个数沉到最底下去了，没有必要再 //替换了 if(a[j]>a[j+1]){ int temp = a[j]; a[j] = a[j+1]; a[j+1] = temp; } } } }还有好几个，以后再写吧。。。。待续
