1 #include <iostream>

 3 #include "SortTestHelper.h"

 4

 5 using namespace std;

 6

 7 template<typename T>

 8 void selectionSort(T arr[],int n){

 9     for(int i = 0 ; i < n ; i ++){

10         int minIndex = i;

11         for( int j = i + 1 ; j < n ; j ++ )

12             if( arr[j] < arr[minIndex] )

13                 minIndex = j;

14         swap( arr[i] , arr[minIndex] );

15     }

16 }

17

18 template<typename T>

19 void insertionSort(T arr[],int n){

20     for(int i = 1 ; i < n ; i++ ){

21         T e = arr[i];

22         int j;

23         for(j = i ; j > 0 && arr[j-1] > e ; j --)

24             arr[j] = arr[j-1];

25         arr[j] = e;

26     }

27 }

28

29 int main(){

30     int n = 100000;

31     int *arr = SortTestHelper::generateNearlyOrderedArray(n,10);

32

33     SortTestHelper::testSort("Insertion Sort",insertionSort,arr,n);

34     SortTestHelper::testSort("Selection Sort",selectionSort,arr,n);

35

36     delete[] arr;

37     return 0;

38 }

 1 #include <iostream>

 2 #include <ctime>

 3 #include <cassert>

 4 #include <string>

 5

 6 using namespace std;

 7

 8 namespace SortTestHelper{

 9     int *generateRandomArray(int n,int rangeL,int rangeR){

10         assert(rangeL <= rangeR);

11         int *arr = new int[n];

12         srand(time(NULL));

13         for(int i = 0 ; i < n ; i++)

14             arr[i] = rand()%(rangeR-rangeL+1) + rangeL;

15         return arr;

16     }

17

18     int *generateNearlyOrderedArray(int n, int swapTimes){

19         int *arr = new int[n];

20         for(int i = 0 ; i < n ; i ++ )

21             arr[i] = i;

22         srand(time(NULL));

23         for( int i = 0 ; i < swapTimes ; i ++){

24             int posx = rand()%n;

25             int posy = rand()%n;

26             swap( arr[posx] , arr[posy] );

27         }

28         return arr;

29     }

30

31     template<typename T>

32     void printArray(T arr[],int n){

33         for(int i = 0;i<n;i++)

34             cout << arr[i] <<" ";

35         cout << endl;

36         return;

37     }

38

39     template<typename T>

40     bool isSorted(T arr[],int n){

41         for(int i = 0 ; i<n-1 ; i++)

42             if(arr[i] > arr[i+1])

43                 return false;

44             return true;

45     }

46     template<typename T>

47     void testSort(const string &sortName,void (*sort)(T[],int),T arr[],int n){

48

49         clock_t startTime = clock();

50         sort(arr,n);

51         clock_t endTime = clock();

52

53         assert(isSorted(arr,n));

54

55         cout << sortName << " : " << double(endTime-startTime)/CLOCKS_PER_SEC << " s" <<endl;

56

57         return;

58     }

59 }

 1 template<typename T>

 2 void bubbleSort( T arr[] , int n){

 3

 4     bool swapped;

 5

 6     do{

 7         swapped = false;

 8         for( int i = 1 ; i < n ; i ++ )

 9             if( arr[i-1] > arr[i] ){

10                 swap( arr[i-1] , arr[i] );

11                 swapped = true;

12

13             }

14

15         // 优化, 每一趟Bubble Sort都将最大的元素放在了最后的位置

16         // 所以下一次排序, 最后的元素可以不再考虑

17         n --;

18

19     }while(swapped);

20 }

 1 template<typename T>

 2 void bubbleSort2( T arr[] , int n){

 3

 4     int newn; // 使用newn进行优化

 5

 6     do{

 7         newn = 0;

 8         for( int i = 1 ; i < n ; i ++ )

 9             if( arr[i-1] > arr[i] ){

10                 swap( arr[i-1] , arr[i] );

11

12                 // 记录最后一次的交换位置,在此之后的元素在下一轮扫描中均不考虑

13                 newn = i;

14             }

15         n = newn;

16     }while(newn > 0);

17 }