排序总结、快速选择、荷兰国旗问题

相关概念

稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。

选择排序Selection Sort

在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

selection_sort.gif

1
2
3
4
5
6
7
8
9
10
public void selectionSort(int[] nums){
	int N = nums.length;
	for(int i  = 0; i < N; i++){
		int min = i;
		for(int j = i+1; j < N; j++){
			if(nums[j] < nums[min]){ min = j; }
		}
		swap(nums, i, min);
	}
}

算法分析：不论初始排序如何，都是(N-1)+(N-2)+…+1 ~ $N^2/2$次比较，N次交换
时间复杂度O($n^2$)，空间复杂度O(1)
特点：n次交换，不稳定排序((7) 2 5 9 3 4 [7] 1…当我们利用直接选择排序算法进行排序时候,(7)和1调换,(7)就跑到了[7]的后面了,原来的次序改变了)
😁优点：不占用额外的内存空间
😢缺点：时复大
💡应用场景：数据规模较小且对内存空间有限制时

插入排序Insertion Sort

对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

insertion_sort.gif

1
2
3
4
5
6
7
8
public void insertionSort(int[] nums){
	int N = nums.length;
	for(int i = 1; i < N; i++){
		for(int j = i; j > 0 && nums[j] < nums[j-1]; j--){
			swap(nums, j, j-1);
		} 
	}
}

算法分析：
最好情况O(n)-初始序列已经是升序: N-1次比较
最坏情况O($n^2$)-初始序列是降序(N-1)+(N-2)+…+1 ~ $N^2/2$次比较，$N^2/2$次交换
平均情况O($n^2$)-每个nums[i]都向前移动一半到nums[i/2] ~ $N^2/4$次比较，$N^2/4$次交换
空间复杂度O(1)
特点：稳定排序(因为插入的过程中都是从后向前进行查找，遇到小于等于(或大于等于)的数停止寻找，进行插入操作。不改变排序前后相等数值的相对顺序)
😁优点：不占用额外的内存空间
😢缺点：时复大
💡应用场景：数据规模较小或者部分数组已排序，且对内存空间有限制时

【优化1】插入排序+二分查找：通过二分查找快速找到插入位置，减少比较次数
比较次数降为O($logn$)，交换次数仍为O($n^2$)

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
public void binaryInsertSort(int[] nums){
	int N = nums.length;
	for(int i = 1; i < N; i++){
		int val = nums[i];
		if(nums[i] < nums[i-1]){
			//二分法求插入位置
			int idx = binarySearch(nums, i); 
			//将插入位置到i-1的数向后移动一位
			for(int j = i; j > idx; j--){ nums[j] = nums[j-1]; }
			nums[idx] = val;
		}
	}
}
private int binarySearch(int[] nums, int n){
	int l = 0;
	int r = n-1;
	int target = nums[n];
	while(l <= r){
		int m = l + (r - l) / 2;
		if(nums[m] < target) l = m + 1;
		else if(nums[m] > target) r = m - 1;
		else return m+1;
	}
	return l;
}

【优化2】希尔排序Shell Sort：增加比较间隔-分治思想：对子序列排序→整个序列有序
插入排序的缺点是一次只换一个位置，希尔排序一次可以移动大于1的位置，时复减小。1959年Shell发明，第一个突破O($n^2$)的排序算法。

希尔排序采用分治思想(Divide and Conquer)，先将整个序列分割成若干小的子序列，再分别对子序列进行直接插入排序，使得原来序列成为基本有序。这样通过对较小的序列进行插入排序，然后对基本有序的数列进行插入排序，能够提高插入排序算法的效率。其核心在于间隔序列的设定。

shell_sort.gif

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public void shellSort(int[] nums){
	int N = nums.length;
	int dist = 1;
	while(dist < N/3){ dist = dist*3+1; } //间隔为...40，13，4，1

	while(dist >= 1){
		insertionSort(nums, N, dist);
		dist = dist / 3;
	}
}
private void insertionSort(int[] nums, int N, int dist){
	// 0~i-1为有序区，i~N-1为无序区
	for(int i = dist; i < N; i++){
		for(int j = i; j >= dist && nums[j] < nums[j-dist]; j -= dist){
			swap(nums, j, j-dist);
		}
	}
}

