@TOC
排序——内部排序之交换排序
内部排序
排序的一篇优秀博客
- 插入排序
- 折半插入排序
- 希尔排序（不稳定）
冒泡排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18void BubbleSort(ElemType A[], int n) {
int temp = 0;
// 标记数组是不是有序的；
bool flag = false;
for (int i = 0; i < n - 1; i++) {
flag = false;
for (int j = n - 1; j > i; j--) {
if(A[j - 1].key > A[j].key) {
temp = A[j - 1].key;
A[j - 1].key = A[j].key;
A[j].key = temp;
flag = true;
}
}
if(flag == false)
return;
}
}快速排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20void QuickSort(ElemType A[], int low, int high) {
if (low < high) {
int mid = Partion(A, low, high);
QuickSort(A, low, mid - 1);
QuickSort(A, mid + 1, high);
}
}
int Partion(ElemType A[], int low, int high) {
ElemType privot = A[low];
// 将数组的第一个元素设置成枢纽值，对数组进行划分
while(low < high) {
while(low < high && A[high] >= privot) --high;
A[low] = A[high];
while(low < high && A[low] <= privot) ++low;
A[high] = A[low];
}
A[low] = privot;
return low;
}
算法练习
线性表按顺序存储，使用最少的时间和空间将所有奇数移动到偶数的前面
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15void OddEvenEx(ElemType A[], int n) {
int i = 0;
int j = n - 1;
while(i < j) {
while(i < j && A[j] % 2 != 1) --j;
// 从后向前寻找第一个奇数
while(i < j && A[i] % 2 != 0) ++i;
// 从前向后寻找第一个偶数
if (i < j) {
Swap(A[i], A[j]);
++i;
--j;
}
}
}试在数组A[1…n]中寻找第k小的数。
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
32ElemType KthLeast(ElemType A[], int k, int low, int high) {
ElemType privot = A[low];
int low_temp = low;
int high_temp = high;
while(low < high) {
while(low < high && A[high] >= privot) --high;
A[low] = A[high];
while(low < high && A[low] <= privot) ++low;
A[high] = A[low];
}
A[low] = privot;
/*这里使用递归的方式来实现
if (low == k) {
return A[low];
} else if (low < k) {
low = low + 1;
high = n - 1;
} else {
high = low - 1;
low = 0;
} */
//这里的k如果数组下表是从0开始的话，最开始的时候k需要减1
if (low == k) {
return A[low];
} else if (low < k) {
// 在后一部分继续寻找
return KthLeast(A, k, low + 1, high_temp);
} else {
// 在前一部分继续寻找
return KthLeast(A, k, low_temp, low - 1);
}
}2016年计算机联考真题
已知由n（n>=2）个正整数构成的集合A ，将其划分成两个不相交的子集A1和A2，元素个数分别为n1和n2，A1和A2中元素之和分别为S1和S2。设计一个尽可能高效的划分算法，满足|n1-n2|最小且|S1-S2|最大。要求：
1）给出算法的基本设计思想。
2）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
3）说明你所设计算法的平均时间复杂度和空间复杂度。算法解析：这道题目是求第k大的数的一个变种.
|n1-n2|最小且|S1-S2|最大，在数组元素为奇数个的时候，|n1-n2|最小为1，那么把前n/2个最小的数放在一个数组，后面n/2+1个比较大的数放在另一个数组，这时得到的结果满足条件；数组元素为偶数个的时候，|n1-n2|最小为0，所以，第一个数组里面的数是比较小的前n/2个数，第二个数组的是后n/2个比较大的数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20void ArrPartion(ElemType A[], int low, int high, int k) {
ElemType privot = A[low];
int low_temp = low;
int high_temp = high;
while(low < high) {
while(low < high && A[high] > privot) --high;
A[low] = A[high];
while(low < high && A[low] < privot) ++low;
A[high] = A[low];
}
A[low] = privot;
if (low == k) {
return;
} else if (low < k) {
ArrPartion(A, low_temp, low - 1, k);
} else {
ArrPartion(A, low + 1, high_temp, k);
}
}荷兰国旗难题
现在有若干个红、白、蓝三种颜色的球随机排列成一条直线。现在我们的任务是把这些球按照红、白、蓝排序。
算法思想：对线性表从前往后进行扫描，将红色的条块放到前面，蓝色对的条块放到后面，白色的条块自然也就在中间的位置，故而需要三个指针，begin和end分别指向数组的头部和尾部，current指针从前往后扫描，如果遇到红色就和头部进行交换，如果遇到蓝色则和尾部交换。
算法实现如下所示：
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
using namespace std;
typedef enum{RED, WHITE, BLUE} color;
void Holland_Partion(color arr[], int n) {
int begin = 0;
int end = n - 1;
int current = begin;
color temp;
while(current <= end) {
switch(arr[current]){
case RED:
temp = arr[begin];
arr[begin] = arr[current];
arr[current] = temp;
begin++;
current++;
break;
case WHITE:
current++;
break;
case BLUE:
temp = arr[end];
arr[end] = arr[current];
arr[current] = temp;
end--;
// current没有++，因为担心交换后current指向的仍为BLUE
}
}
}
int main() {
color arr[12];
for(int i = 0; i < 12; i+=3) {
arr[i] = WHITE;
arr[i + 1] = BLUE;
arr[i + 2] = RED;
}
for(int i = 0; i < 12; i++) {
cout << arr[i] << " ";
}
cout << endl;
Holland_Partion(arr, 12);
for(int i = 0; i < 12; i++) {
cout << arr[i] << " ";
}
return 0;
}