备注：这里使用的插入排序和选择排序都是经过优化后的详细优化请查看上一条博客，编译器使用DEV-C++
冒泡排序算法的运作如下：（从后往前）
1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3.针对所有的元素重复以上的步骤，除了最后一个。
4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较
测试代码：
1 #ifndef OPTIONAL_01_BUBBLE_SORT_SORTTESTHELPER_H 2 #define OPTIONAL_01_BUBBLE_SORT_SORTTESTHELPER_H 3 #include4 #include 5 #include 6 #include 7 #include 8 using namespace std; 9 namespace SortTestHelper {10 // 生成有n个元素的随机数组,每个元素的随机范围为[rangeL, rangeR]11 int *generateRandomArray(int n, int range_l, int range_r) {12 int *arr = new int[n];13 srand(time(NULL));14 for (int i = 0; i < n; i++)15 arr[i] = rand() % (range_r - range_l + 1) + range_l;16 return arr;17 }18 // 生成一个近乎有序的数组19 // 首先生成一个含有[0...n-1]的完全有序数组, 之后随机交换swapTimes对数据20 // swapTimes定义了数组的无序程度21 int *generateNearlyOrderedArray(int n, int swapTimes){22 int *arr = new int[n];23 for(int i = 0 ; i < n ; i ++ )24 arr[i] = i;25 srand(time(NULL));26 for( int i = 0 ; i < swapTimes ; i ++ ){27 int posx = rand()%n;28 int posy = rand()%n;29 swap( arr[posx] , arr[posy] );30 }31 return arr;32 }33 // 拷贝整型数组a中的所有元素到一个新的数组, 并返回新的数组34 int *copyIntArray(int a[], int n){35 int *arr = new int[n];36 copy(a, a+n, arr);37 return arr;38 }39 // 打印arr数组的所有内容40 template 41 void printArray(T arr[], int n) {42 for (int i = 0; i < n; i++)43 cout << arr[i] << " ";44 cout << endl;45 return;46 }47 // 判断arr数组是否有序48 template 49 bool isSorted(T arr[], int n) {50 for (int i = 0; i < n - 1; i++)51 if (arr[i] > arr[i + 1])52 return false;53 return true;54 }55 // 测试sort排序算法排序arr数组所得到结果的正确性和算法运行时间56 template 57 void testSort(const string &sortName, void (*sort)(T[], int), T arr[], int n) {58 clock_t startTime = clock();59 sort(arr, n);60 clock_t endTime = clock();61 cout << sortName << " : " << double(endTime - startTime) / CLOCKS_PER_SEC << " s"<
选择排序代码：
1 #ifndef OPTIONAL_01_BUBBLE_SORT_SELECTIONSORT_H 2 #define OPTIONAL_01_BUBBLE_SORT_SELECTIONSORT_H 3 #include4 #include 5 using namespace std; 6 template 7 void selectionSort(T arr[], int n){ 8 for(int i = 0 ; i < n ; i ++){ 9 int minIndex = i;10 for( int j = i + 1 ; j < n ; j ++ )11 if( arr[j] < arr[minIndex] )12 minIndex = j;13 swap( arr[i] , arr[minIndex] );14 }15 }16 #endif
插入排序代码：
1 #ifndef OPTIONAL_01_BUBBLE_SORT_INSERTIONSORT_H 2 #define OPTIONAL_01_BUBBLE_SORT_INSERTIONSORT_H 3 #include4 #include 5 using namespace std; 6 template 7 void insertionSort(T arr[], int n){ 8 for( int i = 1 ; i < n ; i ++ ) { 9 T e = arr[i];10 int j;11 for (j = i; j > 0 && arr[j-1] > e; j--)12 arr[j] = arr[j-1];13 arr[j] = e;14 }15 return;16 }17 #endif
冒泡排序以及优化代码：
1 #include2 #include 3 #include "SortTestHelper.h" 4 #include "SelectionSort.h" 5 #include "InsertionSort.h" 6 using namespace std; 7 // 第一版bubbleSort 8 template 9 void bubbleSort( T arr[] , int n){ 10 bool swapped; 11 do{ 12 swapped = false; 13 for( int i = 1 ; i < n ; i ++ ) 14 if( arr[i-1] > arr[i] ){ 15 swap( arr[i-1] , arr[i] ); 16 swapped = true; 17 } 18 // 优化, 每一趟Bubble Sort都将最大的元素放在了最后的位置 19 // 所以下一次排序, 最后的元素可以不再考虑 20 n --; 21 }while(swapped); 22 } 23 // 第二版bubbleSort,使用newn进行优化 24 template 25 void bubbleSort2( T arr[] , int n){ 26 int newn; // 使用newn进行优化 27 do{ 28 newn = 0; 29 for( int i = 1 ; i < n ; i ++ ) 30 if( arr[i-1] > arr[i] ){ 31 swap( arr[i-1] , arr[i] ); 32 // 记录最后一次的交换位置,在此之后的元素在下一轮扫描中均不考虑 33 newn = i; 34 } 35 n = newn; 36 }while(newn > 0); 37 } 38 int main() { 39 int n = 20000; 40 // 测试1 一般测试 41 cout<<"Test for random array, size = "< <<", randome range [0, "< <<"]"<
测试结果:
