我们从最基础的排序算法开始介绍，首先是众所周知的选择排序，该算法的时间复杂度为O(n^2)。直接给出其代码：
void selectSort(int* a, int n) {
for(int i = 0; i < n-1; i++) {
int temp = i;
for(int j = i+1; j < n; j++) {
if(a[j] < a[temp]) {
temp = j;
}
}
swap(a[i], a[temp]);
}
}
然后，我们硬编码一个简单的测试代码进行测试，测试程序如下：
int main() {
int a[10] = {3,4,2,5,4,8,4,9,2,1};
selectSort(a, 10);
for(int i = 0; i < 10; i++) {
cout<<a[i]<<" "; //1 2 2 3 4 4 4 5 8 9
}
return 0;
}
结果当然是我们所预期的，但是，这种硬编码的测试也太low了吧，简直不能忍受。所以，我们再来写一个生成随机测试用例的代码：
int* generateRandomArray(int n, int rangeL, int rangeR) {
assert(rangeL <= rangeR);
int *arr = new int[n];
srand(time(NULL));//头文件ctime
for(int i = 0; i < n; i++) {
arr[i] = rand() % (rangeR - rangeL + 1) + rangeL;
}
return arr;
}
然后，我们使用这个函数替换测试程序中硬编码出来的函数，如下：
int main() {
int n = 100;
int* a = sSort::generateRandomArray(n, 0, n);
selectSort(a, n);
for(int i = 0; i < n; i++) {
cout<<a[i]<<" ";
}
cout<<endl;
delete[] a;
return 0;
}
这里，由于我把generateRandomArray函数写到了sSort命名空间下，所以函数调用的时候使用了::运算符；另外，由于这里的a数组是动态分配的，所以程序结束的时候不要忘记delete掉这块空间。
我们后面的学习中可能会多次用到这种打印一个数组中的元素的操作，所以，我们把这个打印操作包装成一个模板函数，如下：
template<typename T>
void printArray(T a[], int n) {
for(int i = 0; i < n; i++) {
cout<<a[i]<<" ";
}
cout<<endl;
}
然后在测试程序中直接调用这个函数即可，调用过程不再介绍。
既然打印数组的函数我们可以写成模板函数，当然排序函数我们最好也写成模板函数，这样，我们就可以对不同类型的数组进行排序啦，修改也很简单，内部的代码不用动，只修改参数列表即可：
template<typename T>
void selectSort(T a[], int n) {...}
到这里，我们的算法写好了，可是，我们怎么知道这个算法运行的快不块呢？这也简单，我们再来写一个统计算法执行时间的函数就好了：
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;
}
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));//确认已经完成了排序，头文件cassert
cout << sortName << " : " << double(endTime - startTime) / CLOCKS_PER_SEC << "s" <<endl;
}
下面我们就可以用这个函数测试一下排序算法的执行时间啦。调用方法：
sSort::testSort("selectSort", selectSort, a, n);
本来还想详细测试一下不同数据量下的执行时间曲线呢，结果数据量为10万的时候跑的时间还算可以，13.518s，当我把数据量改到100万之后，跑的实在是太慢了，等了半天还没有结果，这也从侧面说明了O(n^2)级别的算法在数据量比较大的时候的性能比较差。
下面给出简单的执行时间变化曲线：
不同数据量下选择排序的执行时间
