β

常见排序算法之简单选择排序

自由 96 阅读

排序算法是程序员日常生活中不怎么使用,但必须了解、熟读、记住的内容,这也是区分一个菜鸟和高级的一道坎,虽然我们日常使用的语言,比如Java、c#都对这些算法进行了封装,我们只需要拿来用就ok,但了解、熟悉算法的实现,有助于我们在现实生活中去解决复杂灵活的各种问题。

sort-algorithm

选择排序算法

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。 — 维基百科

Simple Selection Sort,顾名思义,就是简单的每次选择这次遍历中最小的记录放到当前的位置,等到遍历完成后,整个数组也就是有序的了。

思路:通过 n-i 次比较关键字的大小,找出 n-i+1 个数字中最小的关键字的下标,并与第i个记录进行交换。

看代码演示:

/**
* 简单选择排序
* 通过n-i次关键字之间的比较,从n-i+1个记录中选出关键字最小的记录
* @param array
*/
public static void SimpleSelectionSort(int[] array){
int minIndex;
for(int i=0;i<array.length;i++){
minIndex=i;
// 寻找与i相比最小数的下标
for(int j=i+1;j<array.length;j++){
if(array[minIndex] > array[j]){
minIndex =j;
}
}
// 如果存在比 arr[minIndex] 小的记录,则进行交换
if(minIndex !=i){
Swap(array,minIndex,i);
}
}
}

// 交换数组位置
public static void Swap(int[] array,int start,int end){
int temp=array[start];
array[start] = array[end];
array[end] =temp;
}

简单选择排序的特点是交换移动次数很少,这样就节约了时间,其时间复杂度为 O(n²) ,与冒泡排序一样,但性能上优于冒泡。

源码参见github: https://github.com/xirong/my-java/blob/master/sort-algorithm/SelectionSort.java

排序算法是程序员日常生活中不怎么使用,但必须了解、熟读、记住的内容,这也是区分一个菜鸟和高级的一道坎,虽然我们日常使用的语言,比如Java、c#都对这些算法进行了封装,我们只需要拿来用就ok,但了解、熟悉算法的实现,有助于我们在现实生活中去解决复杂灵活的各种问题。

作者:自由
原文地址:常见排序算法之简单选择排序, 感谢原作者分享。

发表评论