排序：就是将一组无序的记录序列调整为有序的记录序列。
列表排序：将无序列表变为有序列表

输入：列表
输出：列表

排序方式：升序和降序
内置排序函数：sort
常见排序算法：

lOW B三人组

原地排序
时间复杂度都是O(n^2)

冒泡排序
列表每两个相邻的数，如果前面比后面大，则交换这两个数（升序排列）
一趟排序完成之后，则无序区减少一个数，有序区增加一个数。

从下往上，5和7，5 < 7 交换第二个数是7，则 7和 4比，7大，继续往上交换
重复上面过程，也就是一趟下来，大的数子冒泡上去。
每一趟，最大的数会渐渐冒泡上去。
总共排序算法走了N-1趟。每一趟减少一个数的有序性。

代码的关键点：趟、有序区和无序区 ```java package com.algorithm.demo.sorts;

import com.alibaba.fastjson.JSONObject;

/**

@Author leijs

@date 2022/4/9 */ public class BubbleSort { public static void main(String[] args) {

 int[] array = new int[] {7,2,5,4,1,9,17,11, 12,3};
 sort(array);
 System.out.println("final result:" + JSONObject.toJSONString(array));

} public static void sort(int[] array) {

 // 第i趟
 for (int i = 0; i < array.length; i++) {
     // 每一趟少1，一共是n-1趟
     boolean exchange = false;
     for (int j = 0; j < array.length -i - 1; j++) {
         if (array[j] > array[j+1]) {
             int temp = array[j];
             array[j] = array[j+1];
             array[j+1] = temp;
             exchange = true;
         }
     }
     if (!exchange) {
         return;
     }
     System.out.println(JSONObject.toJSONString(array));
 }

} }


- 时间复杂度：O(n^2)
注意改进的地方：
> 如果没有可以交换的，说明已经不需要排序了。
<a name="eZZp7"></a>
## 选择排序
遍历一遍找到最小的数，再遍历一遍找到一个最小的数，拿出来放到一个新的列表
```java
package com.algorithm.demo.sorts;
import com.alibaba.fastjson.JSONObject;
import com.google.common.collect.Lists;
import java.util.List;
/**
 * @Author leijs
 * @date 2022/4/9
 */
public class SelectSort {
    public static void main(String[] args) {
        List<Integer> array = Lists.newArrayList(7,2,5,4,1,9,17,11, 12,3, 9);
        System.out.println("final result:" + JSONObject.toJSONString(sort(array)));
    }
    public static List<Integer> sort(List<Integer> array) {
        List<Integer> newList = Lists.newArrayList();
        int totalSize = array.size();
        for (int i = 0; i < totalSize; i++) {
            int minNum = getMinNum(array);
            newList.add(minNum);
        }
        return newList;
    }
    public static int getMinNum(List<Integer> array) {
        int size = array.size();
        int minIndex = 0;
        int minNum = array.get(0);
        for (int i = 1; i < size; i++) {
            if (array.get(i) < minNum) {
                minIndex = i;
                minNum = array.get(i);
            }
        }
        array.remove(minIndex);
        System.out.println("remove result:" + JSONObject.toJSONString(array));
        return minNum;
    }
}

缺点：

选择排序生成了一个新的列表，会占用更多的内存
冒泡排序是原地排序

时间复杂度：O(n^2)

选择排序优化

每一次遍历，找到最小的数和其下标，然后和首位交换
这样首位及之后位置会随着这种和最小的交换变得有序
然后我们重复关心无序区域的数据 ```java package com.algorithm.demo.sorts;

import com.alibaba.fastjson.JSONObject;

/**

@Author leijs

@date 2022/4/9 */ public class SelectSortV2 { public static void main(String[] args) {

 int[] array = new int[] {7,2,5,4,1,9,17,11, 12,3};
 sort(array);
 System.out.println("final result:" + JSONObject.toJSONString(array));

}

public static void sort(int[] array) {

 for (int i = 0; i < array.length; i++) {
     int cur = array[i];
     int minIndex = i;
     for (int j = i+ 1; j < array.length; j++) {
         if (cur > array[j]) {
             cur = array[j];
             minIndex = j;
         }
     }
     // 交换顺序
     int temp = array[i];
     array[i] = array[minIndex];
     array[minIndex] = temp;
     System.out.println("sort result:" + JSONObject.toJSONString(array));
 }

} }

注意有序区和无序区的位置，注意记录最小数的位置。复杂度O(n^2)
<a name="nG2za"></a>
## 插入排序
类似于玩牌的时候，摸牌并插入到有牌的正确位置。
```java
package com.algorithm.demo.sorts;
import com.alibaba.fastjson.JSONObject;
/**
 * @Author leijs
 * @date 2022/4/9
 */
