前言
- 常见的几种排序,针对不同数据,数据量,找到最合适的算法,是衡量一个程序员的基本标准,因此掏出小本子,又复习(其实因为不常用,已经忘完了~~)
代码示例如下
公共部分
int i,j,t,a[10],min;
printf("请输入10个整数:\n");
for (i = 0; i < 10; i++) {
scanf("%d",&a[i]);
}
printf("\n");
- 冒泡排序法
俗称 打擂台,从第一个元素开始,依次与后面的元素比较 平均时间复杂度：O(n^2) 平均空间复杂度：O(1) .
for (i = 0; i < 10; i++) {
for (j = 0; j < 9-i; j++) {
if (a[j] > a[j+1]) {
t = a[j];
a[j] = a[j+1];
a[j+1] = t;
}
}
}
- 插入排序法
1. 从第一个元素开始，认为该元素已经是排好序的。
2. 取下一个元素，在已经排好序的元素序列中从后向前扫描。
3. 如果已经排好序的序列中元素大于新元素，则将该元素往右移动一个位置。
4. 重复步骤3，直到已排好序的元素小于或等于新元素。
5. 在当前位置插入新元素。
6. 重复步骤2。 平均时间复杂度：O(n^2) 平均空间复杂度：O(1)
代码示例:
for (i = 1; i < 10; i ++) {
t = a[i];
for (j = i; j > 0 && t < a[j-1];j--) {
a[j] = a[j - 1];
}
a[j] = t;
}
-
选择排序
假设第一个元素是最小值,下标记为min,循环剩余元素,记下下标,再与之前的最小值相比较,以此不断找出最小值,排到最前面for (i= 0; i < 10; i++) { min = i; for (j = i+1; j < 10; j++) { if (a[min] > a[j]) { min = j; } } //说明a[min]目前不是最小值,需要交换位置 if (min != i) { t = a[min]; a[min] = a[i]; a[i] = t; } }
