回归正确位置 – 十大排序

排序

排序通过 比较 和 交换 将元素回归正确位置
不同的排序思想有各自的特点和更适宜的场景
可利用排序后的序列方便方便进一步解决问题

选择排序

思想 每轮选出最小值，按升序置于数组
优点 数据移动最少
缺点 无脑，有序数组仍需走完所有流程
性能 O(n^2 / 2)

    public void sort(int[] a) {
        int N = a.length;
        for (int i = 0; i < N; i++) {
            int m = i;
            for (int j = i + 1; j < N; j++)
                if (a[j] < a[i]) m = j;
            swap(a, i, m);
        }
    }

插入排序

思想 与已排元素比较交换，直到换到正确位置
优点 性能优于选择排序。利用了有序信息，对很多元素已经有序的情况，仅需很少的交换次数，可达线性复杂度
缺点 完全逆序序列要进行 n^2 / 2 次比较和交换，性能弱于选择排序
性能 平均 O(n^2 / 4)，取决于逆序对个数

    public void sort(int[] a) {
        int N = a.length;
        for (int i = 1; i < N; i++) {
            for (int j = i; j > 0; j--) {
                if (a[j] < a[j - 1])
                    swap(a, j, j - 1);
                else break;
            }
        }
    }

希尔排序

思想 拆为多个子序列的插入排序，子序列内部间隔相等。较大间隔的插入排序子序列较短，运行时间少，可将较远元素交换至前形成部分有序序列，减少了下一轮插入排序的比较和交换次数。较小间隔的插入排序子序列较长，很好地利用了上轮形成的部分有序序列性质。随着间隔递减，每一轮排序复杂度逐步接近线性，提升了算法速度
优点 速度较快，占用内存少，代码量少
性能 最坏复杂度为 O(n^(3/2))

public void sort(int[] a) {
    int N = a.length;
    int k = 1;
    while (k < N / 3) k = 3 * k + 1;
    for (; k >= 1; k /= 3) {
        for (int i = k; i < N; i++) {
            for (int j = i; j >= k; j -= k)
                if (a[j] < a[j - k]) swap(a, j, j - k);
        }
    }
}

归并排序

Merge Sort – 归并排序详解与优化

快速排序

