最近回顾了一下排序算法，发现有些算法还是很绕的，重新梳理一遍，总结如下
很多算法已经忘了，还能流利的写出来的就只有冒泡和选择了，其他排序都是先回顾了一下算法，然后才边调试边写的 其中的基数排序。。感觉很少用，暂时没有梳理，后面再补充
##插入排序 分为直接插入和希尔排序，希尔其实就是插入排序的增量版 ###直接插入：
/**
* 插入排序(升序)
* 维护一个有序列，每次新增元素插入到有序列的某位置使有序列仍有序，直到排序结束
*/
public static int[] insertSort(int[] numbers) {
//若数组为空，或数组的长度为0或1，直接返回
if (numbers == null || numbers.length <= 1) {
return numbers;
}
//假设数组的第一个元素是有序的，从第二个元素开始处理
for (int i = 1; i < numbers.length; i++) {
//表示要插入的位置下标
int j;
//表示当前要插入的元素
int temp = numbers[i];
for (j = i; j > 0; j--) {
//如果当前处理的元素位置比前一个元素小，则前一个元素后移一位
if (temp < numbers[j - 1]) {
numbers[j] = numbers[j - 1];
} else {
//直到找到一个位置当前元素不小于它
break;
}
}
//将当前待插入的元素插入到不小于它的位置
numbers[j] = temp;
}
return numbers;
}
###希尔排序：
/**
* 希尔排序（升序）
* 希尔排序是指，先用2来进行分组，分为n/2组，每组2个数字，进行直接插入排序
* 进而分为n/2/2...直到最后一次分组，只有一个组，然后整体有序
*
* @param numbers
* @return
*/
public static int[] shellSort(int[] numbers) {
//若数组为空，或数组的长度为0或1，直接返回
if (numbers == null || numbers.length <= 1) {
return numbers;
}
//gap为步长
for (int gap = numbers.length / 2; gap > 0; gap /= 2) {
//共分为i组
for (int i = 0; i < gap; i++) {
//第i组的下一个元素为i+gap
for (int j = i + gap; j < numbers.length; j += gap) {
int k;
int temp = numbers[j];
for (k = j; k >= gap; k -= gap) {
if (temp <= numbers[k - gap]) {
numbers[k] = numbers[k - gap];
} else {
break;
}
}
numbers[k] = temp;
}
}
}
return numbers;
}
##交换排序 分为冒泡和快排 冒泡就是两两比较，小的向前，直到一轮后最小的数到了第一位，然后开始第二轮，次小数到第二位... 快排是选第一个数位基准，用两个下标分别指向头尾，用尾下标开始和基准数比较，若小于基准，则交换两个下标对应的数，否则下标递减；然后用头下标与基准比较，若大于基准，则交换两个下标对应的数，否则下标递增...直到两下标相等，再分别对前半段和后半段重复上述操作 ##冒泡
/**
* 冒泡排序
* 从第最后一个数开始，向前每两个做比较，a>b交换，直到第一个数，这样，最小的数就换到了第一位；
* 再从第最后一个数开始重复上述步骤，直到第二个数...
* 最终整个数组有序
*
* @param numbers
* @return
*/
public static int[] popSort(int[] numbers) {
if (numbers == null || numbers.length <= 1) {
return numbers;
}
for (int i = 0; i < numbers.length; i++) {
for (int j = numbers.length - 1; j > i; j--) {
if (numbers[j] < numbers[j - 1]) {
swap(numbers, j, j - 1);
}
}
}
return numbers;
}
##快排
/**
* 快速排序
* 有两个游标a,b分别指向数组头尾，用arr[a]作为基准
* 先从尾部的游标开始与基准作比较，若小于基准，则交换arr[a],arr[b]，否则b--
* 然后从头部开始比较,若大于基准，则交换arr[a],arr[b]，否则a++
* 直到a=b=middle,然后分别将数组0-middle-1位，与middle+1 -arr.length-1位重复上述步骤
*
* @param numbers
* @return
*/
public static int[] quickSort(int[] numbers, int a, int b) {
if (numbers == null || numbers.length <= 1 || a >= b) {
return numbers;
}
int mid = divideForQuick(numbers, a, b);
quickSort(numbers, a, mid - 1);
quickSort(numbers, mid + 1, b);
return numbers;
}
/**
* 快排首轮划分
*
* @param numbers
* @param start
* @param end
*/
private static int divideForQuick(int[] numbers, int start, int end) {
int temp = numbers[start];
while (start < end) {
while (start < end && numbers[end] >= temp) {
end--;
}
if (numbers[end] < temp) {
swap(numbers, start, end);
}
while (start < end && numbers[start] <= temp) {
start++;
}
if (numbers[start] > temp) {
swap(numbers, start, end);
}
}
return end;
}
/**
* 交换
*
* @param num
* @param a
* @param b
*/
private static void swap(int[] num, int a, int b) {
int temp = num[a];
num[a] = num[b];
num[b] = temp;
}
##选择排序 分为选择和堆排序 ###选择排序：
/**
* 选择排序
* 从整列中选一个最小的，与第一位交换
* 然后从第二位开始，重复上述步骤
* 直到全列有序
*
* @param numbers
* @return
*/
public static int[] selectSort(int[] numbers) {
if (numbers == null || numbers.length <= 1) {
return numbers;
}
for (int i = 0; i < numbers.length - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < numbers.length; j++) {
if (numbers[j] < numbers[minIndex]) {
minIndex = j;
}
}
swap(numbers, i, minIndex);
}
return numbers;
}
###堆排序：
/**
* 堆排序
* 按从上到下，从左到右的顺序，将数组想象成完全二叉树
* 则每个子节点的下标/2即为其父节点的下标
* 堆排序就是先将数组调整为大顶堆
* 即从第n/2个节点（最后一颗子树的父节点下标）开始，使每个子树都变成大顶堆
* 直到下标为0的根节点成为整个堆中最大的，将它与第n个数交换
* 然后就只有第0个是不稳定元素，只要调整第0个元素到底部，即可又形成大顶堆，直到全列有序
*
* @param numbers
* @return
*/
public static int[] heapSort(int[] numbers) {
if (numbers == null || numbers.length <= 1) {
return numbers;
}
//从最末端的一颗子树开始构建大顶堆
for (int i = (numbers.length - 1 - 1) / 2; i >= 0; i--) {
bigTopHeap(numbers, i, numbers.length - 1);
}
//此时下标0的数已经是最大的了，交换0与最后一个数，然后将0-last-1再整树构建大顶堆
swap(numbers, 0, numbers.length - 1);
for (int j = numbers.length - 2; j > 0; j--) {
bigTopHeap(numbers, 0, j);
swap(numbers, 0, j);
}
return numbers;
}
/**
* 构建大顶堆，认为传进来的只有第一个元素是不稳定的，即不大于左右叶子
*
* @param numbers 要排序的数组
* @param first 第一个元素下标
* @param last 最后一个元素下标
*/
private static void bigTopHeap(int[] numbers, int first, int last) {
//从最顶部开始,(last-1)/2是最后一个需要调整的子树树根
int i = first;
while (i <= (last - 1) / 2) {
//假设first的左叶子较大
i = i * 2 + 1;
//比较左右叶子，用i记录子树最大值下标
if (i < last && numbers[i] < numbers[i + 1]) {
i++;
}
//若已经是大顶堆，则直接跳出返回
if (numbers[i] < numbers[(i - 1) / 2]) {
break;
}
swap(numbers, i, (i - 1) / 2);
}
}
##归并排序
/**
* 归并排序
* 将一个数组分成两个，然后使每个数组有序，再合并，即为有序数组
* 对分成的两个小数组递归上述操作
*
* @param numbers
* @return
*/
public static int[] mergeSort(int[] numbers) {
if (numbers == null || numbers.length <= 1) {
return numbers;
}
sortForMerge(numbers, 0, numbers.length - 1);
return numbers;
}
/**
* 归并排序的递归方法
*
* @param numbers 要操作的数组
* @param start
* @param end
*/
private static void sortForMerge(int[] numbers, int start, int end) {
if (start >= end) {
return;
}
sortForMerge(numbers, start, (start + end) / 2);
sortForMerge(numbers, (start + end) / 2 + 1, end);
mergeTwoArray(numbers, start, (start + end) / 2 + 1, end);
}
/**
* 归并排序的合并两个数组的算法
*
* @param numbers 要操作的数组
* @param firstStart 第一个序列的起始下标
* @param secondStart 第二个序列的结束下标，第一个序列的结束下标位该值-1
* @param secondEnd 第二个序列的结束下标
*/
private static void mergeTwoArray(int[] numbers, int firstStart, int secondStart, int secondEnd) {
int[] temp = new int[secondEnd - firstStart + 1];
//k是temp的下标
int i = firstStart, j = secondStart, k = 0;
while (i < secondStart && j <= secondEnd) {
if (numbers[i] < numbers[j]) {
temp[k++] = numbers[i++];
} else {
temp[k++] = numbers[j++];
}
}
if (i < secondStart) {
System.arraycopy(numbers, i, temp, k, secondStart - i);
}
if (j <= secondEnd) {
System.arraycopy(numbers, j, temp, k, secondEnd - j + 1);
}
System.arraycopy(temp, 0, numbers, firstStart, temp.length);
}