排序

排序是实际运用中比较常见的情况。计算机界也对排序进行了很深入的研究。常见的排序算法有：快速排序、归并排序、插入排序、堆排序等等。
在一些算法题目当中，排序经常是作为一个实现的前提条件。比如求解 Kth Element 问题或者 TopK Elements 问题。
LeedCode中就有一些题目是需要采用排序解决或者解决排序问题。
1、找到第K大元素
215. Kth Largest Element in an Array (Medium)
题目可以采用各种方法：如各种排序算法、K个元素的堆排序等。。

/*采用go语言自带的排序算法（快排）后直接返回倒数第K个元素*/
func findKthLargest(nums []int, k int) int {
    sort.Sort(sort.IntSlice(nums))
    length := len(nums)
    return nums[length-k] 
}

/*Java的优先级序列来作为堆实现*/
public int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer> pq = new PriorityQueue<>(); // 小顶堆
    for (int val : nums) {
        pq.add(val);
        if (pq.size() > k)  // 维护堆的大小为 K
            pq.poll();
    }
    return pq.peek();
}

2、桶排序
如题目1：出现频率最多的 k 个数
347. Top K Frequent Elements (Medium)

Given [1,1,1,2,2,3] and k = 2, return [1,2].

//利用桶排序。
func topKFrequent(nums []int, k int) []int {
    //1、先统计各个数字出现的次数
    var m = make(map[int]int)
    for _,v := range nums {
        if val,ok := m[v];ok{
            m[v] = val+1
        }else {
            m[v] = 1
        }
    }
    //此时m为统计好的各个数字出现次数的map
    //2、利用桶，下标表示出现的次数，val是个list，存放相同次数的数字。
    var bucket = make([][]int,len(nums)+1)
    for k,v := range m {
        if bucket[v] == nil {
            temp := []int{k}
            bucket[v] = temp
        }else {
            bucket[v] = append(bucket[v],k)
        }
    }
    //此时bucket是按照次数出现的桶
    //3、从后往前遍历通，拿到要出现的单词
    var result []int
    for i:=len(bucket)-1;i!=0&&k!=0;i-- {
        if bucket[i] != nil {
            result = append(result, bucket[i]...)
            k = k-len(bucket[i])
        }
    }
    return result
}

题目2：按照字符出现次数对字符串排序
451. Sort Characters By Frequency (Medium)

Input:
"tree"

Output:
"eert"

Explanation:
'e' appears twice while 'r' and 't' both appear once.
So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.

//利用桶排序。
func frequencySort(s string) string {
    bt := []byte(s)
     //1、先统计各个字母出现的次数
     var m = make(map[byte]int)
     for _,v := range bt {
        if val,ok := m[v];ok{
            m[v] = val+1
        }else {
            m[v] = 1
        }
    }
    //此时m为统计好的各个字母出现次数的map
    //2、利用桶，下标表示出现的次数，val是个list，存放相同次数的字母。
    var bucket = make([][]byte,len(s)+1)
    for k,v := range m {
        if bucket[v] == nil {
            temp := []byte{k}
            bucket[v] = temp
        }else {
            bucket[v] = append(bucket[v],k)
        }
    }
     //此时bucket是按照次数出现的桶
    //3、从后往前遍历通，拿到要出现的单词
    var result []byte
    for i:=len(bucket)-1;i!=0;i-- {
        if bucket[i] != nil {
            for k:=0;k!=len(bucket[i]);k++ {
                for j:=0;j!=i;j++ {
                    result = append(result,bucket[i][k])
                }
            }
        }
    }
    return string(result)
}

3、双（多）指针+排序
问题：荷兰国旗问题
荷兰国旗包含三种颜色：红、白、蓝。

有三种颜色的球，算法的目标是将这三种球按颜色顺序正确地排列。

它其实是三向切分快速排序的一种变种，在三向切分快速排序中，每次切分都将数组分成三个区间：小于切分元素、等于切分元素、大于切分元素，而该算法是将数组分成三个区间：等于红色、等于白色、等于蓝色。
75. Sort Colors (Medium)

Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

/*采用前后两个指针指向两端的颜色标记然后用一个遍历指针从前往后遍历，
遇到red或者blue则交换到相应red和blue指针的位置，
然后继续往前找(注意边界关系，
搜索指针找到red交换后要继续往前，找到blue的时候不能往前还要比较一次，
当搜索指针与blue相遇时也要比一次)*/

func sortColors(nums []int)  {
    l,r := 0,len(nums)-1;
    for i:=0;i<= r;{
        if nums[i] == 0 { //扫描到red
            swap(nums,i,l)
            l++
            i++
        }else if  nums[i] == 2 { //扫描到blue
            swap(nums,i,r)
            r--
        }else {
            i++
        }
    }
}

func swap(nums []int,i int, j int) {
    temp := nums[i]
    nums[i] = nums[j]
    nums[j] = temp
}

思考：如果是K个元素如此排序怎么办。