Garden | Sort

算法解释

排序算法可视化：

https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html

BubbleSort

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


void bubbleSort(vector<int>& nums) {
    int n = nums.size();

    for (int j = n-1; j >= 0; j--) {
        bool sorted = true;
        for (int i = 0; i < j; i++) {
            if (nums[i] > nums[i+1]) {
                swap(nums[i], nums[i+1]);
                sorted = false;
            }
        }
        if (sorted) break;
    }
}

InsertSort

每次将一个数字插入一个有序的数组里，成为一个长度更长的有序数组，有限次操作以后，数组整体有序。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


void insertSort(vector<int>& array) {
	int len = array.size();
	if (len <= 0) return;

	for (int i = 1; i < len; i++) {
		int target = array[i];
		int j = i;
		while (j > 0 && array[j-1] > target) {
    		array[j] = array[j-1];
			j--;
		}
		array[j] = target;
	}
}

QuickSort

快速排序主要思想通过划分将待排序的序列分成前后两部分，其中前一部分的数据都比后一部分的数据要小，然后再递归调用函数对两部分的序列分别进行快速排序，以此使整个序列达到有序。

主要难点在 partition 函数的实现：

选择 nums[r] 作为 pivot
记录指针 i，表示在 [l, i] 数组元素 <= pivot
遍历指针 j，每次加一
遍历完毕之后，交换 nums[i] 与 nums[r]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


    int partition(vector<int>& nums, int l, int r) {
        int pivot = nums[r];
        int i = l;
        for (int j = l; j <= r - 1; ++j) {
            if (nums[j] <= pivot) {
                swap(nums[i], nums[j]);
                i = i + 1;
            }
        }
        swap(nums[i], nums[r]);
        return i;
    }

   int randomized_partition(vector<int>& nums, int l, int r) {
        int i = rand() % (r - l + 1) + l; // 随机选一个作为我们的主元
        swap(nums[r], nums[i]);
        return partition(nums, l, r);
    }

   void quicksort(vector<int>& nums, int l, int r) {
        if (l < r) {
            int pos = randomized_partition(nums, l, r);
            quicksort(nums, l, pos - 1);
            quicksort(nums, pos + 1, r);
        }
    }

    vector<int> sortArray(vector<int>& nums) {
        srand((unsigned)time(NULL));
        quicksort(nums, 0, (int)nums.size() - 1);
        return nums;
    }

MergeSort

定义 mergeSort(nums, l, r) 函数表示对 nums 数组里 [l,r] 的部分进行排序，整个函数流程如下：

递归调用函数 mergeSort(nums, l, mid) 对 nums 数组里[l,mid] 部分进行排序。
递归调用函数 mergeSort(nums, mid + 1, r) 对 nums 数组里 [mid+1,r] 部分进行排序。
此时 nums 数组里 [l,mid] 和 [mid+1,r] 两个区间已经有序，我们对两个有序区间线性归并即可使 nums 数组里 [l,r] 的部分有序。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


void merge(vector<int>& array, int left, int mid, int right) {
	int i = left, j = mid+1;
	vector<int> result;
	while (i <= mid && j <= right) {
		if (array[i] < array[j]) {
			result.push_back(array[i++]);
		} else {
			result.push_back(array[j++]);
		}
	}
	while (i <= mid) result.push_back(array[i++]);
	while (j <= right) result.push_back(array[j++]);

	copy(result.begin(), result.end(), array.begin()+left);
}

void mergeSort(vector<int>& array, int left, int right) {
	if (left >= right) return;

	int mid = (left + right) / 2;
	mergeSort(array, left, mid);
	mergeSort(array, mid+1, right);
	merge(array, left, mid, right);
}

Quick Select

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


int partition(vector<int>& array, int l, int r) {
	int pivot = array[r];
	int i = l;
	for (int j = l; j <= r-1; j++) {
		if (array[j] <= pivot) {
			swap(array[i], array[j]);
			i++;
		}
	}
	swap(array[i], array[r]);
	return i;
}

int kthSmallest(vector<int>& array, int l, int r, int k) {
	if (k > 0 && k <= r-l+1) {
		int index = partition(array, l, r);
		if (index-l+1 == k) return array[index];
		if (index-l+1 > k) return kthSmallest(array, l, index-1, k);
		return kthSmallest(array, index+1, r, k-index+l-1);
	}
	return INT_MAX;
}

TopoSort

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34


#include <iostream>  
  
class Graph {  
private:  
    int V; // number of vertices  
    list<int> *adj; // pointer to an array containing adjacency listsList  
public:  
    Graph(int v);  
    AddEdge(int v, int w);  
    TopologicalSort();  
};  
  
Graph::Graph(int v) {  
    V = v;  
    adj = new list<int>[v];  
}  
  
Graph::AddEdge(int v, int w) {  
    adj[v].push_back(w);  
}  
  
Graph::TopologicalSort() {  
    stack<int> stk;  
  
    bool* visited = new bool[V];  
  
    for (int i = 0; i < V; i++)  
        visited[i] = false;  
    
}  
  
int main() {
    
}

Heap Sort

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35


void heapSort(vector<int>& nums) {
    int n = nums.size();

    heapify(nums);

    int i = n - 1;
    while (i >= 1) {
        swap(nums[0], nums[i]);
        i--;
        siftDown(nums, 0, i);
    }
}

void heapify(vector<int>& nums) {
    int n = nums.size();
    for (int i = (n-1)/2; i >= 0; i--) {
        siftDown(nums, i, n-1);
    }
}

