今天突然想使用简单的方式，总结一下常见的六种排序算法。
我们都知道，这六种排序算法分别是：冒泡排序、选择排序、插入排序、归并排序、希尔排序、快速排序
这几种排序算法均有自己的特性，我们下面慢慢来一一介绍。
冒泡排序
这个排序是比较常见比较简单的算法，就像水里冒泡一样，将最大或最小的数据依次冒出来。
冒泡排序的流程：
1、找最大或最小。遍历数组，顺序比较，如果找最大，第1位>第2位，则交换位置，然后依次比较和交换，最后，数组的末位就是最大数。
2、找次大或次小。依旧上述流程，不比较倒数第一位，找出第二大或第二小。
3、循环以上操作。
冒泡排序的案例：
原始数组为[8,5,7,2,1,4,5,3,2,4]。
第1轮循环后，数组变为：[5,7,2,1,4,5,3,2,4,8]。
第2轮循环后，数组变为：[5,2,1,4,5,3,2,4,7,8]。
第3轮循环后，数组变为：[2,1,4,5,3,2,4,5,7,8]。
第4轮循环后，数组变为：[1,2,4,3,2,4,5,5,7,8]。
第5轮循环后，数组变为：[1,2,3,2,4,4,5,5,7,8]。
第6轮循环后，数组变为：[1,2,3,2,4,4,5,5,7,8]。
第7轮循环后，数组变为：[1,2,2,3,4,4,5,5,7,8]。
第8轮循环后，数组变为：[1,2,2,3,4,4,5,5,7,8]。
第9轮循环后，数组变为：[1,2,2,3,4,4,5,5,7,8]。
冒泡排序的特点：
原理：双层循环，先找最大再找次大，数据想泡泡一样，一个一个往上浮。
执行效率慢。如果数据长度较长，双层遍历，执行完成的时间复杂度为n^2。
实现简单。主要是数据比较，根据结果进行数据交换。
冒泡排序流程图如下：
冒泡排序代码实现如下：
public static int[] mpSort(int[] array) {
for (int i = 0; i < array.length; i++){
for (int j = 0; j < array.length - 1 - i; j++){ //遍历的个数逐次减少（如15,14,13,......）
if (array[j + 1] < array[j]) { //顺序比较要素（如1和2,2和3,3和4......）
int temp = array[j + 1]; //交换要素的位置
array[j + 1] = array[j];
array[j] = temp;
}
}
}
return array;
}
选择排序
这个排序算法也是比较常见的方法，和冒泡排序相识，但是它是找到对应的数据，然后将数据存放到对应的位置。
选择排序的流程：
1、找最大值所在位置下标。遍历数组，记录最大值所在下标，将最大数与最末端的数据进行交换。
2、找次大值所在位置下标。遍历数组（避开最末），记录最大值所在下标，将最大数与倒数第二进行交换。
3、循环以上操作。逐渐减少遍历数组的长度。
选择排序的案例：
原始数组为[8,5,7,2,1,4,5,3,2,4]。
第1轮循环后，数组变为：[4,5,7,2,1,4,5,3,2,8]。
第2轮循环后，数组变为：[4,5,2,2,1,4,5,3,7,8]。
第3轮循环后，数组变为：[4,3,2,2,1,4,5,5,7,8]。
第4轮循环后，数组变为：[4,3,2,2,1,4,5,5,7,8]。
第5轮循环后，数组变为：[4,3,2,2,1,4,5,5,7,8]。
第6轮循环后，数组变为：[1,3,2,2,4,4,5,5,7,8]。
第7轮循环后，数组变为：[1,2,2,3,4,4,5,5,7,8]。
第8轮循环后，数组变为：[1,2,2,3,4,4,5,5,7,8]。
第9轮循环后，数组变为：[1,2,2,3,4,4,5,5,7,8]。
选择排序的特点：
原理：双层循环，先找最大再找次大，与冒泡的差异是找到后再移动。
执行效率慢。如果数据长度较长，双层遍历，执行完成的时间复杂度为n^2。
实现简单。主要是先比较选择到指定数据，再做数据交换。
流程如下：
具体代码实现如下：
public static int[] xzSort(int[] 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;
}
插入排序
这个排序算法也是比较常见的方法，数组中遍历，当前要素往前插入到属于自己的位置（前面小于等于，后面大于）。
插入排序的流程：
1、取下标0数据，往前比较，前面无元素，则结束。
2、取下标1数据，往前比较，如果小于前面，则交换，大于等于则结束。
3、继续遍历取数据，往前比较。
插入排序的案例：
原始数组为[8,5,7,2,1,4,5,3,2,4]。
第1轮循环后，取出8，前面无元素，数组变为：[8,5,7,2,1,4,5,3,2,4]。
第2轮循环后，取出5，前面有元素，进行比较和移动，数组变为：[5,8,7,2,1,4,5,3,2,4]。
第3轮循环后，取出7，前面有元素，进行比较和移动，数组变为：[5,7,8,2,1,4,5,3,2,4]。
第4轮循环后，取出2，前面有元素，进行比较和移动，数组变为：[2,5,7,8,1,4,5,3,2,4]。
第5轮循环后，取出1，前面有元素，进行比较和移动，数组变为：[1,2,5,7,8,4,5,3,2,4]。
第6轮循环后，取出4，前面有元素，进行比较和移动，数组变为：[1,2,4,5,7,8,5,3,2,4]。
第7轮循环后，取出5，前面有元素，进行比较和移动，数组变为：[1,2,4,5,5,7,8,3,2,4]。
第8轮循环后，取出3，前面有元素，进行比较和移动，数组变为：[1,2,3,4,5,5,7,8,2,4]。
第9轮循环后，取出2，前面有元素，进行比较和移动，数组变为：[1,2,2,3,4,5,5,7,8,4]。
第10轮循环后，取出4，前面有元素，进行比较和移动，数组变为：[1,2,2,3,4,4,5,5,7,8]。
插入排序的特点：
原理：遍历数组，数据往前比较移动数据。
执行效率，高于冒泡和选择排序，其时间复杂度为O(n^(1-2))。
实现想较与冒泡和选择会复杂一点，主要也是数据比较和交换，比较的数量是逐渐增加的。
插入排序流程图：
插入排序代码实现：
public static int[] insertionSort(int[] array) {
int current;
for (int i = 0; i < array.length - 1; i++) {
current = array[i + 1]; //获取当前遍历数据（第2位开始）
int preIndex = i; //获取前一位的下标
while (preIndex >= 0 && current < array[preIndex]) { //当前数据与前一位数据的比较（如果小于，则交换）
array[preIndex + 1] = array[preIndex]; //大的数据往后移动一位，给前面数据腾位置
preIndex--; //减少下标，继续比较
}
array[preIndex + 1] = current; //将当前数据插入到对应位置
}
return array;
}
归并排序
这个排序方法，思想挺好的，主要是分治算法和递归算法的结合，也是使用空间换时间的方式。
归并排序的流程：
1、数组先根据长度对半分成两个数组。再递归分别对这两个数组进行归并排序。
2、递归后，数组分割到最后一个元素一个数组，这样每个数组都是认为排好序的了。
3、返回的两个数组进行合并，合并后的数组也是排好序的。
4、完成上述的先分后治，即可完成数组的排序。
归并排序的案例：
原始数组为[8, 5, 7,2,1,4,5,3, 2, 4]。
第1次分递：[8, 5, 7,2,1]和[4,5,3, 2, 4]。
第2次分递：[8, 5, 7]和[2,1]和[4,5,3]和[2, 4]。
第3次分递：[8, 5]和[7]和[2]和[1]和[4,5]和[3]和[2]和[ 4]。
第4次分递：[8]和[5]和[7]和[2]和[1]和[4]和[5]和[3]和[2]和[4]。
第1次回归：[5,8]和[7]和[1,2]和[4,5]和[3]和[2,4]。
第2次回归：[5,7,8]和[1,2]和[3,4,5]和[2,4]。
第3次回归：[1,2,5,7,8]和[2,3,4,4,5]。
第4次回归：[1,2,2,3,4,4,5,5,7,8]。
归并排序的特点：
原理：递归分割，回归合并。
执行效率，明显高于前面几种（没有双层循环），其时间复杂度为O(n log n)，但是空间消耗却远远高于前面几种。
实现较为复杂，主要先递归分拆数组，在回归时合并已经排好序的两个数组。
归并排序流程图：
归并排序代码实现：
public static int[] gbSort(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(gbSort(left), gbSort(right)); //先递归，再合并排序
}
/**
* 归并排序—合并两个排好序的数组
*/
public 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)
result[index] = right[j++];
else if (j >= right.length)
result[index] = left[i++];
else if (left[i] > right[j])
result[index] = right[j++];
else
result[index] = left[i++];
}
return result;
}
希尔排序
这个排序方法，挺有意思的排序算法，它是不断缩小“步宽”进行分组插入排序，最终完成排序。
希尔排序的流程：
1、获取第一轮步宽。数组长度除以2。例如原来数组为[8, 5, 7,2,1,4,5,3, 2, 4]。长度为10，则步宽为10/2=5。
2、按步宽进行分组比较。也就是下标0和小标5进行比较，下标1和下标6进行比较，排序后数组的状态[4, 5, 3,2,1,8,5,7, 2, 4]。
3、缩小步宽。数组长度除以2再除以2。例子的步宽=10/2/2=5/2=2。
4、按步宽进行分组比较。也就是下标0、2、4、6、8为一组。1、3、5、7、9为一组，组内进行排序，排序后结果为：[1,2,2,4,3,5,4,7,5,8]。
5、缩小步宽。数组长度除以2再除以2再除以2。例子的步宽=10/2/2/2=5/2/2=2/2=1。
6、按步宽进行分组比较。也就是下标0、1、2、3、4、5、6、7、8、9为一组，组内排序，排序后结果为：[1,2,2,3,4,4,5,5,7,8]
希尔排序的案例：
原始数组：[8, 5, 7,2,1,4,5,3, 2, 4]
第1轮步宽 = 数组长度/2 ，也就是5，再进行组内排序。
第2轮步宽 = 数组长度/4 ，也就是2，再进行组内排序。
第3轮步宽 = 数组长度/8 ，也就是1，再进行组内排序。
步宽为1后，数组的数据完成了最后的排序。
希尔排序的特点：
原理：对数组内的数据进行分组，组内排序，分组粒度不断缩小。
执行效率，明显高于前面几种，其时间复杂度为O(n^1.3)。
实现较为复杂，主要先分组再排序，再分组再排序，知道步宽为0。
对于排序数据较多的情况比较适用，因为步宽是指数型减少。
流程如下：
具体代码实现如下：
public static int[] xeSort(int[] array) {
int len = array.length;
int temp, gap = len / 2;
while (gap > 0) {
for (int i = gap; i < len; i++) {
temp = array[i];
int preIndex = i - gap;
while (preIndex >= 0 && array[preIndex] > temp) {
array[preIndex + gap] = array[preIndex];
preIndex -= gap;
}
array[preIndex + gap] = temp;
}
gap /= 2;
}
return array;
}
快速排序
这个排序方法，理解起来挺绕的，值得学习一下，主要采用双指针加一个基数的方式。
快速排序的流程：
1、数组中取一个基数，一般都第1位。
2、数组的头尾各一个指针分别是i和j。也就是从数组的两端分别往中心遍历。
3、分别将i和j的值与基数进行比较，小在左，大在右，先右后左循环遍历。
4、遍历的停止条件是i和j相邻，基数存入最后被移动数据的位置。。
5、以基数分割数组，每个数组分别继续以上操作。
快速排序的案例：
原始数组：[23,45,17,11,13,89,72,26,3,17,11,13]
选择一个基数：23。
双指针遍历完成后，数组为[13,11,17,11,13,17,3,23,26,72,89,45]。
分隔数据组为两个数组，再分别进行快速排序[13,11,17,11,13,17,3,23]和[26,72,89,45]。
快速排序的特点：
原理：对数组内的数据基数比较，分割数组，递归继续快速排序。
执行效率，高于前面几种，其时间复杂度为O(nlogn)。
实现较为复杂，主要先选基数再比较分类移动，再分割后递归，结束条件？。
快速排序流程图：
快速排序代码实现：
public static void ksSort() {
int arr[] = {72,6,57,88,60,42,83,73,48,85};
int low = 0;
int high = arr.length-1;
ksSort(arr,low,high);
}
private static void ksSort(int[] arr, int low, int high) {//
if(low < high){
int index = partition(arr,low,high); //分区操作，将一个数组分成两个分区，返回分区界限索引
ksSort(arr,low,index-1); //对左分区进行快排
ksSort(arr,index+1,high); //对右分区进行快排
}
}
private static int partition(int[] arr, int low, int high) {
int i = low; //指定左指针i
int j= high; //指定右指针j
int x = arr[low]; //将第一个数作为基准值
while(i<j){ //前后指针未相遇
//1.从右向左移动j，找到小于等于基准值的值 arr[j]
while(arr[j]>=x && i<j){
j--;
}
//2.将右侧找到小于等于基准数的值加入到左边的位置， 左指针想中间移动一个位置i++
if(i<j){
arr[i] = arr[j];
i++;
}
//3.从左向右移动i，找到第一个大于基准值的值 arr[i]
while(arr[i]<x && i<j){
i++;
}
//4.将左侧找到的大于基准值的值加入到右边的j位置，右指针向中间移动一个位置 j--
if(i<j){
arr[j] = arr[i];
j--;
}
}
arr[i] = x; //基数的最后位置
return i; //返回基准值的位置索引，用于分割数组
}
计数排序
这个排序方法，对数组中的重复数据进行计数，我们来看看这个算法的实现。
计数排序的流程：
1、确定数组中最大数和最小数，例如：最大数89，最小数3
2、计算基础数0-最小值，并新建临时数组，数组长度=最大数-最小数+1，上面例子结果为：基础值 = 0-3 = -3，数组长度 = 89-3+1=87。
3、遍历原始数组，在临时数组中进行计数（值为下标，通过基础数进行调整）。例如：最小数3的计数为：下标（3 - 基础值），数组的值加1
4、遍历临时数组，根据数组的值和下标位置和基础数进行更新数组。
计数排序的案例：
原始数组：[23,45,17,11,13,89,72,26,3,17,11,13]
确定最大最小数：最大数=89，最小数=3。
基础值 = 0-3 = -3，数组长度 = 89-3+1=87。
遍历计算临时数组。
遍历临时数组，根据下标和计数进行更新排序。
计数排序的特点：
重复数据的较多，最大值和最小值差异不大的数组进行该排序算法，该算法比较有利。
数据的差异较大，重复数据较少的数组不利于该算法，比较消耗临时数组的内存。
计数排序流程图：
计数排序代码实现：
public static int[] CountingSort(int[] array) {
int min = array[0], max = array[0];
//1、找到数组中最大数和最小数
for (int i = 1; i < array.length; i++) {
if (array[i] > max)
max = array[i];
if (array[i] < min)
min = array[i];
}
//2、计算基础数（大于0或者小于0均能处理），并新建临时数组，长度=最大数-最小数+1
int bias = 0 - min;
int[] bucket = new int[max - min + 1];
Arrays.fill(bucket, 0);
//3、遍历原始数组，在临时数组中进行计数（值为下标，通过基础数进行调整）
for (int i = 0; i < array.length; i++) {
bucket[array[i] + bias]++;
}
//4、遍历临时数组，根据数组的值和下标位置和基础数进行更新数组
int index = 0;
for (int i = 0; i < bucket.length; i++) {
if (bucket[i] != 0) {
while (bucket[i] > 0) {
array[index] = i;
index++;
bucket[i]--;
}
}
}
return array;
}
桶排序
这个排序方法，要根据计数排序来说，它其实是计数排序的改良版，我们来看看这个算法的实现。
桶排序的流程：
1、确定数组中最大数和最小数，例如：最大数10000，最小数1
2、确定每个桶的容量，例如为1000个。
3、确定桶的数量，例如桶数量 = (10000 -1)/1000 + 1= 10。
4、递归每个桶的数据，进行排序，并且桶容量为上个迭代的十分之一。
桶排序的案例：
原始数组：[23,45,17,11,13,89,72,26,3,17,11,13]
确定最大最小数：最大数=89，最小数=3。
确定桶容量：桶容量=10。
计算获得桶数量 = (89 - 3)/10 + 1 = 9。
遍历原始数组，分配到各个桶中：
桶0：{3}，桶1：{17,11,13,17,11,13}，桶2：{23,26}，桶3：{}，桶4：{45}，桶5：{}，桶6：{}，桶7：{72}，桶8：{89}
将每个桶分别再进行桶排序，继续上述操作。注意桶容量/10。
桶排序的特点：
与计数排序相对比，该排序的桶的数量较少。
对于数组的最大最小值差异很大时，可以减少内存的消耗。（差异10000，计数排序需要10000容量的数组，桶排序需要动态数组即可）
对于数组的最大最小值差异不大时，也可以快速完成排序。（差异为10，计数排序需求10容量的数组，桶排序需要10个List即可）
桶排序流程图：
桶排序的代码实现：
/**
* 桶排序
* @param array 原始数组
* @param bucketSize 桶容量，例如设置为10
*/
public static ArrayList<Integer> tSort(ArrayList<Integer> array, int bucketSize) {
ArrayList<Integer> resultArr = new ArrayList<>();
//1.找到最大值最小值
int max = array.get(0), min = array.get(0);
for (int i = 0; i < array.size(); i++) {
if (array.get(i) > max)
max = array.get(i);
if (array.get(i) < min)
min = array.get(i);
}
//2.初始化桶结构
int bucketCount = (max - min) / bucketSize + 1; //计算桶的数量
ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketCount);
for (int i = 0; i < bucketCount; i++) {
bucketArr.add(new ArrayList<Integer>());
}
//3.遍历原始数据，并存入到相应的桶中
for (int i = 0; i < array.size(); i++) {
int tIndex = (array.get(i) - min) / bucketSize;
ArrayList<Integer> temp = bucketArr.get(tIndex );
temp.add(array.get(i));
}
//4.遍历桶，将桶内数据进行排序，然后还原到数组
for (int i = 0; i < bucketCount; i++) { //遍历桶列表
ArrayList<Integer> temp = bucketArr.get(i); //获取当前桶
if (bucketSize == 1) { //每个桶的最大容量，只有一个要素，那么遍历取出每个数据结果就是排序后的结果
for (int j = 0; j < temp.size(); j++){ //遍历桶，结果就是顺序的
Integer val = bucketArr.get(i).get(j);
resultArr.add(val );
}
} else { //桶容量大于1，递归排序后，还原到数组中
ArrayList<Integer> tems = tSort(temp,bucketSize/10);
for (int j = 0; j < tems.size(); j++)
resultArr.add(temp.get(j));
}
}
return resultArr;
}
