排序算法总结

╰半橙微兮° 2022-04-12 08:57 197阅读 0赞

## 排序算法总结 ##

<table> 
 <thead> 
  <tr> 
   <th align="center">排序算法</th> 
   <th align="center">平均时间复杂度</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center">冒泡排序</td> 
   <td align="center">O(n2)</td> 
  </tr> 
  <tr> 
   <td align="center">选择排序</td> 
   <td align="center">O(n2)</td> 
  </tr> 
  <tr> 
   <td align="center">插入排序</td> 
   <td align="center">O(n2)</td> 
  </tr> 
  <tr> 
   <td align="center">希尔排序</td> 
   <td align="center">O(n1.5)</td> 
  </tr> 
  <tr> 
   <td align="center">快速排序</td> 
   <td align="center">O(N*logN)</td> 
  </tr> 
  <tr> 
   <td align="center">归并排序</td> 
   <td align="center">O(N*logN)</td> 
  </tr> 
  <tr> 
   <td align="center">堆排序</td> 
   <td align="center">O(N*logN)</td> 
  </tr> 
  <tr> 
   <td align="center">基数排序</td> 
   <td align="center">O(d(n+r))</td> 
  </tr> 
 </tbody> 
</table>

#### 一、冒泡排序(BubbleSort) ####

1.  **基本思想：** 两个数比较大小，较大的数下沉，较小的数冒起来。
2.  **过程：**
    
    1.  比较相邻的两个数据，如果第二个数小，就交换位置。
    2.  从后向前两两比较，一直到比较最前的两个数据。最终最小数被交换到起始位置，这样第一个最小数的位置就排好了。
    3.  继续重复上诉过程，依次酱2，3…n-1个最小数排好位置。
    4.

3.**平均时间复杂度：** O(n2)  
4.**C代码实现：**

1 #include <stdio.h>
      2 #include <stdbool.h>
      3 
      4 void BubbleSort(int Array_test[], int n){
      5 
      6     int i, j;
      7     bool flag;
      8     for ( i = n -1; i > 0; --i){
      9         flag = false;
     10         for ( j = 0; j < i; j ++)
     11             if ( Array_test[j] > Array_test[j+1]){
     12                 int temp = Array_test[j];
     13                 Array_test[j] = Array_test[j+1];
     14                 Array_test[j+1] = temp;
     15                 flag = true;
     16             }
     17         if (!flag)
     18             break;
     19     }
     20 }
     21 
     22 void main(){
     23 
     24     int i;
     25     int Array_test[10] = {23, 46, 37, 4, 18, 33, 80, 75, 28, 10};
     26 
     27     BubbleSort(Array_test, 10);
     28     printf("排序后的数组为：\n");
     29     for ( i = 0; i < 10; i++)
     30         if ( i < 9)
     31             printf("%d-", Array_test[i]);
     32         else
     33             printf("%d\n", Array_test[i]);
     34 }

#### 二、选择排序 ####

1.  **基本思想：**  
    在长度为N的无序数组中，第一次扁你n-1个数，找到最小的数值与第一个元素交换；  
    低而磁遍历n-2个数，找到最小值与第二个元素交换；  
    。。。  
    第n-1次遍历，找到最小的数值与第n-1个元素减缓，完成排序。
2.