前言
今天去东鹏特饮面试，我很生气。面的技术岗，卷子竟然是营销的。浪费了我一晚上的时间，害得我差点没赶上地铁的末班车。你能敢相信？这是面
Java的试卷。生气归生气，学习还是要继续的。
image.png
什么是选择排序?
选择排序是不稳定的排序。每一趟从待排序的数据元素中选出最小(或者最大)的一个元素放在已排好序的数列的最后，直到全部待排序的数据排完。
选择排序和冒泡排序的区别
-
选择排序相对于冒泡来说，它不是每次发现逆序都要进行交换。
-
选择排序改进了冒泡排序，将必要的交换次数从
O(N^2)减少到O(N)。但是比较的次数还是O(N^2)。 -
选择排序在为大记录量的排序中提出了一个非常重要的改进。因为这些记录需要在内存中移动，这就使交换的时间和比较的时间相比起来，交换的时间更为很重要。在
Java语言中不是这种情况，Java中只是改变了引用位置，而实际对象的位置并没有发生改变。
提取思想
-
进行选择排序就是先遍历所有的数字扫描一趟，从中挑出最小的数据。最小的数字和队列最左边的数字进行交换位置，即站到
0号位置。现在最左端的数字都是有序的，不需要再进行交换位置了。 -
在这个算法中，有序的数字都排列在队列的最左边，而冒泡排序则是排序在队列最右边。
-
再次遍历数据队列时，就从第
1号位置开始了，还是寻找剩下队列中最小的数据，然后和第1号位置的数字进行交换。重复以上过程，一直持续到所有的队员都排定。
手写代码
public class SelectSortDemo {
public static int[] a = { 11, 20, 5, 4, 8, 14, 2, 10, 20, 9 };
public static void main(String[] args) {
sort();
display();
}
public static void sort() {
int count = a.length;
for (int i = 0; i < count - 1; i++) {
int min = i;
for (int k = i + 1; k < count; k++) {
if (a[k] < a[min]) {
min = k;
}
}
if (min != i) {
swap(min, i);
}
}
}
public static void swap(int x, int y) {
int temp = a[x];
a[x] = a[y];
a[y] = temp;
}
public static void display() {
int count = a.length;
for (int i = 0; i < count; i++) {
System.out.print(a[i] + " ");
}
System.out.println("");
}
}
-
运行结果，看输出。
image.png
效率问题
选择排序和冒泡排序都执行了相同次数的比较: N * (N - 1) / 2。对于10个数据项，需要45次比较。然而10个数据项只需要少于10次交换。选择排序和冒泡排序一样运行了O(N^2)时间。但是，选择排序会更快。因为它进行的交换少的很。当N值较小的时候，如果交换的时间级要比比较的时间级大的多时候，选择排序是相当快的。
尾言
今天女朋友跟我说，面试的时候不要带任何主观色彩情绪。女朋友说的很对，我需要再耐心一点，少一点浮躁，多一点沉淀。实话说，我是一个很爱抱怨的人，可是这往往是弱者的表现。在成为强者的路上，我缺的不仅仅是知识，更多的是如何做人。时间也不早了，晚安，地球人。
网友评论