public class InsertSort {
    public static void main(String[] args) {
        int[] array = new int[]{7, 2, 5, 4, 1, 9, 17, 11, 12, 3};
        sort(array);
        System.out.println("final result:" + JSONObject.toJSONString(array));
    }
    public static void sort(int[] array) {
        // 第i趟
        for (int i = 1; i < array.length; i++) {
            // j指的是手里的牌
            int j = i - 1;
            // 摸到的牌
            int temp = array[i];
            if (temp > array[j]) {
                continue;
            }
            while (j >= 0 && temp < array[j]) {
                array[j + 1] = array[j];
                j -= 1;
            }
            array[j + 1] = temp;
            System.out.println("sort result:" + JSONObject.toJSONString(array));
        }
    }
}

时间复杂度：O(n^2)

牛B三人组

快速排序

快速排序的特点：

取一个元素P（第一个元素），使元素P归位
列表被P分为两个部分，左边都比P小，右边都比P大。
递归完成排序。

从右边找比5小的，从左边找比5大的。

快速排序的框架

package com.algorithm.demo.sorts;
import com.alibaba.fastjson.JSONObject;
/**
 * @Author leijs
 * @date 2022/4/9
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] array = new int[] {7,2,5,4,1,9,17,11, 12,3};
        sort(array, 0, array.length - 1);
        System.out.println("final result:" + JSONObject.toJSONString(array));
    }
    public static void sort(int[] array, int left, int right) {
        if (left < right) {
            int mid = partition(array, left, right);
            sort(array, left, mid -1);
            sort(array, mid + 1, right);
        }
    }
    public static int partition(int[] array, int left, int right) {
        // 把第一个元素存起来
        int temp =  array[left];
        while (left < right) {
            // 从右边找一个比5小的数，因为左边有空位
            while (left < right && array[right] >= temp) {
                // 只要比temp小的,往左走一
                right -= 1;
            }
            // 把右边的值写到昨天空位上
            array[left] = array[right];
            // 接下来就要从左边找比5大的数
            while (left < right && array[left] <= temp) {
                left += 1;
            }
            // 把左边的值写到右边的空位上
            array[right] = array[left];
        }
        // temp写在left和right碰头的位置，把temp归位
        array[left] = temp;
        return left;
    }
}

快速排序的复杂度：

partition，每一层都O(n)的复杂度，整个复杂度就是：O(nlog(n))

快排的问题

最坏情况

倒序列表的排序：9 8 7 6 5 4 3 2 1 排序成 1 2 3 4 5 6 7 8 9 每次只少一个数，并非少一半，最坏复杂度就是O(n^2)
递归的深度

最坏情况的解决：随机找一个数，和第一个数交换，然后逻辑再同之前。

堆排序

前传-树与二叉树

树的基本概念：

根节点、叶子节点

叶子节点：不能分叉的节点，没有孩子
树的深度（高度）

上图4层
树的度

节点的度：对于E节点，度是2，分了两个叉7，F节点是3 树的度最大节点分的叉，A分了6个叉，所以这个树的度就是6.
孩子节点/父节点

节点时间的关系。E是I的父节点，I是E的孩子节点
子树

E I J P Q 就属于子树，，一个树的分叉一起拿出来。

二叉树

度不超过2的树，

完全二叉树：

完全二叉树就是满二叉树叶子节点右边拿到一些叶子节点。

二叉树的存储方式
链式存储方式
顺序存储方式（重点）：简单用列表来存储

下面这是一个完全二叉树：

首先9的编号是0，其左子节点8的编号是1
父节点8的编号是1，左子节点6的编号是3

什么是堆

堆：是一种特殊的完全二叉树

大根堆：一颗完全二叉树，满足任一节点都比其孩子节点大
小根堆：一颗完全二叉树，满足任一节点都比其孩子节点小。
堆的向下调整性质

假设根节点的左右子树是堆，但根节点不满足堆的性质可以通过一次向下调整来将其变成一个堆。

调整后：

堆排序过程

挨个出树，9走了，然后把3放上去：

然后向下调整。之后重复这个过程。

怎么建造一个堆？

首先需要下级先有序。农村包围城市。看最后一个非叶子节点。

3个5调整。

7和1调整

重复以上调整过程。

package com.algorithm.demo.sorts;
import java.util.Arrays;
/**
 * @Author leijs
 * @date 2022/4/9
 */
