1. 首页
  2. 程序人生

面试官:你都工作3年了,连选择排序法都不会,我怎么能选择你

面试时,算法经常会遇到,特别是一些常见的算法。 张工毕业3年了,一直在一家创业公司做java开发,最近到某知名互联网公司面试,做了笔试题后,面试官看了觉得还不错,于是想进一步考察张工的编码能力,就让他手写选择排序算法,张工写不出来,面试官说:你都毕业3年了,连个选择排序法都写不出来, 我参加计算机等级考试就会这个了 。 张工一脸的无助,不过确实不应该,类似选择排序这样基础的算法,平时应该要掌握好才对。 小编之前参加的笔试也遇到了手写排序算法的情况,关于选择排序可能基本都能写出来,但要是能把程序再优化一下,那就更好了,相信能给面试官留下更好的印象。 我们先来看什么选择排序法:
选择排序法是一种 不稳定 的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到全部待排序的数据元素排完。

640?wx_fmt=gif

稳定性选择排序是给每个位置选择当前元素最小的,比如给第一个位置选择最小的,在剩余元素里面给第二个元素选择第二小的,依次类推,直到第n-1个元素,第n个元素不用选择了,因为只剩下它一个最大的元素了。那么,在一趟选择,如果一个元素比当前元素小,而该小的元素又出现在一个和当前元素相等的元素后面,那么交换后稳定性就被破坏了。 举个例子,序列6 8 6 3 9,我们知道第一遍选择第1个元素6会和3交换,那么原序列中两个6的相对前后顺序就被破坏了,所以选择排序是一个不稳定的排序算法。 关于时间复杂度选择排序的交换操作介于 0 和 (n – 1) 次之间。选择排序的比较操作为 n (n – 1) / 2 次之间。选择排序的赋值操作介于 0 和 3 (n – 1) 次之间。比较次数O(n^2),比较次数与关键字的初始状态无关,总的比较次数N=(n-1)+(n-2)+…+1=n*(n-1)/2。交换次数O(n),最好情况是,已经有序,交换0次;最坏情况交换n-1次,逆序交换n/2次。交换次数比冒泡排序少多了,由于交换所需CPU时间比比较所需的CPU时间多,n值较小时,选择排序比冒泡排序快。其中直接选择排序的时间复杂度为O(n*n),空间复杂度为O(1)。树形选择排序的时间复杂度为O(nlog2n),空间复杂度为O(n)。堆排序的平均时间复杂度为O(nlog2n),效率高,但是实现相对复杂,空间代价为O(1)。
我们来看用java编写的选择排序算法代码/**
* 选择排序
*
* @param arr
*/

public static void selectionSort(int[] arr) {
int min;
int length = arr.length;
for ( int i = 0; i < length; i++) {
// 初始化未排序序列中最小数据数组下标
min = i;
for ( int j = i + 1; j < length; j++) {
// 在未排序元素中继续寻找最小元素,并保存其下标
if (arr[j] < arr[min]) {
min = j;
}
}
// 将未排序列中最小元素放到已排序列末尾
if (min != i) {
swap(min, i, arr);
}
}
}

/**
* 交换顺序
*
* @param x
* @param y
* @param arr
*/

private static void swap(int x, int y, int[] arr) {
int temp = arr[x];
arr[x] = arr[y];
arr[y] = temp;
}
调用实例public static void main(String[] args) {
int arr[] = { 2, 17, 2, 11, 7, 6, 19, 9, 14, 20, 17, 13, 14, 2, 10};
System.out.println(String.format( “original array = %s\n”, Arrays.toString(arr)));
selectionSort(arr);
System.out.println(String.format( “sorted array = %s\n”, Arrays.toString(arr)));
}输出结果

640?wx_fmt=png

对于选择排序算法,要是还是不太好理解,我们来看一下动画图,这样会更容易理解些。

640?wx_fmt=gif

不知你对选择排序算法是否完全理解。

选择排序法基本来说还是挺不错的,数据规模不大时,还是推荐使用的,但相对于其他的排序算法(譬如快速排序)效率还是明显有些不足。 小编认为,关于选择排序法思想还是挺重要,要重视。

本文来自CSDN-爱开发V,本文观点不代表网巢立场,转载请联系原作者。

发表评论

邮箱地址不会被公开。 必填项已用*标注

联系我们

159-0364-1529

在线咨询:点击这里给我发消息

邮件:122571245@qq.com

工作时间:周一至周日,9:30-18:30,节假日休息

QR code