算法分析：
最好情况O(n)-初始序列已经是升序: N-1次比较
最坏情况：O($nlogn$)
平均情况：O($nlogn$)
增量选取：希尔排序的时间复杂度与增量选取有关，但现今没有人能找出希尔排序的精确下界。
特点：不稳定排序(因为在进行分组时，相同元素可能分到不同组中，改变相同元素的相对顺序)
💡应用场景：希尔排序在最坏的情况下和平均情况下执行效率相差不是很多，与此同时快速排序（O(logn)）在最坏的情况下执行的效率会非常差。专家们提倡，几乎任何排序工作在开始时都可以用希尔排序，若在实际使用中证明它不够快，再改成快速排序这样更高级的排序算法.

【优化3】希尔排序+二分查找：通过二分查找快速找到插入位置，减少比较次数

合并排序Merge sort

递归(top-down)-recursion

merge_sort_recursive.png

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
public int[] mergeSort(int[] nums){
	int[] temp = new int[nums.length];
	// helper function
	sort(nums, 0, nums.length-1, temp);
	return nums;
}
private void sort(int[] nums, int lo, int hi, int[] temp){
	if(lo >= hi) return;
	int mid = lo + (hi - lo) / 2;
	sort(nums, lo, mid, temp);
	sort(nums, mid+1, hi, temp);
	merge(nums, lo, hi, temp);
}
private void merge(int[] nums, int lo, int hi, int[] temp){
	int mid = lo + (hi - lo) / 2;
	int i = lo;
	int j = mid+1;
	int k = lo;
	while(i <= mid && j <= hi){
		if(nums[i] < nums[j]){ temp[k++] = nums[i++]; }
		else{ temp[k++] = nums[j++]; }
	}
	while(i <= mid){ temp[k++] = nums[i++]; }
	while(j <= hi){ temp[k++] = nums[j++]; }
	// copy back to original array
	for(int p = lo; p <= hi; p++){
		nums[p] = temp[p];
	}
}

算法分析：
最好情况O($nlogn$)-初始序列已经是升序: $(nlogn)/2$次比较
最坏情况：O($nlogn$)
平均情况：O($nlogn$)
时间复杂度：O($nlogn$)；空间复杂度O(n)(其中递归需要logn)
特点：稳定排序，任何情况都保证时复为O(nlogn)

【优化1】交换sort()里的数组，省去merge()里复制数组的步骤

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
private void sort(int[] nums, int lo, int hi, int[] temp){
	if(lo >= hi) return;
	int mid = lo + (hi - lo) / 2;
	sort(temp, lo, mid, nums);
	sort(temp, mid+1, hi, nums);
	merge(nums, lo, hi, temp);
}
private void merge(int[] nums, int lo, int hi, int[] temp){
	int mid = lo + (hi - lo) / 2;
	int i = lo;
	int j = mid+1;
	int k = lo;
	while(i <= mid && j <= hi){
		if(nums[i] < nums[j]){ temp[k++] = nums[i++]; }
		else{ temp[k++] = nums[j++]; }
	}
	while(i <= mid){ temp[k++] = nums[i++]; }
	while(j <= hi){ temp[k++] = nums[j++]; }
	
	// no need for copying
}

【优化2】若前半和后半sort完，整体已经是sorted，则不用再merge
O(n): n-1次比较， why?

1
2
3
4
5
6
7
8
private void sort(int[] nums, int lo, int hi, int[] temp){
	if(lo >= hi) return;
	int mid = lo + (hi - lo) / 2;
	sort(nums, lo, mid, temp);
	sort(nums, mid+1, hi, temp);
	if(nums[mid] < nums[mid+1]) return; //用前半的最后一个元素是否小于后半第一个元素来判断
	merge(nums, lo, hi, temp);
}

【优化3】对于小的数组用插入排序，减少空间占用

1
2
3
4
5
6
7
8
9
10
11
private void sort(int[] nums, int lo, int hi, int[] temp){
	if(lo >= hi) return;
	if((hi - lo + 1) <= CUTOFF){
		insertionSort(nums, lo, hi);
		return;
	}
	int mid = lo + (hi - lo) / 2;
	sort(nums, lo, mid, temp);
	sort(nums, mid+1, hi, temp);
	merge(nums, lo, hi, temp);
}

迭代(bottom-up)-iterative

merge_sort_iterative.png

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
public int[] mergeSort(int[] nums){
	int N = nums.length;
	int[] temp = new int[N];
	for(int sz = 1; sz < N; sz *= 2){
		for(int lo = 0; lo < N-sz; lo += sz+sz){
			merge(nums, lo, Math.min(lo+sz+sz-1,N-1), temp);
		}
	}
	return nums;
}
private void merge(int[] nums, int lo, int hi, int[] temp){
	int mid = lo + (hi - lo) / 2;
	int i = lo;
	int j = mid+1;
	int k = lo;
	while(i <= mid && j <= hi){
		if(nums[i] < nums[j]){ temp[k++] = nums[i++]; }
		else{ temp[k++] = nums[j++]; }
	}
	while(i <= mid){ temp[k++] = nums[i++]; }
	while(j <= hi){ temp[k++] = nums[j++]; }
	// copy back to original array
	for(int p = lo; p <= hi; p++){
		nums[p] = temp[p];
	}
}

