三种排序算法

　　从小到大排序

  • 桶排序 - 时间复杂度为Ο(M+N)，快，但空间复杂度高

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
     1 #include<stdio.h>
     2 
     3 int main() {
     4     int book[1001], n, t;
     5     for(int i = 1; i <= 1000; i++)
     6         book[i] = 0;
     7     scanf("%d", &n); //输入一个数n，表示接下来有n个数
     8     for(int i = 1; i <= n; i++) { //循环读入n个数，并进行桶排序
     9         scanf("%d", &t); //把每一个数读到变量t中
    10         book[t]++; //进行计数，对编号为t的桶放一个小旗子
    11     }
    12     for(int i = 1; i <= 1000; i++) //依次判断编号1000~0的桶
    13         for(int j = 1; j <= book[i]; j++) //出现了几次就将桶的编号打印几次
    14             printf("%d ", i);
    15     return 0;
    16 }

  • 冒泡排序 - 时间复杂度为Ο(N^2)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
     1 #include<stdio.h>
     2 
     3 int main() {
     4     int a[100], t, n;
     5     scanf("%d", &n);  //输入一个数，表示接下来有n个数
     6     for(int i = 1; i <= n; i++)  //循环读入n个数到数组a中
     7         scanf("%d", &a[i]);
     8     //冒泡排序的核心部分
     9     for(int i = 1; i <= n-1; i++) {  //n个数排序，只用进行n-1趟
    10         for(int j = 1; j <= n-i; j++) {  //从第一位开始比较到最后一个尚未归位的数
    11             if(a[j] > a[j+1]) {  //比较大小并交换
    12                 t = a[j];
    13                 a[j] = a[j+1];
    14                 a[j+1] = t;
    15             }
    16         }
    17     }
    18     for(int i = 1; i <= n; i++)  //输出结果
    19         printf("%d ", a[i]);
    20     return 0;
    21 }

  • 快速排序 - 最差时间复杂度为Ο(N^2)，平均时间复杂度为Θ(N㏒N)，最常用

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
     1 #include<stdio.h>
     2 int a[101], n; //全局变量，这两个变量需要在子函数中使用
     3 
     4 void quicksort(int left, int right) {
     5     int i, j, t, temp;
     6     if(left > right)
     7         return;
     8     temp = a[left]; //temp中存的就是基准数
     9     i = left;
    10     j = right;
    11     while(i != j) {
    12         //顺序很重要，要先从右往左找
    13         while(a[j] >= temp && i < j)
    14             j--;
    15         //再从左往右找
    16         while(a[i] <= temp && i < j)
    17             i++;
    18 
    19         //交换两个数在数组中的位置
    20         if(i < j) { //当哨兵i和哨兵j没有相遇时
    21             t = a[i];
    22             a[i] = a[j];
    23             a[j] = t;
    24         }
    25     }
    26     //最终将基准数归位
    27     a[left] = a[i];
    28     a[i] = temp;
    29 
    30     quicksort(left, i - 1); //递归，继续处理左边的
    31     quicksort(i + 1, right); //递归，继续处理左边的
    32 }
    33 
    34 int main() {
    35     scanf("%d", &n);
    36     for(int i = 1; i <= n; i++)
    37         scanf("%d", &a[i]);
    38 
    39     quicksort(1, n); //快速排序调用
    40 
    41     //输出排序后的结果
    42     for(int i = 1; i <= n; i++)
    43         printf("%d ", a[i]);
    44 
    45     return 0;
    46 }