计算机科学基础算法基本概念
Source
Edit
History

2.认识 O(NlogN) 的排序2

第一节、master 公式

​ 在编程中，递归是非常常见的一种算法，由于代码简洁而应用广泛，但递归相比顺序执行或循环程序，时间复杂度难以计算，而master公式就是用于计算递归程序的时间复杂度。

1
T(N) = a*T(N/b) + O(N^d);

​ 下面对参数进行解释:

  • b：子过程的样本量
  • a：子过程的计算次数
  • O(N^d)：子结果合并的时间复杂度

满足如上公式的程序都可以根据master公式计算时间复杂度：

  • log(b，a) > d ：时间复杂度为O(N^log(b，a))
  • log(b，a) = d ：时间复杂度为O(N^d * logN)
  • log(b，a) < d ：时间复杂度为O(N^d)

第二节、求中值

​ 在学习归并排序之前，我们先学习一个简单的算法:当我们求一个值的中值时，可以使用：

1
int mid = L + ((R - L) >> 1);

​ 这样可以避免内存泄露。

第三节、归并排序

​ 归并排序:归并排序也是将速度分别有序化的过程,先解释合并的部分。我们假设有两个有序的数组。我们将这两个数组进行合并。使用一个临时的数组。当这两个数组都没有达到边界时。对对应元素进行比较。叫小的数放进临时数组中。如果相等，则左边的数组先放入。放入一个之后，对应的只增加1。

​ 我们将一个数组划为两部分。然后递归调用这个marge函数，就可以进行归并排序。

​ 根据 master 公式计算，归并排序的master 公式为：

1
2
T(N) = 2*T(N/2) + O(N^1);
log(2，2) = 2;

​ 时间复杂度为==O(N^d * logN)==。

​ 因为归并排序没有浪费比较操作，每一次的比较行为都成为了一个有序的部分。

下面给出代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
#include <vector>
using namespace std;

#pragma once
class MargeSort
{
public:
	static void sort(vector<int>& arr);
	static void progress(vector<int>&, int left, int right);
	static void marge(vector<int>&, int left, int right, int mid);
private:
};
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
#include "MargeSort.h"

void MargeSort::sort(vector<int>& arr)
{
	int length = arr.size();

	if (length < 2) return;

	progress(arr, 0, length - 1);
}

void MargeSort::progress(vector<int>& arr, int left, int right)
{
	if (left == right)
	{
		return;
	}
	int mid = left + ((right - left) >> 1);
	progress(arr, left, mid);
	progress(arr, mid + 1, right);
	marge(arr, left, right, mid);
}

void MargeSort::marge(vector<int>& arr, int left, int right, int mid)
{
	vector<int> help;

	int p1 = left;
	int p2 = mid + 1;

	while (p1 <= mid && p2 <= right)
	{
		help.push_back(arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++]);
	}

	while (p1 <= mid)
	{
		help.push_back(arr[p1++]);
	}

	while (p2 <= right)
	{
		help.push_back(arr[p2++]);
	}

	for (int i = 0; i < right - left + 1; i++)
	{
		arr[i + left] = help[i];
	}

	help.clear();
}

附：C++对数器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#pragma once
#include <iostream>
#include <random>
#include <stdio.h>
#include <stdlib.h> 
#include <windows.h>
using namespace std;

void print_arr(vector<int>& arr, int length);
int random(int min, int max);
void swap(int* a, int* b);
void copy_arr(int* source, int* destination, int length);
void random_arr(vector<int>& arr, int length, int min, int max);
void set_font_color(WORD color);
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
#include "Helper.h"

void print_arr(vector<int>& arr, int length)
{
	cout << " ";
	for (int i = 0; i < length; i++)
	{
		cout << arr[i];
		if (i != length - 1)
			cout << ", ";
	}
	cout << endl;
}

int random(int min = 0, int max = 100) {
	random_device seed;//硬件生成随机数种子
	ranlux48 engine(seed());//利用种子生成随机数引擎
	uniform_int_distribution<> distrib(min, max);//设置随机数范围，并为均匀分布
	return distrib(engine);//随机数
}

void random_arr(vector<int>& arr, int length, int min, int max) {
	for (int i = 0; i < length; i++)
	{
		arr.push_back(random(min, max));
	}
}

void set_font_color(WORD color)
{
	HANDLE handle;//创建句柄 
	handle = GetStdHandle(STD_OUTPUT_HANDLE);//取标准输入输出句柄 
	SetConsoleTextAttribute(handle, color);//字符与 color相同 
}

void swap(int* a, int* b) {
	*a = *a ^ *b;
	*b = *a ^ *b;
	*a = *a ^ *b;
}

void copy_arr(int* source, int* destination, int length) {
	for (int i = 0; i < length; i++)
	{
		destination[i] = source[i];
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
#pragma once
#include <vector>
#include<algorithm>
using namespace std;

class Compare
{
public:
	static void  do_(int number, void(*custom_sort)(vector<int>&), int length, int min, int max);
private:
	static bool do_(void (*custom_sort)(vector<int>&), int length, int min, int max);
	static bool do_(vector<int>& arr1, vector<int>& arr2, int length);
};
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
61
62
63
64
65
66
67
#include "Compare.h"
#include "Helper.h"

void Compare::do_(int number, void(*custom_sort)(vector<int>&), int length, int min, int max)
{
	if (number == 0) return;

	for (int i = 0; i < number; i++)
	{
		do_(custom_sort, length, min, max);
	}
}

bool Compare::do_(void(*custom_sort)(vector<int>&), int length, int min, int max)
{
	vector<int> arr;
	random_arr(arr, length, min, max);

	vector<int>  arr1;
	arr1.assign(arr.begin(), arr.end());

	vector<int>  arr2;
	arr2.assign(arr.begin(), arr.end());

	sort(arr1.begin(), arr1.end());
	custom_sort(arr2);

	if (!do_(arr1, arr2, length))
	{
		set_font_color(FOREGROUND_RED);
		cout << "Wrong Sample: ";
		print_arr(arr, length);
		cout << "Wrong Sample Sort:";
		print_arr(arr2, length);
		cout << endl;
		return false;
	}
	else
	{
		set_font_color(FOREGROUND_GREEN);
		cout << "Right Sample: ";
		print_arr(arr, length);
		cout << "Right Sample Sort: ";
		print_arr(arr2, length);
		cout << endl;
	};

	set_font_color(0x07);
	return true;
}

bool Compare::do_(vector<int>& arr1, vector<int>& arr2, int length)
{
	bool right = true;
	for (int i = 0; i < length; i++)
	{
		if (arr1[i] == arr2[i])
		{

		}
		else
		{
			right = false;
		};
	}
	return right;
}