三种排序算法

　　从小到大排序

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

 1 #include
 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²)

 1 #include
 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²)，平均时间复杂度为Θ(N㏒N)，最常用

 1 #include
 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 }

数据结构与算法学习笔记

三种排序算法

相关

标签