排序演算法總結

  • 2020 年 8 月 18 日
  • 筆記

今天在複習了以前的筆記，發現我有很多遺忘又很重要的知識點。

排序演算法，我自己明白的：1、冒泡排序演算法。2、選擇排序演算法。其中選擇排序演算法又分為數組和鏈表的。3、STL函數中的sort()函數調用（最簡便的。。。）

首先明白選擇排序演算法和冒泡排序演算法的區別:（選自度娘）

冒泡演算法，每次比較如果zhi發現較小的元素在後面，就交換兩個相鄰的元素。

而選擇排序演算法的改進在於：先並不急於調換位置，先從A[1]開始逐個檢查，看哪個數最小就記下該數所在的位置P，等一躺掃描完畢，再把A[P]和A[1]對調，這時A[1]到A[10]中最小的數據就換到了最前面的位置。

所以，選擇排序每掃描一遍數組，只需要一次真正的交換，而冒泡可能需要很多次。比較的次數一樣的。

 

數組的方法..

 1 //選擇法排序（以數組實現）
 2 int main()
 3 {
 4     int arr[10] = { 0 };
 5     int n = sizeof(arr) / sizeof(arr[0]);
 6     int i = 0, j = 0, min = 0;
 7 
 8     printf("請輸入%d個int數據\n", n);
 9     for (i = 0; i < n-1; i++)
10     {
11         for (min = i, j = min + 1; j < n; j++)
12         {
13             if (arr[min] > arr[j])
14                 min = j;
15         }
16 
17         if (min != i)
18         {
19             int tmp = 0;
20             tmp = arr[i];
21             arr[i] = arr[min];
22             arr[min] = tmp;
23         }
24     }
25 
26     for (i = 0; i < n; i++)
27     {
28         printf("%d", arr[i]);
29     }
30     printf("\n");
31 
32     return 0;
33 }

 

 

 鏈表的方法…

 

 

 

 

 

 1 void sort_link(STU *head)
 2 {
 3     //1、判斷鏈表是否存在
 4     if(NULL == head)
 5     {
 6         printf("link not found\n");
 7         return;
 8     }
 9     else
10     {
11         STU *p_i = head;//i=0 
12         while(p_i->next != NULL)//i<n-1  外層循環
13         {
14             STU *p_min = p_i;//min = i;
15             STU *p_j = p_min->next;//j = min+1
16             while(p_j != NULL)//j<n  內層循環
17             {
18                 
19                 //尋找成員num最小值的 節點
20                 if(p_min->num > p_j->num)//if(arr[min] > arr[j])
21                     p_min = p_j;//min = j
22                 p_j = p_j->next;//j++
23             
24             }
25 
26             if(p_min != p_i)//min != i
27             {
28                 //只交換數據域（1、節點內容整體交換   2、只交換指針域）
29                 //1、節點內容整體交換(數據域交換第1次   指針域交換第1次)
30                 STU tmp;
31                 tmp = *p_i;
32                 *p_i = *p_min;
33                 *p_min = tmp;
34 
35                 //2、只交換指針域(指針域交換第2次)
36                 tmp.next = p_i->next;
37                 p_i->next = p_min->next;
38                 p_min->next = tmp.next;
39             }
40 
41 
42             p_i = p_i->next;//i++
43         }
44         
45     }
46     
47 }

最後還有一個STL庫里的sort()函數。把數字存到容器里就可用…

VirMach 便宜 VPS

QNews

QNews