选择排序算法,C语言选择排序算法详解
选择排序是一种简单直观的排序算法。它与冒泡排序很相似,都是比较 n-1 轮,每轮都是比较 n–1–i 次,每轮找出一个最大值或最小值。
只不过,冒泡排序是将每轮找出的最值放到最右边,而选择排序是将每轮找出的最值放到最左边。并且在算法上,冒泡排序是将相邻的数进行逐个比较,以从小到大排序为例,只要前面的比后面的大,就互换这两个数,直到最后将最大的数“浮”到最右边,如此依次循环。而选择排序是先保存第一个元素的下标,然后后面所有的数依次与第一个元素相比,如果遇到更小的,则记录更小的那个数的下标,然后后面所有的数都依次与那个更小的数比较,直到最后将最小的数的下标找出来,然后再将这个数放到最左边,即与下标为 0 的数互换。如果最小的数的下标就是 0 那么就不用互换。
所以,选择排序算法是先判断最小的数的下标是不是 0,如果不是则说明最小的数不是第一个元素,则将这个数与第一个元素互换位置,这样一轮下来最小的那个数就被找到并放到了最左边。
在第二轮同样先保存新序列第二个元素的下标,后面所有的数依次与第二个元素相比较,如果遇到更小的则记录更小的那个数的下标,然后后面所有的数都依次与那个更小的数比较,直到最后又找到一个最小的,此时这个最小的在整个序列中是“第二小”。然后再判断这个数的下标是否等于 1,如果不等于 1 说明“第二小”的那个数不是第二个元素,则将这个数与第二个元素互换位置,这样第二轮下来就找到了“第二小”的那个数,并将它放到了第二个位置。如此循环,直到整个序列实现从小到大排序。
如果是从大到小排序,那么就记录大的那个数的下标,每一轮找出一个最大的数放到左边。
从上面的分析可以看出,选择排序和冒泡排序的另一个不同点是,冒泡排序只要遇到前面比后面大的就互换,而选择排序是比较一轮才互换一次,而且如果本轮中最小的就是最左边那个数则不用互换。所以从这个角度看,选择排序比冒泡排序的效率要高。而且通过上面对选择排序的分析发现,从逻辑上讲,与冒泡排序相比,选择排序更符合人的思维。
下面来写一个程序,用选择排序实现一个序列的从小到大排序:
最终排序结果为:
1 2 3 4 4 5 5 5 6 7 8 9
通过程序可以看出,虽然选择排序比冒泡排序的效率高,逻辑上也更符合人的思维,但是程序相对更复杂,冒泡排序比选择排序在逻辑上要清晰一点,也稍微简单一点。
只不过,冒泡排序是将每轮找出的最值放到最右边,而选择排序是将每轮找出的最值放到最左边。并且在算法上,冒泡排序是将相邻的数进行逐个比较,以从小到大排序为例,只要前面的比后面的大,就互换这两个数,直到最后将最大的数“浮”到最右边,如此依次循环。而选择排序是先保存第一个元素的下标,然后后面所有的数依次与第一个元素相比,如果遇到更小的,则记录更小的那个数的下标,然后后面所有的数都依次与那个更小的数比较,直到最后将最小的数的下标找出来,然后再将这个数放到最左边,即与下标为 0 的数互换。如果最小的数的下标就是 0 那么就不用互换。
所以,选择排序算法是先判断最小的数的下标是不是 0,如果不是则说明最小的数不是第一个元素,则将这个数与第一个元素互换位置,这样一轮下来最小的那个数就被找到并放到了最左边。
在第二轮同样先保存新序列第二个元素的下标,后面所有的数依次与第二个元素相比较,如果遇到更小的则记录更小的那个数的下标,然后后面所有的数都依次与那个更小的数比较,直到最后又找到一个最小的,此时这个最小的在整个序列中是“第二小”。然后再判断这个数的下标是否等于 1,如果不等于 1 说明“第二小”的那个数不是第二个元素,则将这个数与第二个元素互换位置,这样第二轮下来就找到了“第二小”的那个数,并将它放到了第二个位置。如此循环,直到整个序列实现从小到大排序。
如果是从大到小排序,那么就记录大的那个数的下标,每一轮找出一个最大的数放到左边。
从上面的分析可以看出,选择排序和冒泡排序的另一个不同点是,冒泡排序只要遇到前面比后面大的就互换,而选择排序是比较一轮才互换一次,而且如果本轮中最小的就是最左边那个数则不用互换。所以从这个角度看,选择排序比冒泡排序的效率要高。而且通过上面对选择排序的分析发现,从逻辑上讲,与冒泡排序相比,选择排序更符合人的思维。
下面来写一个程序,用选择排序实现一个序列的从小到大排序:
# include <stdio.h> int main(void) { int i, j; //循环变量 int MinIndex; //保存最小的值的下标 int buf; //互换数据时的临时变量 int a[] = {5, 5, 3, 7, 4, 2, 5, 4, 9, 1, 8, 6}; int n = sizeof(a) / sizeof(a[0]); //存放数组a中元素的个数 for (i=0; i<n-1; ++i) //n个数比较n-1轮 { MinIndex = i; for (j=i+1; j<n; ++j) //每轮比较n-1-i次, 找本轮最小数的下标 { if (a[MinIndex] > a[j]) { MinIndex = j; //保存小的数的下标 } } if (MinIndex != i) /*找到最小数之后如果它的下标不是i则说明它不在最左边, 则互换位置*/ { buf = a[MinIndex]; a[MinIndex] = a[i]; a[i] = buf; } } printf("最终排序结果为:\n"); for (i=0; i<12; ++i) { printf("%d ", a[i]); } printf("\n"); return 0; }输出结果是:
最终排序结果为:
1 2 3 4 4 5 5 5 6 7 8 9
通过程序可以看出,虽然选择排序比冒泡排序的效率高,逻辑上也更符合人的思维,但是程序相对更复杂,冒泡排序比选择排序在逻辑上要清晰一点,也稍微简单一点。
所有教程
- socket
- Python基础教程
- C#教程
- MySQL函数
- MySQL
- C语言入门
- C语言专题
- C语言编译器
- C语言编程实例
- GCC编译器
- 数据结构
- C语言项目案例
- C++教程
- OpenCV
- Qt教程
- Unity 3D教程
- UE4
- STL
- Redis
- Android教程
- JavaScript
- PHP
- Mybatis
- Spring Cloud
- Maven
- vi命令
- Spring Boot
- Spring MVC
- Hibernate
- Linux
- Linux命令
- Shell脚本
- Java教程
- 设计模式
- Spring
- Servlet
- Struts2
- Java Swing
- JSP教程
- CSS教程
- TensorFlow
- 区块链
- Go语言教程
- Docker
- 编程笔记
- 资源下载
- 关于我们
- 汇编语言
- 大数据
- 云计算
- VIP视频