冒泡排序
排序思想： 是相邻元素之间的比较和交换，两重循环O(n2)；所以，如果两个相邻元素相等，是不会交换的。所以它是一种稳定的排序方法。
private static void bubbleSort(int[] array) {
int temp;
int endNum = array.length - 1;
for (int i = 0; i < endNum; i++) {
for (int j = 0; j < (endNum) - i; j++) {
if (array[j] > array[j + 1]) {
temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
}
快速排序
从数列中挑出一个元素，称为“基准” 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分割之后，该基准是它的最后位置。这个称为分割（partition）操作。递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。
private static void quickSort(int[] array, int start, int end) {
if (start < end) {
int base = array[start];
int temp;
int i = start;
int j = end;
do {
while (array[i] < base && i < end) {
i++;
}
while (array[j] > base && j > start) {
j--;
}
if (i <= j) {
temp = array[i];
array[i] = array[j];
array[j] = temp;
i++;
j--;
}
} while (i <= j);
if (start < j) {
quickSort(array, start, j);
}
if (end > i) {
quickSort(array, i, end);
}
}
}
选择排序
在未排序序列中找到最小元素，存放到排序序列的起始位置再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。以此类推，直到所有元素均排序完毕。
private static void selectSort(int[] array) {
int temp, length = array.length;
for (int i = 0; i < length; i++) {
int k = i;
for (int j = length - 1; j > i; j--) {
if (array[j] < array[k]) {
k = j;
}
}
temp = array[k];
array[k] = array[i];
array[i] = temp;
}
}
插入排序
从第一个元素开始，该元素可以认为已经被排序取出下一个元素，在已经排序的元素序列中从后向前扫描，如果该元素（已排序）大于新元素，将该元素移到下一位置，重复步骤3，直到找到已排序的元素小于或者等于新元素的位置，将新元素插入到该位置中，重复步骤2。
private static void insertSelect(int[] array) {
int length = array.length, temp, j;
for (int i = 1; i < length; i++) {
temp = array[i];
for (j = i; j > 0 && temp < array[j - 1]; j--) {
array[j] = array[j - 1];
}
array[j] = temp;
}
}
归并排序
申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列，设定两个指针，最初位置分别为两个已经排序序列的起始位置，比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置，重复步骤3直到某一指针达到序列尾，将另一序列剩下的所有元素直接复制到合并序列尾。
private static void mergeSort(int[] array, int left, int right) {
int t = 1;// 每组元素个数
int size = right - left + 1;
while (t < size) {
int s = t;// 本次循环每组元素个数
t = 2 * s;
int i = left;
while (i + (t - 1) < size) {
merge(array, i, i + (s - 1), i + (t - 1));
i += t;
}
if (i + (s - 1) < right)
merge(array, i, i + (s - 1), right);
}
}
/**
* 归并算法实现
*
* @param array
* @param low 低位
* @param mid 中位
* @param high 高位
*/
private static void merge(int[] array, int low, int mid, int high) {
int i = low;
int j = mid + 1;
int k = 0;
int[] tmpArray = new int[high - low + 1];
while (i <= mid && j <= high) {
if (array[i] <= array[j]) {
tmpArray[k] = array[i];
i++;
} else {
tmpArray[k] = array[j];
j++;
}
k++;
}
while (i <= mid) {
tmpArray[k] = array[i];
i++;
k++;
}
while (j <= high) {
tmpArray[k] = array[j];
j++;
k++;
}
for (k = 0, i = low; i <= high; i++, k++) {
array[i] = tmpArray[k];
}
}
希尔排序
希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比o(n^2)好一些。由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。
public static void shellSort(int[] array) {
int increment = 12;
do {
increment = increment / 3 + 1;
shellPass(array, increment);
} while (increment > 1);
}
private static void shellPass(int[] array, int d) {
for (int i = d; i < array.length; i++) {
int temp = array[i];
int j = i - d;
while (j >= 0 && array[j] > temp) {
array[j + d] = array[j];
j -= d;
}
array[j + d] = temp;
}
}
