插入算法：
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] ); // 写法3 T e = arr[i]; int j; // j保存元素e应该插入的位置 for (j = i; j > 0 && arr[j-1] > e; j--) arr[j] = arr[j-1]; arr[j] = e; } return; }
复制数组：
int *copyIntArray(int a[], int n){ int *arr = new int[n]; copy(a, a+n, arr); 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 main() { int n = 10000; // 测试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("Selection Sort", selectionSort,arr2,n); delete[] arr1; delete[] arr2; cout<<endl; // 测试2 有序性更强的测试 cout<<"Test for More Ordered Random Array, size = "<<n<<", random range [0, 3]"<<endl; arr1 = SortTestHelper::generateRandomArray(n,0,3); 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; // 测试3 测试近乎有序的数组 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("Selection Sort", selectionSort,arr2,n); delete(arr1); delete(arr2); return 0; }
转载于:https://www.cnblogs.com/lzb0803/p/9044078.html
