本文主要是介绍Sorting (Merge Sort, Rainball Sort, quick select) 总结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Merge k Sorted Lists (这题是用PQ，或者merge sort都可以做，关于第K大的问题，参考: Find Kth 题目类型总结)
Sort an Array (重点掌握merge sort和quick sort，因为两者可以演变为,divide conquer, quick select, 参考: Find Kth 题目类型总结)
Sort Colors 思路：三指针，i, j, k. 目标是 0 ，1 ，2 用i来保持0的位置，k来保持2的位置，j来做扫描运动，如果j遇见0，换到前面去，如果遇见2换到后面去。注意，如果换到前面的情况，i可以++，j也可以++，因为换回来的只可能是1，不可能是别的情况，因为前面的i部分已经被扫描过，2已经到后面去了。j遇见2，与后面进行互换的时候，j不能++，因为不知道换回来的是0，还是1，还是2，还得进行一次判断。这也是这个题目的考点。
Quick Select 题型参考: Find Kth 题目类型总结
Kth Smallest Numbers in Unsorted Array quick select的标准模板，一定要熟记，多写几次就熟悉了。
public class Solution {/*** @param k: An integer* @param nums: An integer array* @return: kth smallest element*/public int kthSmallest(int k, int[] nums) {if(nums == null || nums.length == 0) {return -1;}return findKth(nums, 0, nums.length - 1, k);}private int findKth(int[] A, int start, int end, int k) {if(start == end) {return A[start];}int mid = start + (end - start) / 2;int pivot = A[mid];int i = start, j = end;while(i <= j) {while(i <= j && A[i] < pivot) {i++;}while(i <= j && A[j] > pivot) {j--;}if(i <= j) {int temp = A[i];A[i] = A[j];A[j] = temp;i++;j--;}}if(start + k - 1 <= j) {return findKth(A, start, j, k);}if(start + k - 1 >= i) {return findKth(A, i, end, k - (i - start));}return A[j + 1];}
}Sort List 思路：merge sort Linked List, jame bone,找到middle point的前一个，然后把list 劈开；
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode sortList(ListNode head) {if(head == null || head.next == null) {return head;}ListNode middlePre = findMiddlePre(head);ListNode newhead = middlePre.next;middlePre.next = null;ListNode l1 = sortList(head);ListNode l2 = sortList(newhead);return mergeTwoSortedList(l1, l2);}private ListNode findMiddlePre(ListNode head) {ListNode dummy = new ListNode(0);dummy.next = head; // 别忘记了，dummy.next = head，连起来；ListNode slow = dummy;ListNode fast = dummy;while(fast != null && fast.next != null && fast.next.next != null) {slow = slow.next;fast = fast.next.next;}return slow;}private ListNode mergeTwoSortedList(ListNode l1, ListNode l2) {ListNode dummy = new ListNode(0);ListNode cur = dummy;while(l1 != null && l2 != null) {if(l1.val < l2.val) {cur.next = l1;l1 = l1.next;cur = cur.next;} else {cur.next = l2;l2 = l2.next;cur = cur.next;}}if(l1 != null) {cur.next = l1;}if(l2 != null) {cur.next = l2;}return dummy.next;}
}Merge Intervals (Interval 是一类很重要的题目，往往跟Sweep line相结合, 参考: 扫描线Sweep Line算法总结)
思路：首先按照start sort之后，判断end是否跟start相交，如果相交，end就是两者最大值；否则加入cur；注意最后需要加入cur；
Convert Sorted Array to Binary Search Tree 思路：找中间点，就是root，然后两边分别构造左子树和右子树。
Convert Sorted List to Binary Search Tree 思路：jame bond 的思路，找mid的前一个点，然后两边分开找；这里只传递一个参数；注意middle的前后都要断开，否则会死循环；
Search in Rotated Sorted Array 思路：按照九章的模板来写；总体思想就是：确定哪段是升序的，然后把target钳住里面，判断是否在里面，否则搜另外一边；因为array是rotated，所以，只能是两边要么一边升序，把target放在升序的序列里面进行判断，如果不在，选另外一边；
关于search，这里有Binary Search 总结
这篇关于Sorting (Merge Sort, Rainball Sort, quick select) 总结的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