快速排序Quick sort

选择pivot，比pivot小的排前面，比pivot大的排后面

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int[] quickSort(int[] nums){
	qsort(nums, 0, nums.length - 1);
	return nums;
}
private void qsort(int[] nums, int lo, int hi){
	if(lo >= hi) return;
	int pivot = partition(nums, lo, hi);
	qsort(nums, lo, pivot - 1);
	qsort(nums, pivot + 1, hi);
}
private int partition(int[] nums, int lo, int hi){
	int pivot = nums[hi];
	int k = lo;
	for(int i = lo; i < hi; i++){
		if(nums[i] < pivot){
			swap(nums, k, i);
			k++;
		}
	}
	swap(nums, k, hi);
	return k;
}
private void swap(int[] nums, int i, int j){ ... }

算法分析：
最好情况O(nlogn)-每次选择的pivot都是中位数
最坏情况O(n^2)-每次选择的pivot都是最小/最大数
平均情况O(nlnn)

quick_sort.png

特点：不稳定，但是只要不是worst case，时复O(nlogn)比merge sort的快
😁优点：不占用额外的内存空间(in-place算法)
😢缺点：若遇到worst case则时复高达O($n^2$)
💡应用场景：通常是最优解法

快速选择Quick Select：常用于第k大/小的问题

利用快速排序中当每个iteration结束，pivot的位置就是其最终已排序位置

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
public int findKthLargest(int[] nums, int k){
	k = nums.length - k; //千万别忘了这句！！！若是findKthSmallest则省略这句
	int lo = 0;
	int hi = nums.length - 1;
	while(lo < hi){
		int pivot = partition(nums, lo, hi);
		if(pivot == k) return nums[k];
		else if(pivot < k) lo = pivot + 1;
		else hi = pivot - 1;
	}
	return nums[k];
}
private int partition(int[] nums, int lo, int hi){
	int pivot = nums[hi];
	int k = lo;
	for(int i = lo; i < hi; i++){
		if(nums[i] < pivot){
			swap(nums, k, i);
			k++;
		}
	}
	swap(nums, hi, k);
	return k;
}
private void swap(int[] nums, int i, int j){ ... }

荷兰国旗问题：优化quick sort，使其支持duplicate keys，3-way partitioning

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public void sort(int[] nums){
	int lo = 0;
	int hi = nums.length - 1;
	int p = 0;
	while(p <= hi){
		if(nums[p] == 0){
			swap(nums, p, lo);
			lo++;
			p++;
		}else if(nums[p] == 2){
			swap(nums, p, hi);
			hi--; //因为不知道nums[hi]的大小，所以p和hi交换后，不进行p++
		}else{
			p++;
		}
	}
}

桶排序Bucket sort：常用于top k问题

详见top k问题总结

堆排序Heap sort

推荐Youtube Back to Back SWE频道的讲解：https://www.youtube.com/watch?v=k72DtCnY4MU
Binary Heap性质：k的父结点在k/2，子结点在2k+1和2k+2

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
public int[] heapSort(int[] nums){
	//从nums的一半开始向前将元素按max heap的顺序重排，因为会swap所以不必从nums最后一元素向前遍历整个nums
	int n = nums.length - 1;
	for(int i = (n-1)/2; i >= 0; i--){
		heapify(nums, n, i);
	}
	//此时，max heap建立完成，root为最大的数
	//将heap的last node与root对调，移走last node，heap大小-1，重新排序
	for(int i = n; i >= 0; i--){
		swap(nums, 0, i);
		heapify(nums, i, 0);
	}
}
private void heapify(int[] nums, int n, int i){
	int max = i;
	int l = 2 * i + 1;
	int r = 2 * i + 2;
	if(l < n && nums[l] > nums[max]) max = l;
	if(r < n && nums[r] > nums[max]) max = r;
	if(max != i){
		swap(nums, max, i);
		heapify(nums, n, max);
	}
}
private void swap(int[] nums, int i, int j){ ... }

Java里Arrays.sort()的实现

sort reference类型时，用merge sort。因为稳定，且保证时复O(nlogn)
sort primitive类型时，用quick sort。因为quick sort在实际应用中用的内存更少、更快