6.插入排序(改进版) 6.插入排序(改进版)

//插入排序法（改进版） template void insertionSort(T arr[], int n){ for(int i = 1; i < n; i++){ //寻找元素arr[i]合适的插入位置 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; } }

图片演示:

文章图片
【6.插入排序(改进版)】测试程序：

#include #include #include "temp.h" #include "SelectionSort.h" using namespace std; template 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; } }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; }

temp.h: #ifndef _TEMP_H #define _TEMP_H #include #include #include #include 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 void PrintArray(T arr[], int n){ for( int i = 0; i < n; i++) cout << arr[i] << " "; cout << endl; return; } template 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 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

SelectionSort.h: #ifndef _SELECTIONSORT_H #define _SELECTIONSORT_H #include #include using namespace std; template 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