回顾经典，八大算法。

ssss其实早在一年前，对于八大算法就能1个多小时全部复现出来，起初没觉得有什么，但什么随着力扣刷题，发现八大排序算法越来越重要，因此，我觉得有必要对其进行总结，或许已经有很多人对其总结了，不过总是不如自己亲身经历一遍，再复现一遍，算法重要，思维更重要。

ssss排序的分类：

ssdssss①、内部排序：指将需要处理的所有数据都加载到内部存储器（内存）中进行排序

sdsssss②、外部排序法： 数据量过大，无法全部加载到内存中，需要借助外部存储（文件等）进行排序

ssss而我们所说的方法，都是内部方法。

ssss算法的复杂度：时间复杂度，空间复杂度。
sss

冒泡排序

ssss基本思想：对排序序列进行从前向后（下标较小的开始），依次比较相邻元素的值，若逆序则交换，则值较大的元素逐渐从前移向后，就像水底的气泡。每一轮的排序都是找到一个最大值，放到最后面，就和气泡浮出水面一样，一共需要执行N-1轮

ssss在每一轮过程中，都会比较相邻的大小，如果在某一轮发现都没有进行变化，则表明已经排序好了，所以不需要再继续下去。

sssseg：[35,88,16,27,32,4,90,56,79]
ssasdasdasddsdasdss

package com.wwj.sort;

import java.util.Arrays;

public class BubbleSort {
    public static void main(String[] args){

        int[] arr = new int[]{35,88,16,27,32,4,90,56,79};
        int tmp;   //中间变量
        boolean flag = false; //标识变量，标识是否进行过交换
        for(int i =0 ; i< arr.length-1 ; i++){
            for(int j=0 ; j<arr.length-1-i; j++){
                if(arr[j] > arr[j+1]){
                    flag = true;
                    tmp = arr[j+1];
                    arr[j+1] = arr[j];
                    arr[j] = tmp;
                }
            }
            //优化
            if(!flag)     //说明依次交换：一次都没有发生过
                break;
            else
                flag = false;  //重置flag！！！，让起进行第二轮的判断，否则就起不到优化的作用了
        }
        System.out.println(Arrays.toString(arr));
    }
}
==================================================================================================================
结果：[4, 16, 27, 32, 35, 56, 79, 88, 90]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

选择排序

ssss基本思想：其实和冒泡排序差不多，冒泡排序是一轮一轮的相邻两个进行比较，每一轮可以比较出一个最大值，然后一共要执行N-1次，再次可以通过设置flag,用if语句进行判断。而选择排序是设置一个最小值，一般是初始值设为最小值，然后和所有数值进行比较，找出最小的数值放在第一位，然后依次执行N-1次，每一次比较的元素依次递（可以排成从大到小，也可 以排成从小到大）。
ssasdasddasdd
sssseg：[103，34，119，1]
ssdsdsdsdsdsdss

public class selectSort {

