基本排序
https://www.cnblogs.com/guoyaohua/p/8600214.html
http://www.cnblogs.com/kkun/archive/2011/11/23/2260312.html
1、冒泡排序（Bubble Sort）
比较相邻的元素。如果第一个比第二个大，就交换它们两个；
最佳情况：T(n) = O(n) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(n2)
/**
* 冒泡排序
*
* @param array
* @return
*/
public static int[] bubbleSort(int[] array) {
if (array.length == 0)
return array;
for (int i = 0; i < array.length; i++)
//注意：j < array.length - 1 - i
for (int j = 0; j < array.length - 1 - i; j++)
if (array[j + 1] < array[j]) {
int temp = array[j + 1];
array[j + 1] = array[j];
array[j] = temp;
}
return array;
}
2、选择排序（Selection Sort）
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
最佳情况：T(n) = O(n2) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(n2)
/**
* 选择排序
* @param array
* @return
*/
public static int[] selectionSort(int[] array) {
if (array.length == 0)
return array;
for (int i = 0; i < array.length; i++) {
int minIndex = i;
for (int j = i; j < array.length; j++) {
if (array[j] < array[minIndex]) //找到最小的数
minIndex = j; //将最小数的索引保存
}
int temp = array[minIndex];
array[minIndex] = array[i];
array[i] = temp;
}
return array;
}
3、插入排序（Insertion Sort）
通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
最佳情况：T(n) = O(n) 最坏情况：T(n) = O(n2) 平均情况：T(n) = O(n2)
/**
* 插入排序
* @param array
* @return
*/
public static int[] insertionSort(int[] array) {
if (array.length == 0)
return array;
for (int i = 0; i < array.length - 1; i++) {
int current = array[i + 1];
int preIndex = i;
while (preIndex >= 0 && current < array[preIndex]) {
array[preIndex + 1] = array[preIndex];
preIndex--;
}
array[preIndex + 1] = current;
}
return array;
}
4、希尔排序（Shell Sort）
5、归并排序（Merge Sort）
数据多，内存小，分而治之，归并排序
最佳情况：T(n) = O(n) 最差情况：T(n) = O(nlogn) 平均情况：T(n) = O(nlogn)
/**
* 归并排序
*
* @param array
* @return
*/
public static int[] MergeSort(int[] array) {
if (array.length < 2)
return array;//很重要，出口
int mid = array.length / 2;
int[] left = Arrays.copyOfRange(array, 0, mid);
int[] right = Arrays.copyOfRange(array, mid, array.length);
return merge(MergeSort(left), MergeSort(right));
}
/**
* 归并排序——将两段排序好的数组结合成一个排序数组
*
* @param left
* @param right
* @return
*/
public static int[] merge(int[] left, int[] right) {
int[] result = new int[left.length + right.length];//一个新的数组
int index = 0,i = 0,j = 0;
while (i < left.length && j < right.length){
if (left[i] > right[j])
result[index++] = right[j++];
else
result[index++] = left[i++];
}
while (i >= left.length && index < result.length){
result[index++] = right[j++];
}
while (j >= right.length && index < result.length){
result[index++] = left[i++];
}
return result;
}
