一、冒泡排序（Bubble Sort）
1.1 基本思想：
冒泡排序算是比较简单的排序了。
即对 n 个数进行排序，每次都是由前一个数和后一个数比较，一对一对地比，最后可以将最大的数移到数组的后面，总共循环 n-1 次，完成对数组的排序。
1.2 动图演示
冒泡排序
1.3 代码实现：
/**
* @anthor shkstart
* @create 2020-03-19-15:33
*/
public class Test1 {
public static void main(String[] args) {
int[] arr = new int[]{
65,98,34,16,0,-5,-6,45,39,-44,-99,35,34
};
//外层控制排序的对比的次数，比数组长度少1是因为最后一个数据不用比
for (int i = 0; i < arr.length; i++) {
//-i 是因为排序导最后可以得出一个最大值，就不用参与排序了
for (int j = 0; j < arr.length-1-i; j++){
//比较相邻的两个元素。如果第一个元素比第二个元素打，就交换位置
if (arr[j] > arr[j + 1]){
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + "\t");
}
}
}
二、选择排序（Selection Sort）
2.1 基本思想：
选择排序是由一个数去和全部的数都比较一次，每次选取相对较小的那个数的下标来进行下一次比较，并且不断更新较小的数的下标，一次循环结束，再通过一次交换，把较小的数放在最前面，一共循环 n-1 次。
相对于冒泡排序，比较的次数不变，但数据交换的次数大大减少了。算是冒泡排序的改良版。
2.2 动图演示：
选择排序
2.3 代码演示：
/**
* 选择排序
*
* @author czh
* @create 2020-03-19-21:40
*/
public class selectSort {
public static void main(String[] args) {
int[] arr = new int[]{
65,98,34,16,0,-5,-6,45,39,-44,-99,35,34
};
//外层循环控制循环次数，最后一个数据自动为最大值，所以arr.length-1
for (int i = 0; i < arr.length - 1; i++) {
//用来保存每次比较的最小值的下标
int MinIndex = i;
//内层控制每次的比较，因为前面的数据已经排好
//所以下一次循环就可以跳过，j=i+1
for (int j = i+1; j < arr.length; j++) {
//对比时，遇到比自己小的，就替换下标
if (arr[MinIndex] > arr[j]){
MinIndex = j;
}
}
//一轮对比下来，发现下标发生了改变
//就把下标对应的数据进行替换
if (MinIndex != i){
int temp = arr[i];
arr[i] = arr[MinIndex];
arr[MinIndex] = temp;
}
}
System.out.println("排序后的数据：");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + "\t");
}
}
}
三、插入排序（Insertion Sort）
3.1 基本思想：
首先默认数组中的第一个数的位置是正确的。然后取下一个数，与前面已经排序好的数据从后往前依次比较，如果该数的值比前一个小，就把排序好的数据后移一位。重复该操作，直到找到合适的位置后结束循环，将数据放到找到的位置。
3.2 动图演示：
插入排序
3.3 代码演示：
/**
*
* 插入排序
*
* @author czh
* @create 2020-03-20-8:42
*/
public class insertSort {
public static void main(String[] args) {
int[] arr = new int[]{
65,98,34,16,0,5,-6,45,39,-44,-99,35,34
};
//控制外层循环，因为第一个数据假定是正确的
//所以i的起始值是1
for (int i = 1; i < arr.length; i++) {
int j=i;//用来记录要排序的数的下标，原来的位置
int target = arr[j];//用来记录要排序的数的值
//因为是从后向前比较，所以j-1和j做比较
//j>0 让比较不要跑出范围
while (j>0 && target<arr[j-1]){
arr[j] = arr[j-1]; //发现前一个比自己大，就往前移动一位
j--;//让目标与下一个继续比较
}
//更换目标数的位置
arr[j] = target;
}
System.out.println("排序后的数据：");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + "\t");
}
}
}
四、希尔排序（Shell Sort）
4.1 基本思想：
先将需要排序的数组分为多个子序列，这样每个子序列的元素个数不多，对每个子序列进行直接插入排序。完成后，再对整个数组进行一次直接排序。希尔排序是直接插入排序的升级版。
4.2 动图演示：
希尔排序
4.3 代码演示：
/**
* @author czh
* @create 2020-03-20-9:40
*/
public class shellSort {
public static void main(String[] args) {
int[] arr = new int[]{
3,65,98,34,-16,0,-5,-6,45,39,-44,-99,35,34
};
//初始增量为数组长度的一半
int k = arr.length / 2;
//while循环控制按增量的值来划分不同的子序列，
//每完成一个增量就减少为原来的一半
while (k>0){
//这其实是升级版的直接插入排序，是对每一个子序列进行直接插入排序
//所以将插入排序的“1”变成“k”
for (int i = k; i < arr.length; i++) {
int j = i;
int target = arr[i];
while (j>=k && target < arr[j-k]){
arr[j] = arr[j-k];
j-=k;
}
arr[j] = target;
}
k/=2;
}
System.out.println("排序后的数据：");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + "\t");
}
}
}
五、归并排序（Merge Sort）
5.1 基本思想：
总体概括就是从上到下递归拆分，然后从下到上逐步合并。
- 递归拆分：先把待排序数组分为左右两个子序列，再分别将左右两个子序列拆分为四个子子序列，以此类推直到最小的子序列元素的个数为两个或者一个为止。
- 逐步合并（一定要注意是从下到上层级合并，可以理解为递归的层级返回）：将最底层的最左边的一个子序列排序，然后将从左到右第二个子序列进行排序，再将这两个排好序的子序列合并并排序，然后将最底层从左到右第三个子序列进行排序..... 合并完成之后记忆完成了对数组的排序操作。
5.2 动图演示：
归并排序
5.3 代码演示（基本思想理解。代码实现不会，参考大佬的代码）：
import java.util.Arrays;
/**
* 归并排序
* 不太会，参考别人的代码的
*
* @author czh
* @create 2020-03-20-10:25
*/
public class test {
public static void main(String[] args) {
int[] arr = {
65,98,34,16,0,-5,-6,45,39,-44,-99,35,34};
mergeSort(arr,0,arr.length-1);
System.out.println(Arrays.toString(arr));
}
/**
* 递归拆分
* @param arr 待拆分数组
* @param left 待拆分数组最小下标
* @param right 待拆分数组最大下标
*/
public static void mergeSort(int[] arr,int left,int right){
int mid = (left + right) / 2;//中间下标
if (left < right){
mergeSort(arr, left, mid);//递归拆分左边
mergeSort(arr,mid+1,right);//递归拆分右边
sort(arr,left,mid,right);//合并左右
}
}
/**
* 合并两个有序子序列
* @param arr 待合并数组
* @param left 待合并数组最小下标
* @param mid 待合并数组中间下标
* @param right 待合并数组最大下标
*/
public static void sort(int[] arr,int left,int mid,int right){
int[] temp = new int[right - left + 1];//临时数组，用来保存每次合并之后的结果
int i = left;
int j = mid + 1;
int k = 0;//临时数组的初始下标
//循环能够初步筛选出待合并的了两个子序列中的较小数
while (i<=mid && j<=right){
if (arr[i]<=arr[j]){
temp[k++] = arr[i++];
}else {
temp[k++] = arr[j++];
}
}
//将左边序列中剩余的数放入临时数组
while (i<=mid){
temp[k++] = arr[i++];
}
//将右边序列中剩余的数放入临时数组
while (j<=right){
temp[k++] = arr[j++];
}
//将临时数组中的元素位置对应到真实数组中
for (int m = 0; m < temp.length; m++) {
arr[m+left] = temp[m];
}
}
}
六、快速排序（Quick Sort）
6.1 基本思想：
快速排序也采用了分治的策略，这里引入了‘基准数’的概念。
- 找一个基准数（一般将待排序的数组的第一个数作为基准数）。
- 对数组进行分区，将小于等于基准数的全部放在左边，大于基准数的全部放在右边。
- 重复1，2步骤，分别对左右两个子分区进行分区，一直到各分区只有一个数为止。
6.2 动图演示：
快速排序
6.3 代码演示（基本思想理解，代码实现也是参考别人的代码）：
import java.util.Arrays;
/**
* @author czh
* @create 2020-03-20-14:27
*/
public class test1 {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr= {65,98,34,16,0,-5,-6,45,39,-44};
quickSort(arr,0,9);
System.out.println(Arrays.toString(arr));
}
/**
* 分区过程
* @param arr 待分区数组
* @param left 待分区数组最小下标
* @param right 待分区数组最大下标
*/
public static void quickSort(int[] arr,int left,int right) {
if(left<right) {
int temp=qSort(arr,left,right);
quickSort(arr,left,temp-1);
quickSort(arr,temp+1,right);
}
}
/**
* 排序过程
* @param arr 待排序数组
* @param left 待排序数组最小下标
* @param right 待排序数组最大下标
* @return 排好序之后基准数的位置下标，方便下次的分区
*/
public static int qSort(int[] arr,int left,int right) {
int temp=arr[left];//定义基准数，默认为数组的第一个元素
while(left<right) {//循环执行的条件
//因为默认的基准数是在最左边，所以首先从右边开始比较进入while循环的判断条件
//如果当前arr[right]比基准数大，则直接将右指针左移一位，当然还要保证left<right
while(left<right && arr[right]>temp) {
right--;
}
//跳出循环说明当前的arr[right]比基准数要小，那么直接将当前数移动到基准数所在的位置，并且左指针向右移一位（left++）
//这时当前数（arr[right]）所在的位置空出，需要从左边找一个比基准数大的数来填充。
if(left<right) {
arr[left++]=arr[right];
}
//下面的步骤是为了在左边找到比基准数大的数填充到right的位置。
//因为现在需要填充的位置在右边，所以左边的指针移动，如果arr[left]小于或者等于基准数，则直接将左指针右移一位
while(left<right && arr[left]<=temp) {
left++;
}
//跳出上一个循环说明当前的arr[left]的值大于基准数，需要将该值填充到右边空出的位置，然后当前位置空出。
if(left<right) {
arr[right--]=arr[left];
}
}
//当循环结束说明左指针和右指针已经相遇。并且相遇的位置是一个空出的位置，
//这时候将基准数填入该位置，并返回该位置的下标，为分区做准备。
arr[left]=temp;
return left;
}
}
七、堆排序（Heap Sort）
7.1 基本思想：
堆是一种特殊的完全二叉树，分为大顶堆和小顶堆。
- 大顶堆：每个结点的值都大于它的左右子结点的值，升序排序用大顶堆。
- 小顶堆：每个结点的值都小于它的左右子结点的值，降序排序用小顶堆。
所以，需要将待排序数组构成大顶堆的格式，这时候该堆的顶节点就是最大的值，将其与堆最后一个节点的元素交换。再将剩余的树重新调整成堆，再次对比一轮后，首节点与尾节点交换，重复执行直到只剩下最后一个节点即完成排序。
7.2 动图演示：
堆排序
7.3 代码演示（参考大佬的代码...）：
import java.util.Arrays;
/**
* @author czh
* @create 2020-03-20-14:27
*/
public class test1 {
public static void main(String[] args) {
int[] arr= {72,6,-7,88,0,42,354,83,-73,48,85,7};
heapSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void heapSort(int[] arr) {
if(arr==null) {
return;
}
int len=arr.length;
//初始化大顶堆（从最后一个非叶节点开始，从左到右，由下到上）
for(int i=len/2-1;i>=0;i--) {
adjustHeap(arr,i,len);
}
//将顶节点和最后一个节点互换位置，再将剩下的堆进行调整
for(int j=len-1;j>0;j--) {
swap(arr,0,j);
adjustHeap(arr,0,j);
}
}
/**
* 整理树让其变成堆
* @param arr 待整理的数组
* @param i 开始的结点
* @param j 数组的长度
*/
public static void adjustHeap(int[] arr,int i,int j) {
int temp=arr[i];//定义一个变量保存开始的结点
//k就是该结点的左子结点下标
for(int k=2*i+1;k<j;k=2*k+1) {
//比较左右两个子结点的大小，k始终记录两者中较大值的下标
if(k+1<j && arr[k]<arr[k+1]) {
k++;
}
//经子结点中的较大值和当前的结点比较，比较结果的较大值放在当前结点位置
if(arr[k]>temp) {
arr[i]=arr[k];
i=k;
}else{//说明已经是大顶堆
break;
}
}
arr[i]=temp;
}
/**
* 交换数据
* @param arr
* @param num1
* @param num2
*/
public static void swap(int[] arr, int num1,int num2) {
int temp=arr[num1];
arr[num1]=arr[num2];
arr[num2]=temp;
}
}
八、计数排序（Counting Sort）
8.1 基本思想：
计数排序采用了一种全新的思路，将待排序数组中的最大值+1作为一个临时数组的长度，然后用临时数组记录待排序数组中每个元素出现的次数。最后再遍历临时数组，因为是升序，所以从前往后遍历将临时数组中值>0的数的下标循环取出，依次放入待排序数组中，即可完成排序。计数排序的效率很高，但是实在牺牲内存的前提下，并且有着限制，那就是待排序数组的值必须 限制在一个确定的范围。
8.2 动图演示：
计数排序
8.3 代码演示：
import java.util.Arrays;
/**
效率高，但无法对负数进行排序
* @author czh
* @create 2020-03-20-14:27
*/
public class test1 {
public static void main(String[] args) {
int[] arr= {65,98,34,16,0,45,39,35,34};
countSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void countSort(int[] arr) {
if(arr==null)
return;
int len=arr.length;
//保存待排序数组中的最大值，目的是确定临时数组的长度（必须）
int maxNum=arr[0];
//保存待排序数组中的最小值，目的是确定最终遍历临时数组时下标的初始值（非必需，只是这样可以加快速度，减少循环次数）
int minNum=arr[0];
//for循环就是为了找到待排序数组的最大值和最小值
for(int i=1;i<len;i++) {
maxNum=maxNum>arr[i]?maxNum:arr[i];
minNum=minNum<arr[i]?minNum:arr[i];
}
//创建一个临时数组
int[] temp=new int[maxNum+1];
//for循环是为了记录待排序数组中每个元素出现的次数，并将该次数保存到临时数组中
for(int i=0;i<len;i++) {
temp[arr[i]]++;
}
//k=0用来记录待排序数组的下标
int k=0;
//遍历临时数组，重新为待排序数组赋值。
for(int i=minNum;i<temp.length;i++) {
while(temp[i]>0) {
arr[k++]=i;
temp[i]--;
}
}
}
}
九、桶排序（Bucket Sort）
9.1 基本思想：
桶排序其实就是计数排序的强化版，需要利用一个映射函数首先定义有限个数个桶，然后将待排序数组内的元素按照函数映射的关系分别放入不同的桶里边，现在不同的桶里边的数据已经做了区分，比如A桶里的数要么全部大于B桶，要么全部小于B桶里的数。但是A，B桶各自里边的数还是乱序的。所以要借助其他排序方式（快速，插入，归并）分别对每一个元素个数大于一的桶里边的数据进行排序。最后再将桶里边的元素按照顺序依次放入待排序数组中即可。
9.2 图片展示：
9.3 代码演示（这个也没懂...CP大佬的代码）：
public static void main(String[] args) {
int[] arr= {72,6,57,88,60,42,83,73,48,85};
bucketSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void bucketSort(int[] arr) {
if(arr==null)
return;
int len=arr.length;
//定义桶的个数，这里k的值要视情况而定，这里我们假设待排序数组里的数都是[0,100)之间的。
int k=10;
//用嵌套集合来模拟桶，外层集合表示桶，内层集合表示桶里边装的元素。
List<List<Integer>> bucket=new ArrayList<>();
//for循环初始化外层集合即初始化桶
for(int i=0;i<k;i++){
bucket.add(new ArrayList<>());
}
//循环是为了将待排序数组中的元素通过映射函数分别放入不同的桶里边
for(int i=0;i<len;i++) {
bucket.get(mapping(arr[i])).add(arr[i]);
}
//这个循环是为了将所有的元素个数大于1的桶里边的数据进行排序。
for(int i=0;i<k;i++) {
if(bucket.size()>1) {
//因为这里是用集合来模拟的桶所以用java写好的对集合排序的方法。
//其实应该自己写一个方法来排序的。
Collections.sort(bucket.get(i));
}
}
//将排好序的数重新放入待排序数组中
int m=0;
for(List<Integer> list:bucket) {
if(list.size()>0) {
for(Integer a:list) {
arr[m++]=a;
}
}
}
}
/**
* 映射函数
* @param num
* @return
*/
public static int mapping(int num) {
return num/10;
}
十、基数排序（Radix Sort）
10.1 基本思想：
基数排序就是将待排序的数组拆分成多个关键字进行排序。基数排序的实质是多关键字排序。多关键字排序的思路是将待排数据里德排序关键字拆分成多个排序关键字； 第1个排序关键字，第2个排序关键字，第3个排序关键字......然后，根据子关键字对待排序数据进行排序。
10.2 动图演示：
基数排序
10.3 代码演示（理论理解，实操不懂...参考大佬的代码）：
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr= {720,6,57,88,60,42,83,73,48,85};
redixSort(arr,10,3);
System.out.println(Arrays.toString(arr));
}
public static void redixSort(int[] arr, int radix, int d) {
// 缓存数组
int[] tmp = new int[arr.length];
// buckets用于记录待排序元素的信息
// buckets数组定义了max-min个桶
int[] buckets = new int[radix];
for (int i = 0, rate = 1; i < d; i++) {
// 重置count数组，开始统计下一个关键字
Arrays.fill(buckets, 0);
// 将data中的元素完全复制到tmp数组中
System.arraycopy(arr, 0, tmp, 0, arr.length);
// 计算每个待排序数据的子关键字
for (int j = 0; j < arr.length; j++) {
int subKey = (tmp[j] / rate) % radix;
buckets[subKey]++;
}
for (int j = 1; j < radix; j++) {
buckets[j] = buckets[j] + buckets[j - 1];
}
// 按子关键字对指定的数据进行排序
for (int m = arr.length - 1; m >= 0; m--) {
int subKey = (tmp[m] / rate) % radix;
arr[--buckets[subKey]] = tmp[m];
}
rate *= radix;
}
}
十一、算法总结：
算法对比图：
算法对比
图片名词解释：
- n：数据规模
- k：“桶”的个数
- In-place：占用常数内存，不占用额外内存
- Out-place：占用额外内存