思想 选取枢轴，使枢轴左侧不大于枢轴，枢轴右侧不小于枢轴。分别对枢轴左右侧子序列及子序列的子序列递归进行上述操作使每个枢轴左右侧均有大小关系，递归完毕则序列有序。
优点 速度快，比较次数少，无需额外内存，代码简洁
缺点 受限于枢轴的选取，最坏情况会降为 O(n^2 / 2)，为保证性能一般在排序前随机打乱顺序
性能 复杂度为 O(nlogn）
实现 枢轴选取：取第一个元素为枢轴；枢轴归位：指针相遇后由于–j，总使j指向最后一个小于枢轴元素，即枢轴归位位置；重复元素处理：指向与枢轴相同的元素视为找到大于/小于枢轴数，对于含有大量重复元素的序列仍需做出不必要的交换；指针关系：扫描循环使i指针左侧总小于等于枢轴，j指针右侧总大于等于枢轴，暗含i<j关系，仅在指针相遇后使得i<j；最坏情况：待排序列为正/逆序序列退化为选择排序，指针到达边界与枢轴或末尾元素交换

    public void sort(int[] a, int lo, int hi) {
        if(lo >= hi) return;
        int j = partition(a, lo, hi);
        sort(a, lo, j - 1);
        sort(a, j + 1, hi);
    }

    public int partition(int[] a, int lo, int hi) {
        int i = lo;
        int j = hi + 1;
        while(true) {
            while(a[++i] < a[lo]) if(i == hi) break; // 从头向右寻找大于枢轴数
            while(a[--j] > a[lo]) if(j == lo) break; // 从尾至头寻找小于枢轴数
            if(i >= j) break;                        // 指针交错本轮已排好跳出
            swap(a, i, j);                           // 指针未交错交换大小关系
        }
        swap(a, lo, j);                              // 将枢轴置于中间
        return j;                                    // 返回枢轴下标
    }

三向切分

维护两个指针l和r，使l左侧数均小于枢轴，r右侧数均大于枢轴，中间所夹均等于枢轴，逐步缩小最左最右范围，完毕进入子序列递归时只需取两个指针为边界，无需将中间值计入，因而缩小了规模。当序列中有较多重复元素时很高效，可达线性复杂度，最坏情况所有值均相异，复杂度为O(nlogn）

    public void sort(int[] a, int lo, int hi) {
        if(lo >= hi) return;
        int l = lo;                                 // l指向等于枢轴数
        int i = lo + 1;                             // i指向当前访问数
        int r = hi;
        int v = a[lo];
        while(i <= r) {
            if     (a[i] < v)   swap(a, i++, l++);  // 小于枢轴数交换到最左侧。i为枢轴无需与枢轴比较，直接进入下轮
            else if(a[i] > v)   swap(a, i, r--);    // 大于枢轴数交换到最右侧。交换到i位置数在下轮与枢轴比较
            else                i++;                // 等于原地不动，指向下一个数再次判断
        }
        sort(a, lo, l - 1);                         // 递归左侧子序列
        sort(a, r + 1, hi);                         // 递归右侧子序列
    }

快速选择

用于找到第K个（从0开始计数）最大/小值。以找到第K个最小值为例，即找到排序后下标K对应值。快速排序思想中，枢轴左右侧大小关系已定，仅需对枢轴一侧数组进行排序即可确定到位置K，省去一半操作。依次向内一直折半递归，直到递归至仅有一个元素即a[K]时完成局部排序结束。复杂度为O(n)，序列为正/逆序为最坏情况，复杂度为O(n^2 / 2)

    public int quickSelect(int[] a, int K) {
        int lo = 0;
        int hi = a.length - 1;
        while(lo < hi) {
            int i = partition(a, lo, hi);
            if      (i > K) lo = i + 1;
            else if (i < K) hi = i - 1;
            else            return a[K];
        }
        return a[K];
    }

堆排序

类似于选择排序，堆排序每次取堆顶元素（最大元素）倒序置于数组而成升序
不同于选择排序需要线性遍历查找最大元素，最大堆具有堆顶元素最大的性质

最大二叉堆

所有父节点均大于子节点的完全二叉树

    public class MaxHeap {
        private int[] a;        // 堆及其中元素，长度为 N+1
        private int N;          // 元素个数，也即堆末下标
    }

父子节点关系 索引从1开始计。已知父节点索引 i，则子节点索引为 2i 和 2i+1。已知子节点索引 i，父节点索引为 i/2
调整最大堆序结构 调整堆有序就是维持所有父节点均大于子节点的关系。当由于改变子节点使子节点>父节点时，将子节点与父节点不断互换上移，改变父节点破坏堆有序时，将较小的父节点与最大子节点互换不断下移，直至满足堆有序

    public void up(int i) {
        while (i > 1) {
            int p = i / 2;
            if (a[p] < a[i]) swap(a, i, p);
            else break;
            i = p;
        }
    }

    public void dn(int i) {
        while (i * 2 <= N) { // 有左子节点测试下移
            int lf = 2 * i;
            int rf = lf + 1;
            if (rf <= N && a[lf] < a[rf]) lf = rf;
            if (a[i] < a[lf]) swap(a, i, lf);
            else break;
            i = lf;
        }
    }

最大堆构造 直接输入从1开始计的无序数组，从倒数第二层开始不断将小的父节点下移，自右向左，自底向上直到根节点调整堆序。也可从零开始将节点一个一个插入堆末并不断将较大的子节点上移，相对于第一种方法多出了最后一层节点的操作

    public MaxHeap(int[] a) {
        this.a = a;
        this.N = a.length - 1;
        int i = N / 2;
        while (i >= 1) dn(i--);
    }

最大二叉堆排序

构造最大堆后，每次将最大元素出堆置于数组末尾，原末尾元素置于根节点，恢复堆序

    public void sort() {
        while (N >= 1) {
            swap(a, 1, N--);
            dn(1);
        }
    }

索引二叉堆

背景 当待排元素是较复杂的数据结构时，在堆中的交换操作成本较高
元素插入堆后，若某个元素的值发生更新需要修改，需要遍历堆来寻找该元素
思想 为每个元素设置一个索引，需要更新特定元素时直接通过索引访问
构造堆时元素不入堆，索引入堆，构建索引二叉堆

思路
    每个元素入堆时绑定一个索引
 -> 通过索引找入堆后对应元素
 -> 索引在入堆后被重排，无法直接找到该索引所在位置
 -> 设置一个数组保存索引当前所在位置
 -> 索引在入堆和堆中交换时，同时要更新索引所在位置

实现

    public class IndexPriorityQueue{
        String[] key;   // 元素不入堆，位置固定，仅在比较时通过索引访问
        int[] lo;       // 下标与元素一一对应，保存该元素索引所在位置
        int[] id;       // 保存索引，构成索引二叉堆
    }

三叉堆

冒泡排序（待续）

逐位比较，大则交换

    public void BubbleSort(int[] nums) {
        for(int i = 0; i < nums.length; i++) {
        }
    }

桶排序（待续）

基于比较的排序算法下界是O(nlogn)
归并排序的优化