public class HeapSortV2 {
    public static void main(String[] args) {
        int[] a = {-1, 9, 0, 6, 5, 8, 2, 1, 7, 4, 3};
        System.out.println(Arrays.toString(a));
        HeapSortV2.sort(a);
        System.out.println(Arrays.toString(a));
    }
    public static void sort(int[] a) {
        //s[0]不用，实际元素数量和最后一个元素的角标都为N
        int N = a.length - 1;
        //构造堆
        //如果给两个已构造好的堆添加一个共同父节点，
        //将新添加的节点作一次下沉将构造一个新堆，
        //由于叶子节点都可看作一个构造好的堆，所以
        //可以从最后一个非叶子节点开始下沉，直至
        //根节点，最后一个非叶子节点是最后一个叶子
        //节点的父节点，角标为N/2
        for (int k = N / 2; k >= 1; k--) {
            sink(a, k, N);
        }
        //下沉排序
        while (N > 1) {
            swap(a, 1, N--); //将大的放在数组后面，升序排序
            sink(a, 1, N);
        }
    }
    //下沉（由上至下的堆有序化）
    private static void sink(int[] a, int k, int N) {
        while (true) {
            int i = 2 * k;
            if (i > N) { //保证该节点是非叶子节点
                break;
            }
            if (i < N && a[i + 1] > a[i]) { //选择较大的子节点
                i++;
            }
            if (a[k] >= a[i]) { //没下沉到底就构造好堆了
                break;
            }
            swap(a, k, i);
            k = i;
        }
    }
    private static void swap(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
}

时间复杂度

sift是一个折半的函数。
时间复杂度：O(nlogn)

问题：topK问题

现在有n个数，设计算法得到前K个大的数（k < n）
解决思路：

方法一：排序后切片，时间复杂度：O(nlogn)
方法二：排序LowB 三人组

冒泡排序排K次。O(kn)
方法三：堆排序，复杂度 O(nlogk)

取列表前K个建立一个小根堆，堆顶就是目前第K大的数依次向后遍历原列表，对于列表中的元素，如果小于堆顶，则忽略该元素，如果大于堆顶，则将该堆顶替换为该元素，并且对堆进行一次排序。遍历完所有元素后，倒序倒出堆顶。

归并排序

分解：将列表越分越小，直至分成一个元素。
终止条件：一个元素是有序的。
合并：将两个有序列表归并，列表越来越大。

两端，2 和 1比较，发现1小，放入第一位，然后第二段指针往右； 2 和 3 比，发现是2，则第一段指针往左挪接下来：5和3比。重复此过程。

package com.algorithm.demo.sorts;
import com.alibaba.fastjson.JSONObject;
import java.util.ArrayList;
import java.util.List;
/**
* @Author leijs
* @date 2022/4/10
*/
public class MergeSort {
    public static void main(String[] args) {
        int[] array = new int[]{7, 2, 5, 4, 1, 9, 17, 11, 12, 3};
        mergeSort(array, 0, array.length - 1);
        System.out.println("final result:" + JSONObject.toJSONString(array));
    }
    public static void mergeSort(int[] li, int low, int high) {
        if (low < high) {
            // 至少有两个元素
            int mid = (low + high) / 2;
            mergeSort(li, low, mid);
            mergeSort(li, mid + 1, high);
            merge(li, low, mid, high);
        }
    }
    public static void merge(int[] li, int low, int mid, int high) {
        // low->mid是一段  mid+1->high是一段
        // i 是第一段的开始，j是第二段的开始
        int i = low;
        int j = mid + 1;
        // 临时存放列表
        List<Integer> temp = new ArrayList<>();
        // 只要左右两边都有数比一下这两个数
        while (i <= mid && j <= high) {
            if (li[i] < li[j]) {
                temp.add(li[i]);
                i += 1;
            } else {
                temp.add(li[j]);
                j += 1;
            }
        }
        // while执行完，肯定有一部分每数了
        while (i <= mid) {
            // 说明左边有数
            temp.add(li[i]);
            i += 1;
        }
        while (j <= high) {
            temp.add(li[j]);
            j += 1;
        }
        // temp写回li
        int curIndex = low;
        for (int k = 0; k < temp.size(); k++) {
            li[curIndex] = temp.get(k);
            curIndex += 1;
        }
    }
}

时间复杂度：O(nlogn)
空间复杂度：O(n)
需要一些额外的空间。

总结

三种时间复杂度O(nlogn)
一般情况下，就运行时间而言：

快速排序 < 归并排序 < 堆排序
三种排序的优缺点

快速排序：极端情况下排序效率低归并排序：需要额外的内存开销堆排序：在快的排序算法中相对较慢。

其他排序

希尔排序

希尔排序是一种分组插入排序算法

过程

取一个整数d1 = n/2 ,将元素分为d1个组，每组相邻量元素之间的距离为d1, 在各组内进行直接插入排序
取第二个整数d2=d1/2，重复上述分组排序过程，直到d1=1,即所有元素在同一组内进行直接插入排序。

希尔排序每趟并不使某些元素有序，而是使整体数据越来越接近有序，最后一趟使得所有数据有序。

长度是9，9/2 = 4，那么我们可以把这个分成4组，间隔为4分组。

分别每组做插入排序：

然后再回到初始位置，
]
接下来d=2, 然后分成两组，每组再做插入排序:

排序好之后再归位：

最后d=1,对这个数组直接进行插入排序完事

代码

package com.algorithm.demo.sorts;
import com.alibaba.fastjson.JSONObject;
/**
* @Author leijs
* @date 2022/4/15
*/
public class ShellSort {
    public static void main(String[] args) {
        int[] array = new int[]{7, 2, 5, 4, 1, 9, 17, 11, 12, 3};
        int d = array.length / 2;
        while (d >= 1) {
            insertSort(array, d);
            d = d / 2;
        }
        System.out.println("final result:" + JSONObject.toJSONString(array));
    }
    public static void insertSort(int[] array, int gap) {
        // 第i趟
        for (int i = gap; i < array.length; i++) {
            // j指的是手里的牌
            int j = i - gap;
            // 摸到的牌
            int temp = array[i];
            if (temp > array[j]) {
                continue;
            }
            while (j >= 0 && temp < array[j]) {
                array[j + gap] = array[j];
                j -= gap;
            }
            array[j + gap] = temp;
            System.out.println("sort result:" + JSONObject.toJSONString(array));
        }
    }
}

其他

希尔排序的时间复杂度和gap取值有关系。

计数排序

对列表进行排序，已知列表中数的范围都在0-100之间，设计时间复杂度为O(n)的算法。
对每个数字计数
如： 1 3 2 4 1 2 4 5 7

实现

package com.algorithm.demo.sorts;
import com.alibaba.fastjson.JSONObject;
/**
 * @Author leijs
 * @date 2022/4/15
 */
public class CountSort {
    public static void main(String[] args) {
        int[] array = new int[] {7,2,5,4,1,9,17,11, 12,3};
        sort(array, 18);
        System.out.println("final result:" + JSONObject.toJSONString(array));
    }
    public static void sort(int[] li, int maxCount) {
        int[] count = new int[maxCount];
        for (int num : li) {
            count[num] = count[num] + 1;
        }
        int index = 0;
        for (int i = 0; i < count.length; i++) {
            int total = count[i];
            if (total == 0) {
                continue;
            }
            for (int j = 0; j < total; j++) {
                li[index] = i;
                index++;
            }
        }
    }
}

总结

时间复杂度：O(n) 缺点：需要知道数的范围；对小数不是很友好。如果知道0-100，就需要一个长度101的数组，如果是1个亿？

桶排序

首先将数划分为不同的范围，相当于丢在不同的桶，然后每个桶的元素保持有序。

实现

package com.algorithm.demo.sorts;
import com.alibaba.fastjson.JSONObject;
import java.util.Arrays;
/**
 * @Author leijs
 * @date 2022/4/15
 */