    public static void main(String[] args) {
        int[] arr = new int[]{103,34,119,1};
        int minIdx;
        int minVal;
        for(int i=0 ; i< arr.length-1 ; i++){
            minIdx = i;
            minVal = arr[i];
            for(int j=i+1 ; j< arr.length; j++){
                if(minVal>arr[j]){  //记录最大值的下标和值
                    minIdx = j;
                    minVal = arr[j];
                }
            }
            if(minIdx != i){
                arr[minIdx] = arr[i];
                arr[i] = minVal;
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}
==============================================================================================
结果：[1, 34, 103, 119]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

插入排序

ssss基本思想：将一个数组的元素分成一个有序数组，和无序数组，然后将无序数组的数值依次 和有序数组中得数组（也就是第一个数）进行比较，然后放入到有序数组中，最后也要 执行N-1次。

sssseg：[17，3，25，14，20，9]

public class insertSort {
    public static void main(String[] args) {

        int[] arr = new int[]{17,3,25,14,20,9};

        int insertIdx;
        int insertVal;
        for(int i=1 ; i<arr.length ; i++){
            insertIdx = i-1;
            insertVal = arr[i];
            while(insertIdx>=0 && insertVal < arr[insertIdx]){
                arr[insertIdx+1] = arr[insertIdx];
                insertIdx--;
            }
            arr[insertIdx+1] = insertVal;
        }
        System.out.println(Arrays.toString(arr));
    }
}
============================================================================================================
结果：[3, 9, 14, 17, 20, 25]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

希尔排序

ssss本质：实际上也是一种插入排序，只不过在一个序列中，如果较小得在后面，通过插入排序效率并不高，针对这种情况，提出了希尔排序。

ssss基本思想：首先通过一组元素得基本个数，让其除以2，算出第一次排序得增量是多少，然后分成几个组，对各组进行排序.一直持续到增量为1时结束。而对各组进行排序，我们可以通过交换排序，也可以通过希尔排序，每种排序针对不同得情况。

sssseg：[8，9，1，7，2，3，5，4，6，0]
sadasdasdasdsdasdsadasds
ssss①、希尔+交换

public class shellSort {
    public static void main(String[] args) {
        int[] arr= new int[]{8,9,1,7,2,3,5,4,6,0};
        int temp;
        //1、我们首先要进行分组，然后每组比较，一直分到增量为1时，就结束
        for(int gap = arr.length/2 ; gap>0 ; gap/=2 ){   //增量大小，最大为序列长度的1/2，最小为1，逐半减小

            for(int i = gap ; i<arr.length ; i++){  //交换排序的核心，在下标为增量数gap开始，因为此下标前面正好是有gap个数

                for(int j = i-gap; j>=0 ; j-=gap){   //每次和同组的比较也就是前gap个

                    if(arr[j]>arr[j+gap]){
                        temp = arr[j];
                        arr[j] = arr[j+gap];
                        arr[j+gap] = temp;

                    }
                }
            }
        }
        System.out.println("希尔排序和交换排序后的序列为："+ Arrays.toString(arr));
    }
}
===============================================================================================
结果：希尔排序和交换排序后的序列为[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

ssss②、希尔+插入

public class shellSort {
    public static void main(String[] args) {
        int[] arr= new int[]{8,9,1,7,2,3,5,4,6,0};
        int temp;
        //分组
        for(int gap = arr.length/2 ; gap>0 ; gap/=2){
            for(int i=gap ; i<arr.length ; i++ ){
                //插入排序
                int insertVal = arr[i];
                int insertIdx = i-gap;
                while(insertIdx>=0 && insertVal<arr[insertIdx]){
                    arr[insertIdx+gap] = arr[insertIdx];
                    insertIdx-=gap;
                }
                arr[insertIdx+gap] = insertVal;
            }
        }

        System.out.println("希尔排序和插入排序后的序列为："+ Arrays.toString(arr));
    }
}
===============================================================================================
结果：希尔排序和插入排序后的序列为：[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

快速排序

ssss本质：是对冒泡排序的一种改进

ssss基本思想：首先我们要找到他中间索引的值，然后以此分成两个序列，通过编程使左边比右边的数小，然后让两别分别进行递归，这样就达到了排序的效果。

ssss注意：通过while循环找出两边序列各自不符合条件的值，然后交换，但是要考虑：

sdssss1、如果两边全部满足条件呢dsssss2、如果两边有与中间值相等的呢

sssseg：[2,10,8,22,34,5,12,28,21,11]
sdsdsdsssss

public class quickSort {
    public static void main(String[] args) {
        int[] arr = new int[]{2,10,8,22,34,5,21,21,21,11};
        quickSort(arr, 0 , arr.length-1);
        System.out.println("快速排序"+ Arrays.toString(arr));
    }
    private  static void quickSort(int[] arr ,int left , int right ){  //left，right分别代表序列左右两边的值
        int l = left;
        int r = right;
        int pivot = arr[(l+r)/2];   //中轴值
        int tmp;  //中间值

        //首先我们要以中轴值为界，把序列分成两份，保证左边的序列的数值比右边的序列的数值大
        //首先一个死循环
        while (l<r){
            while(arr[l]<pivot)     l++;    // 以中轴值为界
            while(arr[r]>pivot)     r--;   // 以中轴值为界
            if(l>r)    break;  //如果当l>r时，说明此时左边序列的数字小于右边数列的值

            tmp = arr[l];
            arr[l] = arr[r];
            arr[r] = tmp;    //进行互换，但是要注意，前面两个while循环，都取的是<>号，如果是==呢，此时需要改变l,r的值

            if(arr[l] == pivot)   l++;//交换完后，如果左边相等，我们要让l++,原因：1、以便让后面进行递归，2、退出while循环
            if(arr[r] == pivot)   r--;//交换完成后，如果右边相等，我们要让r--，以便让后面进行递归  2、退出whil循环         }
        }
        //如果是根据后面两个if语句退出的while循环，说明r==f,此时我们为了后面的遍历要r++,f--
        if(r==l){ r+=1;l-=1; }
        //向左递归,但是要判别下最左边的下标小于left<r
        if(left<r)      quickSort(arr,left,r);
        //又向递归，但是要判别下最右边的下标大于f,right>f
        if(right>l)     quickSort(arr,l,right);
    }
}
===============================================================================================
结果快速排序[2, 5, 8, 10, 11, 21, 21, 21, 22, 34]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

归并排序

ssss核心思想就是“分治”，“分”的情况比较简单，最后拆成一个元素的序列，“治”的情况比较麻烦，合的时候需要把他们一次一次递归，然后排列。核心为“治”，一共要合并N-1次（N为长度）

ssss分成三个阶段：1、分 2、合 3、复制

sssseg：[2,10,8,22,34,5,21,21,21,11]

public class MergeSort {
    public static void main(String[] args) {
        int arr[] = { 2,10,8,22,34,5,21,21,21,11 };
        int[] tmp = new int[arr.length];
        mergeSort(arr,0,arr.length-1 , tmp);
        System.out.println("归并排序的顺序："+Arrays.toString(arr));

    }
    private static void mergeSort(int[] arr , int left , int right , int[] tmp){
        if(left<right){
            int mid = (left + right)/2;
            mergeSort(arr,left,mid,tmp);
            mergeSort(arr,mid+1,right,tmp);
            merge(arr , left , mid , right ,tmp);
        }
    }
    //合并的方法
    /**
     *
     * @param arr 排序的原始数组
     * @param left 左边有序序列的初始索引
     * @param mid 中间索引
     * @param right 右边索引
     * @param temp 做中转的数组
     */
    public static void merge(int[] arr, int left, int mid, int right, int[] temp) {

        int i = left; // 初始化i, 左边有序序列的初始索引
        int j = mid + 1; //初始化j, 右边有序序列的初始索引
        int t = 0; // 指向temp数组的当前索引
        //(一)
        //先把左右两边(有序)的数据按照规则填充到temp数组
        //直到左右两边的有序序列，有一边处理完毕为止
        while (i <= mid && j <= right) {//继续
            //如果左边的有序序列的当前元素，小于等于右边有序序列的当前元素
            //即将左边的当前元素，填充到 temp数组
            //然后 t++, i++
            if(arr[i] <= arr[j])
                temp[t++] = arr[i++];
            else //反之,将右边有序序列的当前元素，填充到temp数组
                temp[t++] = arr[j++];
        }
        //(二)
        //把有剩余数据的一边的数据依次全部填充到temp
        while( i <= mid)   temp[t++] = arr[i++]; //左边的有序序列还有剩余的元素，就全部填充到temp
        while( j <= right)  temp[t++] = arr[j++]; //右边的有序序列还有剩余的元素，就全部填充到temp
        //(三)
        //将temp数组的元素拷贝到arr
        //注意，并不是每次都拷贝所有
        t = 0;
        int tempLeft = left; //
        //第一次合并 tempLeft = 0 , right = 1 //  tempLeft = 2  right = 3 // tL=0 ri=3
        //最后一次 tempLeft = 0  right = 7
        while(tempLeft <= right) arr[tempLeft++] = temp[t++];
    }
}
==================================================================================================================
结果：归并排序的顺序：[2, 5, 8, 10, 11, 21, 21, 21, 22, 34]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

堆排序

ssss基本思想：堆排序分析的比较好的文章

    //堆排序
    public static void heapSort(int[] arr) {
        //构造大根堆
        heapInsert(arr);
        int size = arr.length;
        while (size > 1) {
            //固定最大值
            swap(arr, 0, size - 1);
            size--;
            //构造大根堆
            heapify(arr, 0, size);
 
        }
 
    }
 
    //构造大根堆（通过新插入的数上升）
    public static void heapInsert(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            //当前插入的索引
            int currentIndex = i;
            //父结点索引
            int fatherIndex = (currentIndex - 1) / 2;
            //如果当前插入的值大于其父结点的值,则交换值，并且将索引指向父结点
            //然后继续和上面的父结点值比较，直到不大于父结点，则退出循环
            while (arr[currentIndex] > arr[fatherIndex]) {
                //交换当前结点与父结点的值
                swap(arr, currentIndex, fatherIndex);
                //将当前索引指向父索引
                currentIndex = fatherIndex;
                //重新计算当前索引的父索引
                fatherIndex = (currentIndex - 1) / 2;
            }
        }
    }
    //将剩余的数构造成大根堆（通过顶端的数下降）
    public static void heapify(int[] arr, int index, int size) {
        int left = 2 * index + 1;
        int right = 2 * index + 2;
        while (left < size) {
            int largestIndex;
            //判断孩子中较大的值的索引（要确保右孩子在size范围之内）
            if (arr[left] < arr[right] && right < size) {
                largestIndex = right;
            } else {
                largestIndex = left;
            }
            //比较父结点的值与孩子中较大的值，并确定最大值的索引
            if (arr[index] > arr[largestIndex]) {
                largestIndex = index;
            }
            //如果父结点索引是最大值的索引，那已经是大根堆了，则退出循环
            if (index == largestIndex) {
                break;
            }
            //父结点不是最大值，与孩子中较大的值交换
            swap(arr, largestIndex, index);
            //将索引指向孩子中较大的值的索引
            index = largestIndex;
            //重新计算交换之后的孩子的索引
            left = 2 * index + 1;
            right = 2 * index + 2;
        }
 
    }
    //交换数组中两个元素的值
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

基数排序(桶排序)

ssss之所以叫做桶排序，是因为分成了10个桶，0-9，这样我们可以从这个序列的各个数值的个位开始放入桶中，然后按顺序取出，组成新出的数组，再按照十位……依次类推，需要执行的次数，就是序列中最大数的位数。

ssss基数排序是空间换时间的经典算法

ssss相同的数值排序本来在前面的排序后也在前面

public class RadixSort {
    public static void main(String[] args) {
        int[] arr = { 53, 3, 542, 748, 14, 214};
        radixSort1(arr); //整体
        System.out.println(Arrays.toString(arr));
    }
    //基数排序，俗称桶排序，基本思想就是：按照个位，十位，百位等分别放入对应得桶中，
    // 然后依次进行排序，所以我们首先要找到一个数组中的最大值，然后用二维数组表达出桶，以及里面对应的数
    private static void radixSort1(int[] arr) {
        int max = arr[0]; //假定第一个数是最大数
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        //得到最大数是几位数
        int maxLength = (max + "").length();
        //10  对应0-9. arr.length对应着我们要排序的数组的元素个数，防止溢出
        int[][] bucket = new int[10][arr.length];
        int[] bucketElementCounts = new int[10];    //存入的是特定位是0~9的个数
        for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
            //(针对每个元素的对应位进行排序处理)， 第一次是个位，第二次是十位，第三次是百位..
            for (int j = 0; j < arr.length; j++) {
                //取出每个元素的对应位的值
                int digitOfElement = arr[j] / n % 10;
                //放入到对应的桶中
                bucket[digitOfElement][bucketElementCounts[digitOfElement]++] = arr[j];
            }
            //按照这个桶的顺序(一维数组的下标依次取出数据，放入原来数组)
            int index = 0;
            //遍历每一桶，并将桶中是数据，放入到原数组
            for (int k = 0; k < bucketElementCounts.length; k++) {
                //如果桶中，有数据，我们才放入到原数组
                if (bucketElementCounts[k] != 0) {
                    //循环该桶即第k个桶(即第k个一维数组), 放入
                    for (int l = 0; l < bucketElementCounts[k]; l++) {
                        //取出元素放入到arr
                        arr[index++] = bucket[k][l];
                    }
                }
                //第i+1轮处理后，需要将每个 bucketElementCounts[k] = 0 ！！！！
                bucketElementCounts[k] = 0;
            }
            System.out.println("第" + (i + 1) + "轮，对个/十/百/...位的排序处理 arr =" + Arrays.toString(arr));
        }
    }
}
==============================================================================================================
结果：
第1轮，对个/十/百/...位的排序处理 arr =[542, 53, 3, 14, 214, 748]
第2轮，对个/十/百/...位的排序处理 arr =[3, 14, 214, 542, 748, 53]
第3轮，对个/十/百/...位的排序处理 arr =[3, 14, 53, 214, 542, 748]
[3, 14, 53, 214, 542, 748]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53