11. Sorting

8大排序算法图解

Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix) - VisuAlgovisualgo.net

Must do all required Sorting Algorithms: Complete Guide - Discuss - LeetCodeLeetCode

Bubble sort

1. 2 for loops

2. every time compare and swap 2 adjacent elements

3. find the largest element and move to the end

4. Time: O(N^2) and space: O(1)

Selection Sort

1. 2 for loops

2. every loop find the smallest element and move to the beginning

3. split the arrays into 2 parts, sorted subarray and unsorted subarray

4. Time: O(N^2) and space: O(1)

快排为何这么快（比较快排和堆排）

Largest Number

• 给一个int[] nums, 返回一个用nums里的num组成的最大的数

• custom sort: basically implement a String comparator to decide which String should come first during concatenation

public String largestNumber(int[] nums) {
        String[] arr = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            arr[i] = String.valueOf(nums[i]);
        }
        Arrays.sort(arr, new Comparator<String>() {
                @Override
                public int compare(String a, String b) {
                    String s1 = a + b;
			        String s2 = b + a;
			        return s2.compareTo(s1); // reverse order here, so we can do append() later
                }
            });
        if (arr[0].charAt(0) == '0') {
            return "0"; // edge case, list of "0"
        }
        StringBuilder sb = new StringBuilder();
        for (String s : arr) {
            sb.append(s);
        }
        return sb.toString();
    }