排序算法学习笔记

• 1 快速排序（分治）
• • 1.1 算法流程
  • 1.2 算法代码
• 2 堆排序（二叉树）
• • 2.1 算法流程
  • 2.2 算法代码

假设对长度为 N N N的数组 n u m s nums nums进行升序排序。
(1) 确定第 i i i次排序的范围 [ l i , r i ] [l_i,r_i] [li​,ri​]以及基准点 n u m s [ m i ] nums[m_i] nums[mi​]。其中， l i ≤ m i ≤ r i l_i leq m_i leq r_i li​≤mi​≤ri​随机产生， 0 ≤ l i , r i ≤ N − 1 0 leq l_i, r_i leq N-1 0≤li​,ri​≤N−1。核心思想：在第 i i i次排序中，将比基准点大的值放在其右侧，比基准点小的值放在其左侧。
(2) 将基准点放在右端， s w a p ( n u m s [ m i ] , n u m s [ r i ] ) swap(nums[mi],nums[ri]) swap(nums[mi],nums[ri])，则待排序范围为 [ l i , r i − 1 ] [l_i,r_i-1] [li​,ri​−1]。同时， l i − 1 l_i-1 li​−1表示已经排序，且比基准点小的数值的最右侧的索引。
(3) 令 j j j遍历 [ l i , r i − 1 ] [l_i,r_i-1] [li​,ri​−1]，若 n u m s [ j ] < n u m s [ r i ] nums[j] < nums[r_i] nums[j] (4) j j j完成遍历后， s w a p ( n u m s [ l i ] , n u m s [ r i ] ) swap(nums[l_i],nums[r_i]) swap(nums[li​],nums[ri​])，即将基准点放回。此时，基准点左侧的值均小于基准点，右侧的值均大于等于基准点。
(5) 重复步骤(1)~(4)，直到对完成对所有元素的排序。

void quickSort(vector& nums, int l, int r) {
	if (l < r) {
		int m = rand() % (r - l + 1) + l;
		swap(nums[m], nums[r]);
		m = l; // 复用变量m，此时记录原始左端索引

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

vector sortArray(vector& nums) {
	int N = nums.size();
	srand(time(0));
	quickSort(nums, 0, N - 1);
	return nums;
}

堆排序的典型应用场景：每次排序可以获得未排序数组中的最大值（大根堆）或最小值（小根堆），经历过 K ≤ N K leq N K≤N次排序后，即可找到前 K K K个最大值或最小值。
堆排序利用二叉树进行记录数据，其中父节点 i i i的值一定大于子节点 2 i + 1 2i+1 2i+1和 2 i + 2 2i+2 2i+2的值。其中， 0 ≤ i , 2 i + 1 , 2 i + 2 ≤ N − 1 0 leq i,2i+1,2i+2 leq N-1 0≤i,2i+1,2i+2≤N−1。
(1) 自下而上地创建堆。创建的堆满足上述性质。
(2) s w a p ( n u m s [ 0 ] , n u m s [ N − 1 ] ) swap(nums[0],nums[N-1]) swap(nums[0],nums[N−1])，依据堆的性质 n u m s [ 0 ] nums[0] nums[0]为最大值，则按照升序排序的规则，将其交换到数组尾端，并更新数组范围 N = N − 1 N=N-1 N=N−1。
(3) 自上而下地维护堆的性质。由于步骤(2)，堆的性质被破坏，需要重新维护堆的性质。

void heapify(vector &arr, int N, int i) {
	int m = i, l = 2 * i + 1, r = 2 * i + 2;
	
	if (l < N && arr[l] > arr[m]) {
		m = l;
	}
	
	if (r < N && arr[r] > arr[m]) {
		m = r;
	}

	if (m != i) {
		swap(arr[m], arr[i]);
		heapify(arr, N, m);
	}
}

void heapSort(vector &arr) {
	int N = arr.size();
	// (1) “自下而上”创建大根堆
	for (int i = N / 2 - 1; i >= 0; --i) {
		heapify(arr, N, i);
	}
	// 排序
	while (N > 1) {
		// (2) 将最大值调换到尾端
		swap(arr[0], arr[--N]);
		// (3) “自上而下”维护大根堆
		heapify(arr, N, 0);
	}

}

int main()
{	
	vector nums = {4, 5, 8, 2, 3, 1, 7, 6};
	// 大根堆实现升序排序
	heapSort(nums);
	for (const int& num : nums) {
		cout << num << endl;
	}
	return 0;
}