08-排序.md

分类

按排序方法分类

按存储介质分

按比较器个数可分为

按主要操作可分为

按辅助空间

按稳定性

插入排序

直接插入排序

使用顺序查找法查找插入位置

使用哨兵

折半插入排序

希尔排序

过程

排序对不相邻的记录进行比较和移动：

1. 将待排序序列分为若干子序列（每个子序列的元素在原始数组中间距相同）；
2. 对这些子序列进行插入排序；
3. 减小每个子序列中元素之间的间距，重复上述过程直至间距减少为 。

class Solution {
    public int[] sortArray(int[] nums){
    shellSort(nums);
    return nums;
  }

  public void shellSort(int[] nums){
        for(int step = nums.length >> 1; step >= 1; step = step >> 1){
            for(int start = step; start < nums.length; start++){
                for(int j = start - step; j >= 0 && nums[j + step] < nums[j]; j-=step){
                    swap(nums, j, j + step);
                }
            }
        }
    }

    public void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

交换排序

快速排序

——改进的交换排序

节省空间秘技：【左右横跳】 https://www.bilibili.com/video/BV1nJ411V7bd?p=164&vd_source=6c2daed6731190bb7d70296d6b9746bb

选择排序

简单选择排序

堆排序

堆的定义

排序的调整

无序变有序的输出过程

1. 输出根节点
2. 将一个叶子节点放到根节点
3. 不断比较其左右孩子值的大小，并与其中较小者交换，直到底下没有更大的节点

小根堆的建立

从 最底下的一个非叶子节点开始，找左右孩子最小的来替换本节点。向上逐个调整

堆排序算法

归并排序

双指针法

基数排序（桶排序）

按照逐个的关键字排序