[算法] O(n^2)算法的效率比较

main.cpp

 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 }

SortTestHelper.h

 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、可提前终止循环

2、没有交换操作

3、对近乎有序数组，插入排序会更快，甚至快于O(nlogn)级算法，在实际中有大量应用

bubbleSort 方法1

 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 }

bubbleSort 方法2

 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 }

bubbleSort的优化：

每轮循环如果没有发生交换，就代表数据已经有序，提前退出
每轮循环中后面的元素如果已经有序，下一轮循环就不再考虑

三种O(n^2)级别算法的思路：

1、冒泡排序：相邻元素作比较，每次循环后最大的元素放在最后

2、选择排序：找到后面最小的元素，每次循环后最小的元素放在最前

3、插入排序：将新元素插入到有序数组中合适的位置