Coding►Algorithm►Sort

《算法导论》第一部分 C++综合实现

1.将第二章和第五章正文和部分习题讲到的算法用C++实现并整理到一个程序中，不同算法使用不同函数即可。 2.程序功能：输入任意个整数的序列，生成一个均匀随机排列。
3.使用vector作数据容器。

随机排列数组

第二章 算法入门
2.1 插入排序 -> insertSort()
2.3 分治法 -> mergeSortByPri()
习题 2.3-2 分治法中哨兵的使用
算法一：使用哨兵 -> mergeWithSentry()
算法二：不使用哨兵 -> mergeNoSentry()
第五章 概率分析和随机算法
5.3 随机排列数组（详见main()）
1.) 优先级排序 PERMUTE-BY-SORTING + 习题 5.3-6 两个或更多优先级相同的情况
2.) 原地排序 RANDOMIZE-IN-PLACE

C++ random(a, b)的方法：（random(0, 1)简化即可）

1
2
3
#include <time.h>
srand((unsigned int)time(0)); // 用时间设置随机数种子
rand() % (b - a) + a; // 生成[a, b]内的随机整数

第一轮随机数由时间做种，第二轮由第一轮时间做种，以此类推

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
#include "stdafx.h"
#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <vector>
using namespace std;
int creatRandomNum(int a, int b)
{
    return rand() % (b - a) + a;
}
void swapTwoNum(vector<int> &ivec, int a, int b)
{
trueint temp = ivec[a];
trueivec[a] = ivec[b];
trueivec[b] = temp;
}
// 使用哨兵
void mergeWithSentry(vector<int> &numBox, vector<int> &priBox, int begin, int middle, int end)
{
trueint n1 = middle - begin + 1;
trueint n2 = end - middle;
truevector<int> priL, priR, numL, numR;
truefor (int i = 0; i < n1; i++) {
truetruepriL.push_back(priBox[begin + i]);
        numL.push_back(numBox[begin + i]);
true}
truefor (int j = 0; j < n2; j++) {
truetruepriR.push_back(priBox[middle + j + 1]);
truetruenumR.push_back(numBox[middle + j + 1]);
true}
truepriL.push_back(INT_MAX);
truepriR.push_back(INT_MAX);
truefor (int i = 0, j = 0, k = begin; k <= end; k++) {
truetrueif (priL[i] <= priR[j]) {
truetruetruepriBox[k] = priL[i];
truetruetruenumBox[k] = numL[i++];
truetrue} else {
truetruetruepriBox[k] = priR[j];
truetruetruenumBox[k] = numR[j++];
truetrue}
true}
}
// 不使用哨兵
void mergeNoSentry(vector<int> &numBox, vector<int> &priBox, int begin, int middle, int end)
{
trueint n1 = middle - begin + 1;
trueint n2 = end - middle;
truevector<int> priL, priR, numL, numR;
truefor (int i = 0; i < n1; i++) {
truetruepriL.push_back(priBox[begin + i]);
truetruenumL.push_back(numBox[begin + i]);
true}
truefor (int j = 0; j < n2; j++) {
truetruepriR.push_back(priBox[middle + j + 1]);
truetruenumR.push_back(numBox[middle + j + 1]);
true}
truefor (unsigned int i = 0, j = 0, k = begin; k <= (unsigned)end; k++) {
truetrue// 先判断是否有排完的情况，否者会造成vector的subscript越界
truetrueif (j == priR.size() && i < priL.size()) { // 左边未完右边已完
truetruetruepriBox[k] = priL[i];
truetruetruenumBox[k] = numL[i++];
truetrue} else if (i == priL.size() && j < priR.size()) { // 右边未完左边已完
truetruetruepriBox[k] = priR[j];
truetruetruenumBox[k] = numR[j++];
truetrue} else if (priL[i] < priR[j]) { // 两边都未完，直接比大小
truetruetruepriBox[k] = priL[i];
truetruetruenumBox[k] = numL[i++];
truetrue} else if (priR[j] < priL[i]) {
truetruetruepriBox[k] = priR[j];
truetruetruenumBox[k] = numR[j++];
truetrue}
true}
}
void mergeSortByPri(vector<int> &numBox, vector<int> &priBox, int begin, int end)
{
trueif (begin < end) {
truetrueint middle = (begin + end) / 2;
truetruemergeSortByPri(numBox, priBox, begin, middle);
truetruemergeSortByPri(numBox, priBox, middle + 1, end);
truetrue// have哨兵
truetruemergeWithSentry(numBox, priBox, begin, middle, end);
truetrue// no哨兵
truetrue// mergeNoSentry(numBox, priBox, begin, middle, end);
true}
}
void insertSort(vector<int> &numBox, vector<int> &priBox)
{
truevector<int>::size_type length = priBox.size();
trueint priKey, numKey;
truefor (unsigned int i, j = 1; j < length; j++) {
truetruepriKey = priBox[j];
truetruenumKey = numBox[j];
truetrue// insert a[j] into the sorted sequence a[1..j-1]
truetruei = j - 1;
truetrue// 线性查找
truetruewhile (i >= 0 && priBox[i] > priKey) {
truetruetruepriBox[i + 1] = priBox[i];
truetruetruenumBox[i + 1] = numBox[i];
truetruetruei--;
truetrue}
truetruepriBox[i + 1] = priKey;
truetruenumBox[i + 1] = numKey;
true}
}
int main()
{
truesrand((unsigned int)time(0));
truevector<int> numBox, priBox;
trueint num;
truewhile (cin >> num)
truetruenumBox.push_back(num);
true/*
true    随机排列数组 算法一：优先级排序 (permute-by-sorting)
true    为每个元素 numBox[i] 赋一个随机的优先级 priBox[i]，然后根据优先级对数组中的元素进行排序
true*/
truevector<int>::size_type length = numBox.size();
truefor (unsigned int i = 0; i < length; i++) { //
truetruenum = creatRandomNum(1, length * length * length);
truetrueint flag = 1;
truetruewhile (flag)
truetruetruefor (vector<int>::iterator iter = numBox.begin(); iter != numBox.end();iter++)
truetruetruetrueif (*iter == num) {
truetruetruetruetruenum = creatRandomNum(1, length * length * length);
truetruetruetruetruebreak;
truetruetruetrue} else if (iter + 1 == numBox.end()) {
truetruetruetruetrueflag = 0;
truetruetruetruetruebreak;
truetruetruetrue}
truetruepriBox.push_back(num);
true}
true/*
true    排序算法一：分治递归法 (merge-sort)
true    时间复杂度：Θ(nlgn)
true*/
truemergeSortByPri(numBox, priBox, 0, length - 1);
true/*
true    排序算法二：线性查找插入排序 (insertion-sort)
true    时间复杂度：Θ(n^2)
true*/
true//	insertSort(numBox, priBox);
true/*
true    随机排列数组 算法二：原地排列 (randomize-in-place)
true    在第i次迭代时，元素 numBox[i] 是从元素 numBox[i] 到 numBox[length - 1] 中随机选取的
true    时间复杂度：O(n)
true*/
true/*for (int i = 0;i < length - 1; i++)
truetrueswapTwoNum(numBox, i, creatRandomNum(i, length - 1));*/
    for (vector<int>::iterator iter = numBox.begin(); iter != numBox.end(); ++iter)
truetruecout << *iter << " ";
truecout << endl;
truesystem("pause");
truereturn 0;
}

END.