排序算法
O(n2)的排序算法
为什么要学习O(n2)的排序算法?
- 基础
- 编码简单，易于实现，是一些简单场景的首选
- 在一些特殊情况下，简单的排序算法更有效
- 简单的排序算法思想衍生出复杂的排序算法
- 作为子过程，改进更复杂的排序算法
选择排序（Selection Sort）
算法思想：每一趟（例如第i趟）在后面n-i+1（i=1，2，3，···，n-1）个待排序元素中选取关键字最小的元素，作为有序子序列的第i个元素，直到第n-1趟做完，待排序元素只剩下1个，就不用再选了。
算法动画演示：
选择排序
基本算法如下：
#include <iostream>
using namespace std;
void selectionSort(T arr[], int n) {
for (int i = 0; i < n - 1; i++) {
// 寻找[i, n)区间里的最小值
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex])
minIndex = j;
}
if (minIndex != i)
swap(arr[i], arr[minIndex]);
}
}
int main(void) {
int a[10] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
selectionSort(a, 10);
for (int i = 0; i < 10; i++)
cout << a[i] << " ";
cout << endl;
return 0;
}
其运行结果为：
1 2 3 4 5 6 7 8 9 10
但上述算法存在一些问题，如果我们想要对浮点数、字符串等进行排序，上述代码就不能满足我们的需求，那我们要如何做才能解决这个问题呢？熟悉C++语言或者Java语言的同学就会知道，可以使用C++中的模板或者使用Java中的泛型来解决此问题。此处，我们以C++语言为例，代码如下：
#include <iostream>
using namespace std;
template<typename T>
void selectionSort(T arr[], int n) {
for (int i = 0; i < n - 1; i++) {
// 寻找[i, n)区间里的最小值
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex])
minIndex = j;
}
if (minIndex != i)
swap(arr[i], arr[minIndex]);
}
}
int main(void) {
int a[10] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
float b[10] = {10, 9.6, 8, 7.9, 6.3, 5, 4.1, 3, 2, 1.6};
string c[4] = {"D", "A", "C", "B"};
selectionSort(a, 10);
for (int i = 0; i < 10; i++)
cout << a[i] << " ";
cout << endl;
selectionSort(b, 10);
for (int i = 0; i < 10; i++)
cout << b[i] << " ";
cout << endl;
selectionSort(c, 4);
for (int i = 0; i < 4; i++)
cout << c[i] << " ";
cout << endl;
return 0;
}
其运行结果为：
1 2 3 4 5 6 7 8 9 10
1.6 2 3 4.1 5 6.3 7.9 8 9.6 10
A B C D
如果我们要按结构体变量中的某个成员从小到大排序，那代码如何实现？这里，我们先创建Student.h这个头文件，代码如下：
#ifndef SELECTIONSORT_STUDENT_H
#define SELECTIONSORT_STUDENT_H
#include <iostream>
using namespace std;
struct Student {
string name;
int score;
// 重载<
bool operator<(const Student &otherStudent) {
return score != otherStudent.score ? score < otherStudent.score : name < otherStudent.name;
}
// 重载<<
friend ostream &operator<<(ostream &os, const Student &student) {
os << "Student: " << student.name << " " << student.score << endl;
return os;
}
};
#endif //SELECTIONSORT_STUDENT_H
然后我们将之前的代码修改如下即可：
#include <iostream>
#include "Student.h"
using namespace std;
template<typename T>
void selectionSort(T arr[], int n) {
for (int i = 0; i < n - 1; i++) {
// 寻找[i, n)区间里的最小值
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex])
minIndex = j;
}
if (minIndex != i)
swap(arr[i], arr[minIndex]);
}
}
int main(void) {
Student d[4] = {
{"D", 90},
{"A", 100},
{"C", 78},
{"B", 89}
};
selectionSort(d, 4);
for (int i = 0; i < 4; i++)
cout << d[i];
cout << endl;
return 0;
}
其运行结果为：
Student: C 78
Student: B 89
Student: D 90
Student: A 100
虽然，我们完善了我们的程序，使我们的程序可以对int、float和string等类型排序，但纵观我们的程序，始终有个小问题，就是我们的测试用例不是很智能。因此，我们创建SortTestHelper.h文件，其代码如下：
#ifndef SELECTIONSORT_SORTTESTHELPER_H
#define SELECTIONSORT_SORTTESTHELPER_H
#include <iostream>
#include <ctime>
#include <cassert>
using namespace std;
namespace SortTestHelper {
// 生成有n个元素的随机数组，每个元素的随机范围为[rangeL, rangeR]
int *generateRandomArray(int n, int rangeL, int rangeR) {
assert(rangeL <= rangeR);
int *arr = new int[n];
srand(time(NULL));
for (int i = 0; i < n; i++)
// 控制随机数的取值范围
arr[i] = rand() % (rangeR - rangeL + 1) + rangeL;
return arr;
}
}
#endif //SELECTIONSORT_SORTTESTHELPER_H
好了，我们回到main函数中，调用我们刚刚创建的generateRandomArray()，代码如下：
#include <iostream>
#include "Student.h"
#include "SortTesthelper.h"
using namespace std;
template<typename T>
void selectionSort(T arr[], int n) {
for (int i = 0; i < n - 1; i++) {
// 寻找[i, n)区间里的最小值
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex])
minIndex = j;
}
if (minIndex != i)
swap(arr[i], arr[minIndex]);
}
}
int main(void) {
int n = 10000;
int *arr = SortTestHelper::generateRandomArray(n, 0, n);
selectionSort(arr, n);
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
delete[] arr;
return 0;
}
我们又进一步完善了我们的程序，让我们在想想看还有没有地方我们可以继续优化呢？不知道大家有没有注意到结果打印代码，这几行代码我们已经重复了好几遍了！因此，我们可以对结果打印代码进行优化，我们在SortTestHelper.h文件中添加如下代码：
template<typename T>
void printArray(T arr[], int n) {
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
}
我们在main函数中只要添加如下代码就可调用printArray()了：
SortTestHelper::printArray(arr, n);
为了使我们的程序更加完善，我们继续在SortTestHelper.h文件中添加验证排序算法执行是否正确的函数isSorted()，其代码如下：
// 验证排序算法是否执行正确
template<typename T>
bool isSorted(T arr[], int n) {
for (int i = 0; i < n - 1; i++)
if (arr[i] > arr[i + 1])
return false;
return true;
}
除此之外，我们在SortTestHelper.h文件中添加testSort()来测试我们排序算法的性能，其代码如下：
// 测试排序算法的性能
template<typename T>
void testSort(string sortName, void(*sort)(T[], int), T arr[], int n) {
clock_t startTime = clock();
sort(arr, n);
clock_t endTime = clock();
assert(isSorted(arr, n));
cout << sortName << " : " << double(endTime - startTime) / CLOCKS_PER_SEC << " s" << endl;
return;
}
好了，我们在main()调用我们刚刚添加的方法吧，代码如下：
SortTestHelper::testSort("Selection Sort", selectionSort, arr, n);
