算法笔记 - 排序

本文主要是介绍算法笔记 - 排序，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

• 桶排序 - 空间复杂度高

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

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

 1 //冒泡排序 从大到小排序
 2 
 3 //书上给的
 4 #include<stdio.h>
 5 
 6 int main() {
 7     int a[100], i, j, t, n;
 8     scanf("%d", &n);  //输入一个数，表示接下来有n个数
 9     for(i = 1; i <= n; i++)  //循环读入n个数到数组a中
10         scanf("%d", &a[i]);
11     //冒泡排序的核心部分
12     for(i = 1; i <= n-1; i++) {  //n个数排序，只用进行n-1趟
13         for(j = 1; j <= n-i; j++) {  //从第一位开始比较到最后一个尚未归位的数
14             if(a[j] < a[j+1]) {  //比较大小并交换
15                 t = a[j];
16                 a[j] = a[j+1];
17                 a[j+1] = t;
18             }
19         }
20     }
21     for(i = 1; i <= n; i++)  //输出结果
22         printf("%d ", a[i]);
23     return 0;
24 }
25 
26 /* 我的尝试
27 #include<stdio.h>
28 
29 int main() {
30     int n, i, j, t;
31     scanf("%d", &n);
32     int arr[n+1];
33     for(i = 1; i <= n; i++)
34         scanf("%d", &arr[i]);
35     for(i = n; i >= 1; i--) {
36         for(j = 2; j <= i; j++)
37             if(arr[j] > arr[j-1]) {
38                 t = arr[j];
39                 arr[j] = arr[j-1];
40                 arr[j-1] = t;
41             }
42     }
43     for(i = 1; i <= n; i++)
44         printf("%d ", arr[i]);
45     return 0;
46 }
47 */

• 三、快速排序 - 最差时间复杂度为Ο(N²)，平均时间复杂度为Θ(N㏒N)

 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 
35 int main() {
36     int i, j, t;
37     //读入数据
38     scanf("%d", &n);
39     for(i = 1; i <= n; i++)
40         scanf("%d", &a[i]);
41 
42     quicksort(1, n); //快速排序调用
43 
44     //输出排序后的结果
45     for(i = 1; i <= n; i++)
46         printf("%d ", a[i]);
47 
48     return 0;
49 }

这篇关于算法笔记 - 排序的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！