十大排序算法 （java实现）
转自：https://zhuanlan.zhihu.com/p/80043870
1、冒泡排序（Bubble Sort）
冒泡排序：对每一对相邻的元素比较大小，若顺序错误则交换顺序（正确的顺序由排序方向决定，我们假定数组元素应该从小到大排序）；这样从头到尾操作一遍，最大的元素将会在最后一个（操作的一组元素的最后一个）；对前面未确认顺序的重复以上操作，直到没有元素可操作即排序完成。
1.1 算法描述：
（1）对一组元素，将相邻两个元素比较大小，如果顺序错误则交换顺序；
（2）对每一对相邻元素作同样的操作，从每一组开头一对到最后一对元素，这样每一组元素最后一个元素会是最大；
（3）循环n次（n为数组长度），每次选择前n - 1 - i个（i为第几次循环）元素重复（1）、（2）步骤；
1.2 代码实现：
public static int[] bubbleSort(int[] arr){
int len = arr.length;
if (len == 0) return arr;
for (int i = 0; i < len; i++){
for (int j = 0; j < len - 1 - i; j++){
if (arr[j+1] < arr[j]){
int temp = arr[j+1];
arr[j+1] = arr[j];
arr[j] = temp;
}
}
}
return arr;
}
2、选择排序（Selection Sort）
选择排序：是一种简单直接的排序算法，它的工作原理是：遍历未排序元素，将最小值（或者最大值）和遍历的第一个元素交换位置；然后继续在剩余未排序的元素中重复以上操作，直到将所有元素排序完成。
2.1 算法描述：
（1）初始状态：无序区为R[1..n]，有序区为空；
（2）第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
（3）n-1趟结束，数组有序化了。
2.2 代码实现：
public static int[] selectorSort(int[] arr){
int len = arr.length;
if (len == 0) return arr;
for (int i = 0; i < len-1; i++){
int minIndex = i;
//遍历出每趟的最小值
for (int j = i+1; j < len; j++){
if (arr[j] < arr[minIndex]){
minIndex = j;
}
}
//把最小值与每趟第一个元素交换位置
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
return arr;
}
3、插入排序（Insertion Sort）
插入排序：一种简单直观的排序算法。它的工作原理是：通过构建有序序列，依次取未排序序列元素，在有序序列后面从后往前扫描，找到相应位置插入，插入位置后面的元素需要依次外后移动，为新元素提供位置。
3.1 算法描述
（1）从第一个元素开始，可以认为是已经排好序了
（2）取出下一个新元素，依次从后往前扫描；
（3）如果扫描到的元素比新元素大，则将扫描到的元素依次往后移动一个位置；
（4）重复步骤（3）直到扫描到的元素小于等于新元素，则将新元素插入该位置之后；
（5）重复步骤（2）~（4），直到最后一个元素被插入正确的位置。
3.2 代码实现
public static int[] insertionSort(int[] arr){
int len = arr.length;
if (len == 0) return arr;
for (int i = 0;i < len -1; i++){
int curr = arr[i+1]; //这是要插入的新元素
int preIndex = i;
//从后往前扫描有序序列，如果新元素小于等于扫描到的元素，则将被扫描的元素依次后移一个位置，注意不要下标不要越界
while (preIndex >= 0 && arr[preIndex] > curr){
arr[preIndex+1] = arr[preIndex];
preIndex--;
}
//上面的while循环跳出则表示当前preIndex的元素比新元素小或者已经越界，应该把新元素插入preIndex+1位置
arr[preIndex+1] = curr;
}
return arr;
}
4、希尔排序（Shell Sort）
希尔排序：是插入排序的改良版本，又叫缩小增量排序。希尔排序是把记录按下表的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
4.1 算法描述：
在此我们选择增量为gap = length / 2，继续缩小增量gap = gap / 2直到 gap == 1，我们用一个序列来表示这些增量{len/2, (len/2)/2, ....,1} 这种增量序列的选择和证明是一种数学难题，在此选择的增量是比较常见的，也是希尔建议的称之为希尔增量。
先将整个待排序的序列分割为若干个子序列分别进行插入排序，具体如下
（1）选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
（2）按增量序列个数k，对序列进行k 趟排序；
（3）每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
4.2 代码实现：
public static int[] shellSort(int[] arr){
int len = arr.length;
if (len == 0) return arr;
int gap = len / 2; //增量初始值
while (gap > 0){
for (int i = gap; i < len; i++){
//对每个分组进行插入排序
int curr = arr[i];
int preIndex = i - gap;
while (preIndex >= 0 && arr[preIndex] > curr){
arr[preIndex + gap] = arr[preIndex];
preIndex -= gap;
}
arr[preIndex + gap] = curr;
}
gap = gap / 2; //缩小增量，重新分组进行插入排序
}
//gap==1时，将所有序列分为一组进行插入排序
return arr;
}
5、归并排序（Merge Sort）
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
5.1 算法描述：
（1）把长度为n的输入序列分成两个长度为n/2的子序列；
（2）对这两个子序列分别采用归并排序；
（3）将两个排序好的子序列合并成一个最终的排序序列。
5.2 代码实现：
public static int[] mergeSort(int[] arr){
if (arr.length < 2) return arr;
int mid = arr.length / 2;
int[] left = Arrays.copyOfRange(arr, 0 , mid);
int[] right = Arrays.copyOfRange(arr, mid , arr.length);
return merge(mergeSort(left), mergeSort(right));
}
/**
* 将两个有序序列 组合成一个新的有序序列
*/
private static int[] merge(int[] left, int[] right){
int[] result = new int[left.length + right.length];
for (int index = 0, i = 0, j = 0; index < result.length; index++){
if (i < left.length && j < right.length){
if (left[i] <= right[j]) {
result[index] = left[i++];
} else if (left[i] > right[j]) {
result[index] = right[j++];
}
} else {
if (i >= left.length) result[index] = right[j++];
else if (j >= right.length) result[index] = left[i++];
}
}
return result;
}
未完待续。。。
