【算法与数据结构】排序相关思想 - hippowc/hippowc.github.io GitHub Wiki
概览
常见的排序算法分类：
- 插入排序：直接插入，shell排序
- 选择排序：直接选择，堆排序
- 交换排序：冒泡排序，快速排序
- 归并排序
- 基数排序
冒泡排序
思想：对于数组a[n],进行排序，思路比较直观
- 将a[n]中最大数移到最后
- 将a[n-1]中最大数移到最后 。。。
- 将a[0]中最大数移到最后
for(int i = unsorted.length - 1; i >= 0; i--) {
for(int j = 0; j < i; j++) {
if(unsorted[j] < unsorted[j + 1]) {
int temp = unsorted[j];
unsorted[j] = unsorted[j + 1];
unsorted[j + 1] = temp;
}
}
}
冒泡排序思路和实现很简单，但是有很多优化的空间，因为存在重复比较 譬如：1 3 5 4，因为每次都从最开始进行比较，并选择出一个最大的冒泡上去，那么其实最开始的1和3，每次循环都要比较，这就是优化空间
快速排序
思想：选取一个中间值，然后根据这个中间值pivot，将大于pivot的值都挪到左边，将小于pivot的值都挪到右边，然后分别对左侧和右侧进行相同的操作。
递归的设计思路
- 递归就是在过程或函数里调用自身。所以函数的设计上：递归函数参数要能解决本身问题以及子问题
- 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。
先抛开快速排序，看一个经典的递归问题，斐波那契数列（Fibonacci），这个数列中，每个数是前两个数值的和，第一个和第二个数值是1，那么如何求解这个这个数列第n个值：
int fibo(int n) {
if(n == 1 || n == 2) {
return 1;
} else {
return fibo(n - 1) + fibo(n - 2);
}
}
可以发现递归法写的程序，非常容易描述：
- 第n个值就等于第n-1个值加上第n-2个值
- 返回点是n==1或者n==2的时候
递归函数在设计的时候，函数本身也可以用作子问题。再来看看快速排序：
快速排序会稍微复杂一点：
- 选择一个pivot中枢点，将小于pivot的值放在左侧，将大于pivot的放在右侧
- 返回点为不能再继续分的时候
- 分别对左边和右边在运用这个方法
所以我们看到递归函数要在本函数中调用本身解决子问题，那么：
- 要可以将整体问题划分为相同的且规模更小的子问题
- 递归函数的解决方案可以适用于子问题，规模作为参数传递
- 递归函数每个问题的解决不一定依赖于子问题的结果，譬如快速排序，就自己解决自己就好
完全懂了快速排序原理后，依然不一定写好一个快排算法，算法实现时有很多细节，譬如：
- 小于等于号
- 中间节点是变化的，而不是数组正中间，是最后left和right碰头的地方。
public static int partition(int[] unsorted, int li, int ri) {
int pivot = (li + ri) / 2;
int pv = unsorted[pivot];
while(li <= ri) {
while(unsorted[li] < unsorted[pivot]) {
li++;
}
while(unsorted[ri] > unsorted[pivot]) {
ri--;
}
if(li <= ri) {
int tmp = unsorted[li];
unsorted[li] = unsorted[ri];
unsorted[ri] = tmp;
li++;
ri--;
}
}
return li;
}
public static void sort(int[] unsorted, int li, int ri) {
if(li < ri) {
int pivot = partition(unsorted, li, ri);
sort(unsorted, li, pivot - 1);
sort(unsorted, pivot, ri);
}
}
归并排序
归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。
归并排序的思想：将数列均分为两列，分别对两列进行排序，然后将两列合并为同一列。其实这个问题显然也可以使用递归的方式完成，因为每个子问题的处理方式都是相同的；
最终会分成一个一个的元素，然后对元素进行归并，其实我们主要需要解决下如何把两个已经排好序的序列归并为同一个有序序列。
- 需要一个额外的数组放置两个待归并数组
- 从头逐一检索两个数组，并比较大小，将小的一个插入到新数组中，并移动至下一个数
- 直到两个数组都遍历完成
public static void sort(int[] unsorted, int[] temp, int li, int ri) {
int mid = (li + ri) / 2;
if(li < ri) {
// 继续分解
sort(unsorted, temp, li, mid);
sort(unsorted, temp, mid + 1, ri);
merge(unsorted, temp, li, ri);
}
}
public static void merge(int[] unsorted, int[] temp, int li, int ri) {
// copy
for(int i = li; i <= ri; i++) {
temp[i] = unsorted[i];
}
int mid = (li + ri) / 2;
int tli = li;
int tri = mid + 1;
int starti = li;
// 如果两个数组都没有走到边界的时候
// 这个地方最好不要使用||，否则内部的情况比较复杂
while(tli <= mid && tri <= ri) {
if(temp[tli] < temp[tri]) {
unsorted[starti++] = temp[tli++];
}
if(temp[tli] >= temp[tri]){
unsorted[starti++] = temp[tri++];
}
}
// 如果左边数组到了尽头，把右边剩余数组copy过来
while(tri <= ri) {
unsorted[starti++] = temp[tri++];
}
// 如果右边数组到了尽头，把左边剩余数组copy过来
while(tli <= mid) {
unsorted[starti++] = temp[tli++];
}
}
归并排序和快排的递归方法对比来看，会比较有趣，快速排序实现先处理父问题，在去依次处理子问题（先整体划分，在去划分子问题），所以快排中的递归不依赖子问题的返回，所以快排的处理逻辑放在最前面，然后是递归处理逻辑
而归并排序，是需要先归并处理子问题，当所有子问题都处理好之后，最后归并Merge最上层的问题，所以递归方法是放在前面的，需要等递归返回之后，再归并。
这样的话，要理解归并排序，需要先想到递归的终点，也就是最小子问题，并且返回之后，才可以理解整体。
所以递归的终点做了什么事，是理解递归的重要部分之一
在递归的尽头，就是当 执行 0 - 1 时，mid此时为0，这是内部的sort都会直接返回，此时执行merge，也就是说，递归的尽头，是两个数的归并排序。
ps：递归真的超级难理解啊。目前我觉得设计递归的关键是：
- 父问题与子问题处理方式要相同
- 是先递归，还是先处理问题要看具体问题，先递归则要把递归函数写在前面，否则要把递归函数写在后面（呸，废话）
- 递归的尽头是怎么处理的？倒数一步或者倒数两步
堆排序
堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。
堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
我们对堆中的结点按层从左到右进行编号，可以以数组的形式表示一个堆
大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]
基本思想
将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了
相当于不断的去找一个数组中的最大值，整体思维和冒泡排序是相似的。但是堆排序只需要扫描一半的元素（n/2-1 ~ 0）即可，因为堆排序是从下往上，从右往左，以一个节点（父-左子-右子）来比较的。因为(n/2-1)~0的节点才有子节点，所以循环的数量要少。
先了解下二叉树
二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。
二叉树的每个结点至多只有二棵子树（不存在度大于 2 的结点），二叉树的子树有左右之分，次序不能颠倒。二叉树的第 i 层至多有 2i - 1 个结点；深度为 k 的二叉树至多有 2k - 1 个结点；对任何一棵二叉树 T，如果其终端结点数为 n0，度为 2 的结点数为 n2，则n0 = n2 + 1
二叉树又分为完全二叉树（complete binary tree）和满二叉树（full binary tree）
- 满二叉树：一棵深度为 k，且有 2k - 1 个节点称之为满二叉树
- 完全二叉树：深度为 k，有 n 个节点的二叉树，当且仅当其每一个节点都与深度为 k 的满二叉树中序号为 1 至 n 的节点对应时，称之为完全二叉树
堆（二叉堆）可以视为一棵完全的二叉树，完全二叉树的一个“优秀”的性质是，除了最底层之外，每一层都是满的，这使得堆可以利用数组来表示（普通的一般的二叉树通常用链表作为基本容器表示），每一个结点对应数组中的一个元素。如果i为父元素，那么2i-1是其左子孩子，2i+1是其右子孩子
步骤
- 从下往上，从右往左，逐个节点进行比较，最大值成为父节点，最终在root处获得最大值
- 将最大值与尾部节点交换，调整堆，从上往下，逐个节点进行比较，直到尾部节点到达正确位置
- 依次循环