排序算法
O(n2)的排序算法
為什么要學(xué)習(xí)O(n2)的排序算法?
- 基礎(chǔ)
- 編碼簡(jiǎn)單，易于實(shí)現(xiàn)，是一些簡(jiǎn)單場(chǎng)景的首選
- 在一些特殊情況下，簡(jiǎn)單的排序算法更有效
- 簡(jiǎn)單的排序算法思想衍生出復(fù)雜的排序算法
- 作為子過(guò)程，改進(jìn)更復(fù)雜的排序算法
選擇排序（Selection Sort）
算法思想：每一趟（例如第i趟）在后面n-i+1（i=1，2，3，···，n-1）個(gè)待排序元素中選取關(guān)鍵字最小的元素，作為有序子序列的第i個(gè)元素，直到第n-1趟做完，待排序元素只剩下1個(gè)，就不用再選了。
算法動(dòng)畫(huà)演示：
基本算法如下：
#include <iostream>
using namespace std;
void selectionSort(T arr[], int n) {
for (int i = 0; i < n - 1; i++) {
// 尋找[i, n)區(qū)間里的最小值
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;
}
其運(yùn)行結(jié)果為：
1 2 3 4 5 6 7 8 9 10
但上述算法存在一些問(wèn)題，如果我們想要對(duì)浮點(diǎn)數(shù)、字符串等進(jìn)行排序，上述代碼就不能滿足我們的需求，那我們要如何做才能解決這個(gè)問(wèn)題呢？熟悉C++語(yǔ)言或者Java語(yǔ)言的同學(xué)就會(huì)知道，可以使用C++中的模板或者使用Java中的泛型來(lái)解決此問(wèn)題。此處，我們以C++語(yǔ)言為例，代碼如下：
#include <iostream>
using namespace std;
template<typename T>
void selectionSort(T arr[], int n) {
for (int i = 0; i < n - 1; i++) {
// 尋找[i, n)區(qū)間里的最小值
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;
}
其運(yùn)行結(jié)果為：
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
如果我們要按結(jié)構(gòu)體變量中的某個(gè)成員從小到大排序，那代碼如何實(shí)現(xiàn)？這里，我們先創(chuàng)建Student.h這個(gè)頭文件，代碼如下：
#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)區(qū)間里的最小值
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;
}
其運(yùn)行結(jié)果為：
Student: C 78
Student: B 89
Student: D 90
Student: A 100
雖然，我們完善了我們的程序，使我們的程序可以對(duì)int、float和string等類型排序，但縱觀我們的程序，始終有個(gè)小問(wèn)題，就是我們的測(cè)試用例不是很智能。因此，我們創(chuàng)建SortTestHelper.h文件，其代碼如下：
#ifndef SELECTIONSORT_SORTTESTHELPER_H
#define SELECTIONSORT_SORTTESTHELPER_H
#include <iostream>
#include <ctime>
#include <cassert>
using namespace std;
namespace SortTestHelper {
// 生成有n個(gè)元素的隨機(jī)數(shù)組，每個(gè)元素的隨機(jī)范圍為[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++)
// 控制隨機(jī)數(shù)的取值范圍
arr[i] = rand() % (rangeR - rangeL + 1) + rangeL;
return arr;
}
}
#endif //SELECTIONSORT_SORTTESTHELPER_H
好了，我們回到main函數(shù)中，調(diào)用我們剛剛創(chuàng)建的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)區(qū)間里的最小值
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;
}
我們又進(jìn)一步完善了我們的程序，讓我們?cè)谙胂肟催€有沒(méi)有地方我們可以繼續(xù)優(yōu)化呢？不知道大家有沒(méi)有注意到結(jié)果打印代碼，這幾行代碼我們已經(jīng)重復(fù)了好幾遍了！因此，我們可以對(duì)結(jié)果打印代碼進(jìn)行優(yōu)化，我們?cè)赟ortTestHelper.h文件中添加如下代碼：
template<typename T>
void printArray(T arr[], int n) {
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
}
我們?cè)趍ain函數(shù)中只要添加如下代碼就可調(diào)用printArray()了：
SortTestHelper::printArray(arr, n);
為了使我們的程序更加完善，我們繼續(xù)在SortTestHelper.h文件中添加驗(yàn)證排序算法執(zhí)行是否正確的函數(shù)isSorted()，其代碼如下：
// 驗(yàn)證排序算法是否執(zhí)行正確
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;
}
除此之外，我們?cè)赟ortTestHelper.h文件中添加testSort()來(lái)測(cè)試我們排序算法的性能，其代碼如下：
// 測(cè)試排序算法的性能
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;
}
好了，我們?cè)趍ain()調(diào)用我們剛剛添加的方法吧，代碼如下：
SortTestHelper::testSort("Selection Sort", selectionSort, arr, n);
