1. 排序

排序（sort）是一種常見的算法，把數據根據特定的順序進行排列。經典的排序算法如下：

• 冒泡排序（bubble sort）
• 插入排序（insertion sort）
• 選擇排序（selection sort）
• 快速排序（quick sort）
• 堆排序（heap sort）
• 歸并排序（merge sort）

冒泡排序依次比較相鄰的兩個元素，若逆序則交換；如此走訪數列重復n次，即不再發生交換，排序完成。（以下圖片均來自于Wikipedia）

但是，冒泡排序存在著許多無意義的交換，比如：對于基本有序的數組（最好情況），冒泡排序仍舊有\(O(n^2)\)次交換。我們可以標記需要交換的可能，從而降低交換次數到\(O(n)\)：

void bubble_sort(int a[], int n) {
  int i, bound;
  int exchange = n - 1;       // 初始化
  while (exchange) {
    bound = exchange; // 記錄上一次的交換位置
    exchange = 0;     // 假定這一次沒發生交換
    for (i = 0; i < bound; i++)
      if (a[i] > a[i + 1]) {
        swap(&a[i], &a[i + 1]);
        exchange = i;
      }
  }
}

插入排序能很好地避免部分無意義的交換，其核心思想：從前往后掃描序列，已掃描的元素構成一個已排序的有序序列，當前掃描的元素作為待插入元素，從有序序列中找到其適合的位置進行插入。

選擇排序是一種直觀的排序算法，其基本思想：從前往后走訪待排序序列，找出最小的元素置于待排序序列的首端；如此往復，直到待排序序列只包含一個元素。

快速排序是由Hoare提出，采用了分治（divide and conquer）策略：選取一個基準pivot，將序列劃分為兩個子序列，比pivot小的元素歸為左子序列，比pivot大（或等于）歸于右子序列；如此遞歸地劃分子序列直到無需劃分（即整體有序）。此劃分操作也被稱為partition；下圖給出以元素5為pivot的partition操作：

堆排序是指利用大頂堆（max heap）進行排序的算法，基本思想：依次刪除堆頂元素（待排序序列的最大值），將其置于待排序序列的末端；如此往復，直至堆為空。

歸并排序也是采用分治策略：將相鄰兩個有序的子序列進行歸并（merge）操作，如此往復，直到歸并成一個完整序列（排序完成）。初始時，子序列對應于每一個元素。

穩定性是衡量排序算法是否改變相等鍵值的次序的指標。典型地，比如快排因pivot的選取可能會改變相等鍵值的次序。各種排序算法的比較如下：

2. 題解

75. Sort Colors
數字0、1、2排序，采取類似選擇排序的思路，數字0放在首端，數字2放在尾端。

public void sortColors(int[] nums) {
  int low = 0, high = nums.length - 1;
  for (int k = 0; k <= high; k++) {
    if (nums[k] == 0)
      swap(nums, k, low++);
    else if (nums[k] == 2)
      swap(nums, k--, high--);
  }
}

private void swap(int[] A, int a, int b) {
  int temp = A[a];
  A[a] = A[b];
  A[b] = temp;
}

349. Intersection of Two Arrays
鏈表的插入排序。

public ListNode insertionSortList(ListNode head) {
  ListNode nHead = new ListNode(0), p = head, pNext, np, nPre;
  while (p != null) {
    // find the suitable position to insert
    for (np = nHead.next, nPre = nHead; np != null && np.val < p.val; ) {
      np = np.next;
      nPre = nPre.next;
    }
    nPre.next = p;
    pNext = p.next;
    p.next = np;
    p = pNext;
  }
  return nHead.next;
}

148. Sort List
排序鏈表，要求時間復雜度\(O(n \log n)\)、空間復雜度\(T(1)\)，所以使用歸并排序。其中，合并兩個有序鏈表復用了問題21. Merge Two Sorted Lists的代碼。

public ListNode sortList(ListNode head) {
  if (head == null || head.next == null) return head;
  ListNode pre = head, slow = head, fast = head;
  // cut the list into two halves
  while (fast != null && fast.next != null) {
    pre = slow;
    slow = slow.next;
    fast = fast.next.next;
  }
  pre.next = null;
  // sort the two halves
  ListNode l1 = sortList(head);
  ListNode l2 = sortList(slow);
  // merge the two sorted halves
  return mergeTwoLists(l1, l2);
}

242. Valid Anagram
判斷兩個字符串是否同構（變位詞）。將values數組排序后，判斷是否相等。

public boolean isAnagram(String s, String t) {
  char[] sValues = s.toCharArray();
  char[] tValues = t.toCharArray();
  Arrays.sort(sValues);
  Arrays.sort(tValues);
  return Arrays.equals(sValues, tValues);
}

56. Merge Intervals
合并重復的區間段。思路：排序區間，然后根據條件進行合并。

public List<Interval> merge(List<Interval> intervals) {
  if (intervals.size() <= 1) return intervals;
  intervals.sort((i1, i2) -> {
    if (i1.start == i2.start) return i1.end - i2.end;
    return i1.start - i2.start;
  });
  List<Interval> result = new ArrayList<>();
  for (int i = 0; i < intervals.size(); ) {
    int j, margin = intervals.get(i).end;
    for (j = i + 1; j < intervals.size(); j++) {
      if (intervals.get(j).start > margin)
        break;
      margin = Math.max(margin, intervals.get(j).end);
    }
    result.add(new Interval(intervals.get(i).start, margin));
    i = j;
  }
  return result;
}

57. Insert Interval
將一個區間插入到有序區間列表中，若有重復區間則需要做合并。

public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
  LinkedList<Interval> result = new LinkedList<>();
  if (intervals == null || intervals.isEmpty()) {
    result.add(newInterval);
    return result;
  }
  int len = intervals.size(), start, end, j;
  Interval interval;
  boolean hasAdded = false;
  for (int i = 0; i < len; ) {
    interval = intervals.get(i);
    if (interval.end < newInterval.start) { // newInterval is right-outside
      result.add(interval);
      i++;
    } else if (interval.start > newInterval.end) { // newInterval is left-outside
      if (!hasAdded) {
        result.add(newInterval);
        hasAdded = true;
      }
      result.add(interval);
      i++;
    } else {
      start = Math.min(interval.start, newInterval.start);
      end = Math.max(interval.end, newInterval.end);
      for (j = i + 1; j < len; j++) {
        interval = intervals.get(j);
        if (interval.start > end) break;
        end = Math.max(end, interval.end);
      }
      result.add(new Interval(start, end));
      hasAdded = true;
      i = j;
    }
  }
  if (!hasAdded) result.add(newInterval);
  return result;
}

274. H-Index
計算作者的h-index。思路：對引用次數數組排序，找出至少有h篇論文的引用次數>=h。

public int hIndex(int[] citations) {
  Arrays.sort(citations);
  int h = 0;
  for (int i = citations.length - 1; i >= 0; i--) {
    if (citations[i] < h + 1) break;
    h++;
  }
  return h;
}

275. H-Index II
與上類似，不同在于citations已排序，且是升序。

179. Largest Number
從一串數字中，找出能拼成的最大整數；相當于對整數字符串的排序。

public String largestNumber(int[] nums) {
  int len = nums.length;
  String[] strs = new String[len];
  for (int i = 0; i < len; i++) {
    strs[i] = String.valueOf(nums[i]);
  }
  Arrays.sort(strs, this::compareNum);
  // special case
  if (strs[0].charAt(0) == '0') return "0";
  StringBuilder builder = new StringBuilder();
  for (String str : strs) {
    builder.append(str);
  }
  return builder.toString();
}

// compare two number-strings
private int compareNum(String num1, String num2) {
  String cat1 = num1 + num2;
  String cat2 = num2 + num1;
  return cat2.compareTo(cat1);
}

349. Intersection of Two Arrays
求解兩個數組的交集，并去重。思路：排序兩個數組，然后做依次比較，用pre保存上一次添加元素（用于去重）。

public int[] intersection(int[] nums1, int[] nums2) {
  if (nums1 == null || nums2 == null) return null;
  Arrays.sort(nums1);
  Arrays.sort(nums2);
  int len1 = nums1.length, len2 = nums2.length, pre = 0;
  boolean hasAdded = false;
  ArrayList<Integer> common = new ArrayList<>();
  for (int i = 0, j = 0; i < len1 && j < len2; ) {
    if (nums1[i] < nums2[j])
      i++;
    else if (nums1[i] > nums2[j])
      j++;
    else {
      if (nums1[i] != pre || !hasAdded) {
        common.add(nums1[i]);
        pre = nums1[i];
        hasAdded = true;
      }
      i++;
      j++;
    }
  }
  int[] result = new int[common.size()];
  for (int i = 0; i < common.size(); i++) {
    result[i] = common.get(i);
  }
  return result;
}

350. Intersection of Two Arrays II
同上求交集，不需要做去重。