public class BucketSort {
    public static void main(String[] args) {
        int[] array = new int[]{7, 2, 5, 4, 1, 9, 17, 11, 12, 3};
        bucketSort(array, 4, 17);
        System.out.println("final result:" + JSONObject.toJSONString(array));
    }
    public static void bucketSort(int[] array, int bucketNums, int maxNum) {
        // 创建N个桶，每个桶放maxNum/bucketNums个数
        int range = maxNum / bucketNums;
        int[][] buckets = new int[bucketNums][];
        for (int i = 0; i < array.length; i++) {
            int value = array[i];
            int j = Math.min(value / range, bucketNums - 1);
            int[] currentBucketVals = buckets[j];
            if (null == currentBucketVals) {
                currentBucketVals = new int[1];
                buckets[j] = currentBucketVals;
                currentBucketVals[0] = value;
                continue;
            }
            int[] newElements = Arrays.copyOf(currentBucketVals, currentBucketVals.length + 1);
            newElements[currentBucketVals.length] = value;
            if (newElements.length > 1) {
                insetSort(newElements);
            }
            buckets[j] = newElements;
        }
        // 最后回写array
        int curIndex = 0;
        for (int i = 0; i < buckets.length; i++) {
            for (int j = 0; j < buckets[i].length; j++) {
                array[curIndex] = buckets[i][j];
                curIndex++;
            }
        }
    }
    public static void insetSort(int[] array) {
        // 第i趟
        for (int i = 1; i < array.length; i++) {
            // j指的是手里的牌
            int j = i - 1;
            // 摸到的牌
            int temp = array[i];
            if (temp > array[j]) {
                continue;
            }
            while (j >= 0 && temp < array[j]) {
                array[j + 1] = array[j];
                j -= 1;
            }
            array[j + 1] = temp;
        }
    }
}

桶排序的表现取决于数据的分布，也就是需要对不同数据排序时采取不同的分桶策略。
平均情况时间复杂度：O(n+k)
最坏情况时间复杂度：O(n^2 * k)
空间复杂度：O(nk)

对k，代表一个桶可以有多少数据

基数排序

多关键字排序，比方说员工表，先按照薪资排序，再按薪资相同按照年龄排序。

思路： 94和32，看十位，9比3大，所以94大于32. 94和94，十位相同，比较个位

实现

package com.algorithm.demo.sorts;
import com.alibaba.fastjson.JSONObject;
import java.util.Arrays;
/**
 * @Author leijs
 * @date 2022/4/15
 */
public class RadixSort {
    public static void main(String[] args) {
        int[] array = new int[]{7, 2, 5, 4, 1, 9, 17, 11, 12, 3};
        radixSort(array, 17);
        System.out.println("final result:" + JSONObject.toJSONString(array));
    }
    public static void radixSort(int[] li, int max) {
        // 最大值：99-> 2次排序,999 -> 需要3次
        int it = 0;
        while (Math.pow(10, it) < max) {
            int[][] buckets = new int[10][];
            for (int value : li) {
                int curBucket = (int) (value / (Math.pow(10, it)) % 10);
                int[] currentBucketVals = buckets[curBucket];
                if (null == currentBucketVals) {
                    currentBucketVals = new int[1];
                    buckets[curBucket] = currentBucketVals;
                    currentBucketVals[0] = value;
                    continue;
                }
                int[] newElements = Arrays.copyOf(currentBucketVals, currentBucketVals.length + 1);
                newElements[currentBucketVals.length] = value;
                if (newElements.length > 1) {
                    insetSort(newElements);
                }
                buckets[curBucket] = newElements;
            }
            // 最后回写array
            int curIndex = 0;
            for (int i = 0; i < buckets.length; i++) {
                if (null == buckets[i]) {
                    continue;
                }
                for (int j = 0; j < buckets[i].length; j++) {
                    li[curIndex] = buckets[i][j];
                    curIndex++;
                }
            }
            it += 1;
        }
    }
    public static void insetSort(int[] array) {
        // 第i趟
        for (int i = 1; i < array.length; i++) {
            // j指的是手里的牌
            int j = i - 1;
            // 摸到的牌
            int temp = array[i];
            if (temp > array[j]) {
                continue;
            }
            while (j >= 0 && temp < array[j]) {
                array[j + 1] = array[j];
                j -= 1;
            }
            array[j + 1] = temp;
        }
    }
}

时间复杂度

时间复杂度：O(kn)
空间复杂度：O(k+n)
k表示数字位数

列表排序

lOW B三人组

冒泡排序

选择排序优化

牛B三人组

快速排序

快速排序的框架

快排的问题

堆排序

前传-树与二叉树

二叉树

什么是堆

堆的向下调整性质

堆排序过程

怎么建造一个堆？

时间复杂度

问题：topK问题

归并排序

总结

其他排序

希尔排序

过程

代码

其他

计数排序

实现

总结

桶排序

实现

基数排序

实现

时间复杂度