经典算法回顾冒泡排序【交换排序】

算法思想：对n个数进行排序，需进行n-1趟排序，每次归位一个数。

每次比较两个相邻的元素，如果他们的顺序错误，就把它们交换过来。

复杂度：O(N2)

优化：记录是否发生交换（true：是，false：否）

算法代码：

 1 #include "stdafx.h"
 2 #include <iostream>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 void BubbleSort(int unsorted[],int size)
 7 {
 8     bool flag = true;
 9             
10      while(flag)
11     {
12         for(int i = 0; i < size-1; ++i)//n-1次排序
13         {
14             flag = false;
15             for(int j=1; j<size-i; j++)//！！！注意i和j的范围！！
16             {
17                 if(unsorted[j-1] > unsorted[j])
18                 {
19 
20                     swap(unsorted[j-1],unsorted[j]);//是对j，而不是i
21                     flag = true;
22                  }
23             }
24             if(!flag)
25                 return;
26          }
27     }
28 }
29 
30 int  main()
31 {
32     int unsorted[] = {3,6,1,4,5};
33     int length = sizeof(unsorted)/sizeof(int);
34 
35     for(int i=0;i<length;++i)
36        cout<<unsorted[i]<<" ";
37     cout<<endl;
38 
39     BubbleSort(unsorted,length);
40 
41     for(int i=0;i<length;++i)
42         cout<<unsorted[i]<<" ";
43     cout<<endl;
44 
45     return 0;
46 }