一、快排

(nlogn)

我的想法就是：左边第一个作为一个基准元素，然后往后遍历，比基准的小的放基准元素的左边，比基准大的放基准元素的右边，第一次遍历完成时左边都是比基准小的，右边都是比基准大的。（log2n）

二、冒泡

(o(n^2))

我的想法是：1）一个数组两两相邻排序，第一个和第二个比较小的放前面大的放后面，第一趟完了从第二个元素再开始，进

                        过n-1趟以后，就完成了。

                   2） 第二趟对余下的n-1个数（最大的数已经“沉底”），按上法比较，经n-2次两两比较之后得次大的数

                   3） 依此推算，n个数共进行n-1趟比较，在第j趟中要进行n-j次两两比较

 在进行一趟比较排序之后，马上就判断一下这个数组是否已经排好序了，如果已经排好了，那就直接退出。

  

 

   判断是否已经排好序了的函数isSorted()

 

  从0-n-1，只要有一个数不符合排序规矩，就说明这个数还没有排好序

优化：

在函数中定义一个bool 的变量 issorted ，在每趟对剩余的数字排序时，先把它设为true，然后当发生两个两个相邻的数没有按要求排时，在交换这两个数的同时，把issorted设为false，不然就一直保持为true。

      在进行好一趟排序之后，测试issorted这个变量的值，如果保持true，就说明已经排好序了，停止继续排序，不然进行下一趟排序。

 

具体代码：

三、插入排序

我认为：每次从待插入组中取出一个元素，与有序组的元素进行比较，并找到合适的位置，将该元素插到有序组当中。一般都是把第一个数据看为有序的。稳定的（o(n^2)）

1. #include<stdio.h>  
2.   void InsertionSort(int *num,int n)   
3.   {  
4.     int i = 0;  
5.     int j = 0;  
6.     int tmp = 0;  
7.     for(i = 1;i<n;i++)  
8.     {  
9.       tmp = num[i];//从待插入组取出第一个元素。   
10.       j = i-1; //i-1即为有序组最后一个元素（与待插入元素相邻）的下标   
11.       while(j>=0&&tmp<num[j])  //注意判断条件为两个，j>=0对其进行边界限制。第二个为插入判断条件   
12.       {  
13.         num[j+1] = num[j];//若不是合适位置，有序组元素向后移动   
14.         j--;   
15.       }  
16.       num[j+1] = tmp;//找到合适位置，将元素插入。   
17.     }  
18.   }  
19.   int main()   
20.   {  
21.     int i = 0;  
22.     int num[8]={9,3,4,2,6,7,5,1};  
23.     InsertionSort(num,8);   
24.     /*这个函数必须知道元素的个数，所以将元素个数传入。 
25.     有心者可以在函数内部用sizeof求出元素个数 */  
26.     for(i=0;i<8;i++)  
27.     {  
28.         printf("%d ",num[i]);  
29.     }  
30.     return 0;  
31.   }  

四、选择排序

在要排序的一组数中，选出最小（或者最大）的一个数与第1个位置的数交换；然后在剩下的数当中再找最小（或者最大）的与第2个位置的数交换，依次类推，直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止。

1. void print(int a[], int n ,int i){  
2.     cout<<"第"<<i+1 <<"趟 : ";  
3.     for(int j= 0; j<8; j++){  
4.         cout<<a[j] <<"  ";  
5.     }  
6.     cout<<endl;  
7. }  
8. /** 
9.  * 数组的最小值 
10.  * 
11.  * @return int 数组的键值 
12.  */  
13. int SelectMinKey(int a[], int n, int i)  
14. {  
15.     int k = i;  
16.     for(int j=i+1 ;j< n; ++j) {  
17.         if(a[k] > a[j]) k = j;  
18.     }  
19.     return k;  
20. }  
21.   
22. /** 
23.  * 选择排序 
24.  * 
25.  */  
26. void selectSort(int a[], int n){  
27.     int key, tmp;  
28.     for(int i = 0; i< n; ++i) {  
29.         key = SelectMinKey(a, n,i);           //选择最小的元素  
30.         if(key != i){  
31.             tmp = a[i];  a[i] = a[key]; a[key] = tmp; //最小元素与第i位置元素互换  
32.         }  
33.         print(a,  n , i);  
34.     }  
35. }  
36. int main(){  
37.     int a[8] = {3,1,5,7,2,4,9,6};  
38.     cout<<"初始值：";  
39.     for(int j= 0; j<8; j++){  
40.         cout<<a[j] <<"  ";  
41.     }  
42.     cout<<endl<<endl;  
43.     selectSort(a, 8);  
44.     print(a,8,8);  
45. }