- 1. 归并排序
- 1.1 算法思想
- 1.2 代码模板
- 2. 快速排序
- 1.1 算法思想
- 1.2 代码模板
将一组数据分为若干组，再两两合并，直至所有组合并完成，最终得到一个有序的数组。
我们以数组[1，8，4，2，9，7，12]为例。
-
首先将数组分为两两一组：
[1，8]， [4，2] ，[9，7] ，[12]再将其中的数两两排序，得到：
[1，8]， [2，4] ，[7，9] ，[12] -
再两两和并（归并排序的重点）（递归），在合并时，用指针 i 指向第一个数组，指针 j 指向第二个数组，判断指针指向的数的大小，将较小的数放在结果数组的第一个位置上。然后指针后移，继续比较，直至 某一个数组为空后，将另一个数组直接连接到结果数组后：
[1，8]， [2，4]比较，合成数组：[1，2，4，8]
[7，9] ，[12]比较，合成数组：[7，9，12]
因此，通过这次合并后得到的结果为：
[1，2，4，8] ，[7，9，12]
-
最后将[1，2，4，8] ，[7，9，12]合并：
当合并为[1，2，4，7，8]时，第一个数组已经为空，则直接将第二个数组中还剩下的元素[9，12]连接 到结果数组后，结果为：
[1，2，4，7，8，9，12]
// 归并排序
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) return l2;
if (l2 == null) return l1;
ListNode head = null;
if (l1.val <= l2.val){
head = l1;
head.next = mergeTwoLists(l1.next, l2);
} else {
head = l2;
head.next = mergeTwoLists(l1, l2.next);
}
return head;
}
2. 快速排序
1.1 算法思想
给定一组数据，用指针 i 指向第一个数据，用指针 j 指向最后一个数据，并给定一个基准值 flag（可以取第一个数，也可以取最后一个数，也可以取中间的数），取出这个数（这样会在数组中形成一个空位，用于后续比较后交换数据后存放）。
然后比较两个指针指向的值的大小，比 flag 大的数放在它的右边，比 flag 小的数放在它的左边，然后对左右两边再次进行快速排序（递归）。
我们以数组[1，8，4，2，9，7，12]为例。
-
首先选择基准值为正中间的数 2 。
此时，数组为[1，8，4，“此处取出2后为空”，9，7，12] -
排序（快速排序核心思想）：比较：i 指向a[0]，j 指向 a[7]
1比2小，位置不变；
i 向后移动，比较，8比2大，放在空格处，此时数组为[1， ，4，8，9，7，12]；
交换数据后，i j 交换，i 不动，j 开始移动；
12比2大，位置不变；
j 往前移动，比较，7比2大，位置不变
j 往前移动，比较，9比2大，位置不变
j 往前移动，比较，8比2大，位置不变
j 往前移动，比较，4比2大，位置不变
j 往前移动，此时i j 相遇，将拿出去的基准值2放在空处，第一次快速排序结束。此时数组为[1，2 ，4，8，9，7，12]； -
然后对左右两边再次进行快速排序（递归）。
左：[1]
右：[4，8，9，7，12]对左右两侧进行第二次快速排序，左侧只有一个数，直接返回该数组。对右侧取基准值9，右侧结果为：[4，8，7，9，12]
再对[4，8，7，9，12]，进行第三次快速排序，取基准值7，结果为[4，7，8，9，12]
此时排序完成，最终结果为[1，4，7，8，9，12]
****待补充****
