排序演算法01------------------------------------冒泡排序-有解無憂

1.排序演算法在編程中必不可少，也很常用，是必須要學的，

2.就我本人看來，最適合練習各種演算法的語言非C語言不可，C語言本身語法簡單直接明了，沒有太多的封裝，很適合描述演算法的各步驟，

一 .冒泡排序

　　1）冒泡排序在排序演算法中比較常見，也很簡單，適合資料量不是很大的程式，適合日常使用，

　　2）冒泡排序的原理（以升序為例）：將相鄰的兩個元素進行比較，如果前面的元素比后面的元素大，則兩個元素進行交換，否則就進行下兩個相鄰元素的比較，

　　　　這樣進行過一趟的比較，就可以把最大的元素排在最后面了，再對剩下的元素進行同樣的操作，即可排序好，這樣的排序就像冒泡一樣，符合的元素慢慢“浮”到頂端，故名冒泡排序，

　　3）代碼如下，已寫好注釋，

 1 #include<stdio.h>
 2 //arr陣列，num 元素個數 
 3 void bubbleSort(int *arr,int num)
 4 {
 5     int i,j;
 6     int temp;
 7     for(i=0;i<num-1;i++)//有num個元素，需要比較num-1次 
 8     {
 9         for(j=0;j<num-i-1;j++)//每一次的比較，需要進行num-i-1次比較， 
10         {                        //這里的i表示已經排序好的元素個數
11                  //升序排序
12             if(arr[j]>arr[j+1])//如果前面的比后面的大，則進行交換 
13             {
14                 temp=arr[j];
15                 arr[j]=arr[j+1];
16                 arr[j+1]=temp;
17             }
18         }
19     }
20 }
21 int main()
22 {    
23     int i; 
24     int arr[10]={1,3,-9,0,10,2,8,9,19,-1};
25     bubbleSort(arr,10);//冒泡排序
26     for(i=0;i<10;i++)
27         printf("%d\n",arr[i]);
28     return 0;
29 }

演算法時間復雜度：O(n²)，n個元素，需要n-1次比較，每次比較需要進行n-i-1次比較，

二.拓展

曾經見過一個問題，問：有什么方法可以提升冒泡排序的效率？

答案是：設定一個標志flag,用這個flag表示每一次的比較是否有元素進行交換，如果沒有交換，則說明這些元素已經排好序了，那就沒必要繼續比較下去，演算法到此結束，

修改后的bubbleSort如下

 1 void bubbleSort(int *arr,int num)
 2 {
 3     int i,j;
 4     int temp;
 5     int flag=0;//0表示沒有交換，1表示有交換 
 6     for(i=0;i<num-1;i++)//有num個元素，需要比較num-1次 
 7     {
 8         for(j=0;j<num-i-1;j++)//每一次的比較，需要進行num-i-1次比較， 
 9         {                        //這里的i表示已經排序好的元素個數
10                  //升序排序
11             if(arr[j]>arr[j+1])//如果前面的比后面的大，則進行交換 
12             {
13                 temp=arr[j];
14                 arr[j]=arr[j+1];
15                 arr[j+1]=temp;
16                 flag=1; 
17             }
18         }
19         if(flag==0)//沒有交換，已排好序，直接結束回圈 
20             break;
21         flag=0; 
22     }
23 }

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/43027.html

標籤：C

上一篇：Ubuntu下實作歌詞決議

下一篇：C語言設計實驗報告（第三次）