//从第2个元素遍历到最后一个元素，在每一次迭代中，要将arr[i]放到前面合适的位置
//每一次迭代完成后，要保证[0, i]这个区间内的元素有序.
template<typename T>
void insertionSort(T arr[], int n){
for(int i = 1; i < n; i++){
//寻找元素arr[i]合适的插入位置
//写法1
/*
for(int j = i; j > 0; j--){
if(arr[j] < arr[j-1])
swap(arr[j], arr[j-1]);
else
break;
}
*/
//写法2
for(int j = i; j > 0 && arr[j] < arr[j-1]; j--)
swap( arr[j], arr[j-1]);
}
}
测试：
main.cpp:
#include <iostream>
#include <algorithm>
#include "temp.h"
#include "SelectionSort.h"
using namespace std;
template<typename T>
void insertionSort(T arr[], int n){
for(int i = 1; i < n; i++){
//寻找元素arr[i]合适的插入位置
//写法1
/*
for(int j = i; j > 0; j--){
if(arr[j] < arr[j-1])
swap(arr[j], arr[j-1]);
else
break;
}
*/
//写法2
for(int j = i; j > 0 && arr[j] < arr[j-1]; j--)
swap( arr[j], arr[j-1]);
}
}
int main()
{
int n = 10000;
cout << "Test for Random Array ,size = " << n << ", random range [0, " << n << "]" << endl;
int *arr1 = SortTestHelper::generateRandomArray(n,0,n);
int *arr2 = SortTestHelper::copyIntArray(arr1, n);
SortTestHelper::testSort("Insertion Sort", insertionSort, arr1, n);
SortTestHelper::testSort("Selection Sort", selectionSort, arr2, n);
delete[]arr1;
delete[]arr2;
cout << endl;
return 0;
}
SelectionSort.h:
#ifndef _SELECTIONSORT_H
#define _SELECTIONSORT_H
#include<iostream>
#include<algorithm>
using namespace std;
template<typename T>
void selectionSort(T arr[], int n)
{
for(int i = 0; i < n-1; i++){
int minIndex = i;
for(int j = i + 1; j < n; j++)
if(arr[j] < arr[minIndex])
minIndex = j;
swap(arr[i], arr[minIndex]);
}
}
#endif
temp.h:
#ifndef _TEMP_H
#define _TEMP_H
#include <iostream>
#include <ctime>
#include <cassert>
#include <algorithm>
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;
}
int *generateNearlyOrderedArray(int n, int swapTimes){
int *arr = new int [n];
for(int i = 0; i < n; i++)
arr[i] = i;
srand(time(NULL));
for( int i = 0; i < swapTimes; i++ ){
int posx = rand()%n;
int posy = rand()%n;
swap( arr[posx], arr[posy]);
}
return arr;
}
int* copyIntArray(int a[], int n){
int *arr = new int [n];
copy(a, a + n, arr);
return arr;
}
template<typename T>
void PrintArray(T arr[], int n){
for( int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
return;
}
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;
}
/*
* endTime - startTime返回的是运行了几个时钟周期
* CLOCK_PER_SEC是标准库中定义的宏，表示每秒钟运行的时钟周期的个数
*/
template<typename T>
void testSort(const 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;
}
};
#endif
小结：
这个未改进的插入排序和之前的选择排序相比，内层循环可以提前退出，理论上应该比选择排序要高校(因为选择排序内存的循环不能提前退出),但实际上，对于一个很随机的数组(这个随机是相对于有序性的，即有序性很差)，我们测试得到的结果是选择排序更高效。
这是因为在这个版本的插入排序中，在遍历的同时也在不停地交换，交换是比简单的比较操作还要耗时的，因为每次交换背后都有三次赋值的操作，对于数组来说还有访问索引相应位置的元素的时间。
下一篇将改进插入排序算法，使其在内层循环中只交换一次。
