今天去东鹏特饮面试,我很生气。面的技术岗,卷子竟然是营销的。浪费了我一晚上的时间,害得我差点没赶上地铁的末班车。你能敢相信?这是面
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值较小的时候,如果交换的时间级要比比较的时间级大的多时候,选择排序是相当快的。
今天女朋友跟我说,面试的时候不要带任何主观色彩情绪。女朋友说的很对,我需要再耐心一点,少一点浮躁,多一点沉淀。实话说,我是一个很爱抱怨的人,可是这往往是弱者的表现。在成为强者的路上,我缺的不仅仅是知识,更多的是如何做人。时间也不早了,晚安,地球人。