算法改变人生 2019-11-08
选择式排序(select sorting)也属于内部排序法,是从欲排序的数据中,按指定的规则选出某一元素,再依规定交换位置后达到排序的目的。
基本思想是:第一次从 arr[0]~arr[n-1]中选取最小值,与 arr[0]交换,第二次从 arr[1]~arr[n-1]中选取最小值,与 arr[1]交换,第三次从 arr[2]~arr[n-1]中选取最小值,与 arr[2]交换,…,第 i 次从 arr[i-1]~arr[n-1]中选取最小值,与 arr[i-1]交换,…, 第 n-1 次从 arr[n-2]~arr[n-1]中选取最小值,与 arr[n-2]交换,总共通过 n-1 次,得到一个按排序码从小到大排列的有序序列。
1.选择排序一共有数组大小-1 次排序
2.每一次排序,又是一个循环,循环规则如下
2.1 先假定当前这个数是最小数
2.2 然后和后面的每个数进行比较,如果发现有比当前数更小的数,就重新确定最小数,并得到下标
2.3 当遍历到数组的最后时,就得到本轮最小数和小标
2.4 交换代码,再继续
/** * @author: Coder编程 * @create: 2019-6-20 22:06 * @description: 选择排序 **/ public class SelectionSort { /** * 选择排序 * @param arr 待排序数组 */ public void selectionSort(Integer[] arr) { // 需要遍历获得最小值的次数 // 要注意一点,当要排序 N 个数,已经经过 N-1 次遍历后,已经是有序数列 for (int i = 0; i < arr.length - 1; i++) { int minindex = i; // 用来保存最小值得索引 int min = arr[i]; // 用来保存最小值 for (int j = i + 1; j < arr.length; j++) { if (min > arr[j]) {// 说明假定的最小值,并不是最小 min = arr[j]; // 重置 min minindex = j; // 重置 minIndex } } // 如果假定最小值的索引发生了改变,则进行交换 if(minindex != i){ arr[minindex] = arr[i]; //此时minindex为j,因此i与j交换 arr[i] = min; //最小值给下标i } System.out.format("\n第 %d 趟:\t", i + 1); Arrays.asList(arr).stream().forEach(x -> System.out.print(x + " ")); } } public static void main(String[] args) { //初始数组 Integer arrays[] = {2,9,7,5,3}; // 调用选择排序方法 SelectionSort selection = new SelectionSort(); System.out.print("欢迎个人公众号Coder编程:选择排序前:\t"); Arrays.asList(arrays).stream().forEach(x -> System.out.print(x + " ")); selection.selectionSort(arrays); System.out.print("\n欢迎个人公众号Coder编程:选择排序后:\t"); Arrays.asList(arrays).stream().forEach(x -> System.out.print(x + " ")); } }
打印结果
如果还有什么不理解的,可以把代码Debug抛一遍就明白了。
简单选择排序的比较次数与序列的初始排序无关。 假设待排序的序列有n个元素,则比较次数总是n(n - 1) / 2。
而移动次数与序列的初始排序有关。当序列正序时,移动次数最少,为 0.
当序列反序时,移动次数最多,为3n (n- 1) / 2。
所以,综合以上,简单排序的时间复杂度为 O(n^2)。
简单选择排序需要占用 1 个临时空间,在交换数值时使用。
#include <stdio.h> int main() { int i,j,t,a[11]; //定义变量及数组为基本整型 printf("请输入10个数:\n"); for(i=1;i<11;i++) scanf("%d",&a[i]); //从键盘中输入要排序的10个数字 for(i=1;i<=9;i++) for (j=i+1;j<=10;j++) if(a[i]>a[j]) //如果前一个数比后一个数大,则利用中间变量t实现两值互换 { t=a[i]; a[i]=a[j]; a[j]=t; } printf("排序后的顺序是:\n"); for(i=1;i<=10;i++) printf("%5d", a[i]); //输出排序后的数组 printf("\n"); return 0; }
def selectedSort(myList): length = len(myList) for i in range(0,length-1): smallest = i for j in range(i+1,length): if myList[j]<myList[smallest]: tmp = myList[j] myList[j] = myList[smallest] myList[smallest]=tmp print("Round ",i,": ",myList) myList = [2,9,7,5,3] print("Selected Sort: ") selectedSort(myList)
var example=[2,9,7,5,3]; function selectSort(arr){ var len=arr.length; var minIndex,temp; console.time('选择排序耗时'); for(i=0;i<len-1;i++){ minIndex=i; for(j=i+1;j<len;j++){ if(arr[j]<arr[minIndex]){ minIndex=j; } } temp=arr[i]; arr[i]=arr[minIndex]; arr[minIndex]=temp; } console.timeEnd('选择排序耗时'); return arr; } console.log(selectSort(example));
欢迎关注个人微信公众号:Coder编程
获取最新原创技术文章和免费学习资料,更有大量精品思维导图、面试资料、PMP备考资料等你来领,方便你随时随地学习技术知识!
新建了一下qq群:315211365,欢迎大家进群交流一起学习。谢谢了!也可以介绍给身边有需要的朋友。
文章收录至
Github: https://github.com/CoderMerli...
Gitee: https://gitee.com/573059382/c...
参考文章:
https://blog.csdn.net/qq_3624...
https://www.cnblogs.com/shen-...
推荐文章: