# 11. Sorting

## [8大排序算法图解](http://www.cricode.com/3212.html)

{% embed url="<https://visualgo.net/en/sorting>" %}

{% embed url="<https://leetcode.com/discuss/study-guide/1091763/Must-do-all-required-Sorting-Algorithms%3A-Complete-Guide>" %}

##

## 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)

## [快排为何这么快（比较快排和堆排）](http://mindhacks.cn/2008/06/13/why-is-quicksort-so-quick/)

## 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();
    }
```