InsertionSort.h
#ifndef INC_02_MERGE_SORT_INSERTIONSORT_H
#define INC_02_MERGE_SORT_INSERTIONSORT_H
#include <iostream>
#include <algorithm>
using namespace std;
template<typename T>
void insertionSort(T arr[], int n){
for( int i = 1 ; i < n ; i ++ ) {
T e = arr[i];
int j;
for (j = i; j > 0 && arr[j-1] > e; j--)
arr[j] = arr[j-1];
arr[j] = e;
}
return;
}
// 对arr[l...r]范围的数组进行插入排序
template<typename T>
void insertionSort(T arr[], int l, int r){
for( int i = l+1 ; i <= r ; i ++ ) {
T e = arr[i];
int j;
for (j = i; j > l && arr[j-1] > e; j--)
arr[j] = arr[j-1];
arr[j] = e;
}
return;
}
#endif //INC_02_MERGE_SORT_INSERTIONSORT_H
SortTestHelper.h
#ifndef INC_02_MERGE_SORT_SORTTESTHELPER_H
#define INC_02_MERGE_SORT_SORTTESTHELPER_H
#include <iostream>
#include <algorithm>
#include <string>
#include <ctime>
#include <cassert>
using namespace std;
namespace SortTestHelper {
int *generateRandomArray(int n, int range_l, int range_r) {
int *arr = new int[n];
srand(time(NULL));
for (int i = 0; i < n; i++)
arr[i] = rand() % (range_r - range_l + 1) + range_l;
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;
}
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();
cout << sortName << " : " << double(endTime - startTime) / CLOCKS_PER_SEC << " s"<<endl;
assert(isSorted(arr, n));
return;
}
};
#endif //INC_02_MERGE_SORT_SORTTESTHELPER_H
main.app
#include <iostream>
#include "SortTestHelper.h"
#include "InsertionSort.h"
using namespace std;
// 将arr[l...mid]和arr[mid+1...r]两部分进行归并
template<typename T>
void __merge(T arr[], int l, int mid, int r){
// 经测试,传递aux数组的性能效果并不好
T aux[r-l+1];
for( int i = l ; i <= r; i ++ )
aux[i-l] = arr[i];
int i = l, j = mid+1;
for( int k = l ; k <= r; k ++ ){
if( i > mid ) { arr[k] = aux[j-l]; j ++;}
else if( j > r ){ arr[k] = aux[i-l]; i ++;}
else if( aux[i-l] < aux[j-l] ){ arr[k] = aux[i-l]; i ++;}
else { arr[k] = aux[j-l]; j ++;}
}
}
// 递归使用归并排序,对arr[l...r]的范围进行排序
template<typename T>
void __mergeSort(T arr[], int l, int r){
if( l >= r )
return;
int mid = (l+r)/2;
__mergeSort(arr, l, mid);
__mergeSort(arr, mid+1, r);
__merge(arr, l, mid, r);
}
template<typename T>
void mergeSort(T arr[], int n){
__mergeSort( arr , 0 , n-1 );
}
int main() {
int n = 50000;
// 测试1 一般性测试
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("Merge Sort", mergeSort, arr2, n);
delete[] arr1;
delete[] arr2;
cout<<endl;
// 测试2 测试近乎有序的数组
int swapTimes = 100;
cout<<"Test for Random Nearly Ordered Array, size = "<<n<<", swap time = "<<swapTimes<<endl;
arr1 = SortTestHelper::generateNearlyOrderedArray(n,swapTimes);
arr2 = SortTestHelper::copyIntArray(arr1, n);
SortTestHelper::testSort("Insertion Sort", insertionSort, arr1, n);
SortTestHelper::testSort("Merge Sort", mergeSort, arr2, n);
delete(arr1);
delete(arr2);
return 0;
}