void siftDown(vector<int>& nums, int k, int end) {
    while (2*k+1 <= end) {
        int j = 2*k+1;
        if (j+1 <= end && nums[j+1] > nums[j]) {
            j++;
        }

        if (nums[j] > nums[k]) {
            swap(nums[j], nums[k]);
        } else {
            break;
        }
        k = j;
    }
}

BucketSort

题解

31 Next Permutation
- O(n) time (worst case is reverse) and O(1) space by finding the least significant number a i.e. there is b less significant than b and a < b.
- Simulating the DFS stack and judging at each depth whether the chose one is the maximum in possible number set also works.
57 Insert Interval
- O(nlog(n)) time by sorting and merge.
- O(n) time by direct insert.
179 Largest Number
- Given a list of non-negative integers, concatenate them into the largest number.
- O(nlog(n)) time by custom sorting. For any two numbers, compare which should be the first to form a larger number when they form a new number. For example, 30|309 vs. 309|30.
274 H-Index
- Given a citation list, find the author’s H-index.
- O(nlog(n)) time by sorting.
- O(n) time by radix sorting. Any citation larger than n can be treated as n.
280 Wiggle Sort
- Given a sorted array A, no replica, sort it i.e. A[0] < A[1] > A[2] < A[3] …
- O(n) time by swapping neighbors.
296 Best Meeting Point
- Given points in a grid, find the point where sum of manhattan distance from given points to it is minimized.
- Find the median.
324 Wiggle Sort II
- Given an array A, might with replica, sort it i.e. A[0] < A[1] > A[2] < A[3] …
- Average O(n) time by quick selection and push >mid to left and < mid to right.
370 Range Addition
- Given a range [0, n] and several range updates, give final values of all points.
- O(nlog(n)) time by sorting the ranges and line sweeping.
- O(n) time and O(1) space by changing range bounds and using prefix sum.
451 Sort Characters By Frequency
493 Reverse Pairs
- Given a number array, find all (i,j) pairs that num[i] > num[j] * 2.
- Instrumented merge sort or BIT or BST(trie) with binary search. 315 and 327 are the same paradigm.
539 Minimum Time Difference
- Given timestamps, find minimum difference. Sort and scan.
759 Employee Free Time
- Sort and find holes in intervals.
969 Pancake Sorting
- Sort an array by reversing its prefixes.
- The minimum number question is NP-hard. See Wikipedia
973 K Closest Points to Origin
1057 Campus Bikes
- Given positions of bikes and persons, match shortest manhattan distances.
- Sort bike-person pairs according to their distances.

912 Sort an Array

https://leetcode.com/problems/sort-an-array

这是最基本的 Sort 题目，在这个题目下，可以实现各种 Sort 算法。

215 Kth Largest Element in an Array

https://leetcode.com/problems/kth-largest-element-in-an-array/description

最简单可以通过 heap 做

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int>> q;

        for (auto& n : nums) {
            if (q.size() <= k || n >= q.top()) {
                q.push(n);
                if (q.size() > k) {
                    q.pop();
                }
            }
        }

        return q.top();
    }
};

但是面试一般不会让你这么简单

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35


class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int size = nums.size();
        int l = 0, r = size-1;

        if (k < 0 || k > size) return -1;

        while (true) {
            int pos = partition(nums, l, r);
            if (pos == k-1) return nums[pos];
            if (pos > k-1) r = pos-1;
            else l = pos+1;
        }

        return -1;

    }

    int partition(vector<int>& nums, int l, int r) {
        int pivot = nums[r];

        int i = l;

        for (int j = l; j <= r-1; j++) {
            if (nums[j] > pivot) {
                swap(nums[j], nums[i]);
                i++;
            }
        }
        swap(nums[i],nums[r]);

        return i;
    }
};

148 Sort List

https://leetcode.com/problems/sort-list

O (nlog (n)) time by merge sort. O(1) space by bottom-up sorting.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        return MergeSort(head);
    }

    ListNode* MergeSort(ListNode* head) {
        if (head == nullptr || head->next == nullptr) return head;

        ListNode* p1 = head;
        ListNode* p2 = head->next;

        while (p2 && p2->next) {
            p1 = p1->next;
            p2 = p2->next->next;
        }

        ListNode* h1 = head;
        ListNode* h2 = p1->next;
        p1->next = nullptr;

        ListNode* t1 = MergeSort(h1);
        ListNode* t2 = MergeSort(h2);
        return Merge(t1, t2);
    }

    ListNode* Merge(ListNode* p, ListNode* q) {
        ListNode* pre = new ListNode(-1);
        ListNode* cur = pre;

        while (p && q) {
            if (p->val <= q->val) {
                ListNode* tmp = p->next;
                cur->next = p;
                cur = cur->next;
                p = tmp;
            } else {
                ListNode* tmp = q->next;
                cur->next = q;
                cur = cur->next;
                q = tmp;
            }
        }

        if (p) cur->next = p;
        if (q) cur->next = q;

        return pre->next;
    }
};

75 Sort Colors

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


class Solution {
public:
    void sortColors(vector<int>& nums) {
        int n = nums.size();
        int l = 0, r = n-1;
        int i = 0;

        while (r >= 0 && nums[r] == 2) r--;
        while (i <= r) {
            if (nums[i] == 2) {
                swap(nums[i], nums[r]);
                r--;
            } else if (nums[i] == 1) {
                i++;
            } else {
                nums[i] = nums[l];
                nums[l] = 0;
                l++;
                i++;
            }
        }
    }
};

315. Count of Smaller Numbers After Self

https://leetcode.com/problems/count-of-smaller-numbers-after-self

参考资料

https://leetcode-cn.com/circle/discuss/KIfqN3/