演算法復習之分治與貪心（1）

經典演算法回顧

問題一：歸并排序

題目描述

給定一組數，將其從小到大排序，要求時間復雜度為，

分析

比較樸素的歸并排序演算法，本質思想就是將陣列不斷折半，最后將陣列全部拆分為長度為1或2的子陣列，然后進行排序后再合并到一起

解決方法

void merge(vector<int>& data, int start, int end) {
	int mid = start + (end - start) / 2;
	vector<int> left(mid - start, 0);
	vector<int> right(end - mid + 1, 0);
	for (int i = start; i < end; i++) {
		i < mid ? left.push_back(data[i]) : right.push_back(data[i]);
	}
	int i, j = 0;
	int index = start;
	while (i < left.size() && j < right.size()) {
		if (left[i] > right[j]) {
			data[index++] = right[j++];
		}
		else {
			data[index++] = left[i++];
		}
	}
	while (i < left.size()) {
		data[index++] = left[i++];
	}
	while (j < right.size()) {
		data[index++] = right[j++];
	}
}

void mergeSort(vector<int>& data, int start, int end) {
	if (start >= end) {
		return;
	}
	int mid = start + (end - start) / 2;
	mergeSort(data, start, mid);
	mergeSort(data, mid + 1, end);
	merge(data, start, end);
}

問題二：逆序對個數

題目描述

給定一個陣列，求其中所有的逆序對個數，

分析

其實本質上還是進行歸并排序，只不過在比較合并的程序中，如果前半個陣列中存在某一個值比后半個陣列中的值大，需要計數，最后求和即可，

解決方法

int merge(vector<int>& data, int start, int end, int sum) {
	int mid = start + (end - start) / 2;
	vector<int> left(mid - start, 0);
	vector<int> right(end - mid + 1, 0);
	for (int i = start; i < end; i++) {
		i < mid ? left.push_back(data[i]) : right.push_back(data[i]);
	}
	int i, j = 0;
	int index = start;
	while (i < left.size() && j < right.size()) {
		if (left[i] > right[j]) {
			sum += left.size() - i;
			data[index++] = right[j++];
		}
		else {
			data[index++] = left[i++];
		}
	}
	while (i < left.size()) {
		data[index++] = left[i++];
	}
	while (j < right.size()) {
		data[index++] = right[j++];
	}
	return sum;
}

int mergeSort(vector<int>& data, int start, int end, int sum) {
	if (start >= end) {
		return;
	}
	int mid = start + (end - start) / 2;
	sum += mergeSort(data, start, mid, sum);
	sum += mergeSort(data, mid + 1, end, sum);
	return merge(data, start, end, sum);
}

問題三：快速排序

題目描述

給定一個陣列，通過快速排序的方法將陣列進行排序，

分析

使用最基本的快速排序演算法即可實作，（注意雙指標的使用以及標準值的確定）

解決方法

void quickSort(vector<int> data, int start, int end) {
	if (start >= end) {
		return;
	}
	int leftPointer = start;
	int rightPointer = end + 1;
	int key = data[start];
	while (1) {
		while (data[++leftPointer] < key) {
			if (leftPointer == end) {
				break;
			}
		}
		while (data[--rightPointer] > key) {
			if (rightPointer == start) {
				break;
			}
		}
		if (leftPointer >= rightPointer) {
			break;
		}
		swap(data[leftPointer], data[rightPointer]);
	}
	data[start] = data[rightPointer];
	data[rightPointer] = key;
	quickSort(data, start, rightPointer - 1);
	quickSort(data, rightPointer + 1, end);
}

問題四：第k大數

問題描述

給定一個陣列，找出其中第k大的數，

分析

選用不同的排序方法可以以不同的時間復雜度解決該問題

解決方法

冒泡排序

int findKthLargestByBubble(vector<int> data, int k) {
	bool flag = true;
	for (int i = 0; i < k && flag; i++) {
		flag = false;
		for (int j = data.size() - 2; j >= i; j--) {
			if (data[j] < data[j + 1]) {
				swap(data[j], data[j + 1]);
				flag = true;
			}
		}
	}
	return data[k - 1];
}

其時間復雜度可以較為容易的判斷出，為，

選擇排序

int findKthLargestBySelection(vector<int> data, int k) {
	bool flag = true;
	for (int i = 0; i < k && flag; i++) {
		flag = false;
		for (int j = i + 1; j < data.size(); j++) {
			if (data[j] > data[i]) {
				swap(data[j], data[i]);
				flag = true;
			}
		}
	}
	return data[k - 1];
}

其時間復雜度與冒泡排序相同，但是這兩種排序演算法在資料量巨大時（即k和n規模相近），時間復雜度就會變為，計算效率將會大打折扣，

快速排序

int findKthLargestByQuickSort(vector<int> data, int k) {
	return find(data, 0, data.size(), k);
}

int find(vector<int> data, int start, int end, int k) {
	int key = data[start];
	int leftPointer = start;
	int rightPointer = end + 1;
	while (1) {
		while (data[++leftPointer] < key) {
			if (leftPointer == end) {
				break;
			}
		}
		while (data[--rightPointer] > key) {
			if (rightPointer == start) {
				break;
			}
		}
		if (leftPointer >= rightPointer) {
			break;
		}
		swap(data[leftPointer], data[rightPointer]);
	}
	data[start] = data[rightPointer];
	data[rightPointer] = key;
	if (rightPointer == k - 1) {
		return key;
	}
	else if (rightPointer > k - 1) {
		return find(data, start, rightPointer - 1, k);
	}
	else {
		return find(data, rightPointer + 1, end, k);
	}
}

由于最差也只是經過一次對陣列的完整搜索，所以其時間復雜度為，

還有其余的排序方法，例如堆排序、歸并排序等，其時間復雜度均為，