冒泡排序
思想就是小的数不停地往上（前）冒，程序实现是第i轮从后往前依次比较相邻两数大小，如果小的数在靠后位置就交换两数，这样这一轮最小的数就冒泡到了i的位置。
public static void bubbleSort(int[] a){
for(int i = 0; i < a.length - 1; ++i){
for(int j = a.length - 1; j > i; --j){
if(a[j] < a[j-1]){
int temp = a[j];
a[j] = a[j-1];
a[j-1] = temp;
}
}
}
}
开始我对冒泡排序的理解其实是下沉排序的思想，于是顺手写了个下沉排序：
public static void sinkSort(int[] a){
for(int i = 0; i < a.length - 1; ++i){
for(int j = 0; j < a.length - i - 1; ++j){
if(a[j] > a[j+1]){
int temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
}
选择排序
我个人认为最好理解最好实现的一种排序算法，思想就是第i轮从未排序的序列中找到最小的，跟第i个数交换。
public static void selectSort(int[] a){
for(int i = 0; i < a.length - 1; ++i){
int min = a[i], minIndex = i;
for(int j = i+1; j < a.length; ++j){
if(a[j] < min){
min = a[j];
minIndex = j;
}
}
if(minIndex != i){
int temp = a[i];
a[i] = min;
a[minIndex] = temp;
}
}
}
插入排序
思想就是对前面已排好序的序列，寻找合适的位置插入进去。程序怎么实现插入呢？就是想象把待插入的数挖出来，从后往前寻找，每发现当前位置不是合适的位置就把当前位置的数往后挪一个位置，最后发现合适的位置把待插入的数塞进去。要注意的是j开始的位置就是待插入数位置的前一个，并且每次发现不合适要减一，所以最后发现合适位置时应该+1回到当前位置。
public static void insertSort(int[] a){
for(int i = 1; i < a.length; ++i){
int j = i - 1;
int temp = a[i];
while(j >= 0 && temp < a[j]){
a[j+1] = a[j--];
}
a[++j] = temp;
}
}
归并排序
（二路归并）就是（递归）将数组平分成两部分，每部分实现有序，再把两数组合并。在合并时需要用一个新数组来存储合并结果，所以需要额外O(n)空间。
public static void merge(int[] a, int start, int mid, int end){
int[] temp = new int[end - start + 1];
int i = start, j = mid+1, k = 0;
while(i <= mid && j <= end){
if(a[i] < a[j]){
temp[k++] = a[i++];
}else{
temp[k++] = a[j++];
}
}
while(i <= mid){
temp[k++] = a[i++];
}
while(j <= end){
temp[k++] = a[j++];
}
for(i = start; i <= end; ++i){
a[i] = temp[i-start];
}
}
public static void mergeSort(int[] a, int start, int end){
if(start < end){
int mid = (end - start)/2 + start;
mergeSort(a,start,mid);
mergeSort(a,mid+1,end);
merge(a,start,mid,end);
}
}
快速排序
思想是取一个pivot，让待排序数组变成所有小于pivot的数放pivot左边，其他放右边。程序怎样实现呢？假设pivot是待排序的第一个数，想象给它挖一个坑，从后往前找一个比pivot小的数来填前面这个坑，再从前往后找一个比pivot大于等于的数来填后面的坑；循环进行，最后剩下的一个坑就是pivot位置。
public static void quickSort(int[] a, int start, int end){
if(start < end){
int pivot = a[start];
int left = start, right = end;
while(left < right){
while(left < right && a[right] >= pivot){
--right;
}
if(left < right && a[right] < pivot){
a[left++] = a[right];
}
while(left < right && a[left] < pivot){
++left;
}
if(left < right && a[left] >= pivot){
a[right--] = a[left];
}
}
a[left] = pivot;
quickSort(a,start,left-1);
quickSort(a,left+1,end);
}
}
}
还差一个对我来说比较难的堆排序，抽时间一定要写出来啊！！！！！！！
