【复试总结】绊脚石之选择排序

浏览数：15 / 时间：2015年06月08日

　　这会心情很糟糕啊。被一个自己认为很自信的选择排序绊了一脚。改总结总结。今天下午，如约去了腾达大厦空中网机试了。还是原先那个面试官面我。因为上次已经聊多了，这次就简单说了几句，决定手写一个选择排序作为测试。当时挺自信的。觉得选择排序，很简单啊。拿起笔就写。交换两值函数、寻找最值函数、排序接口函数。嗖嗖嗖的写完了。可想而知，手写代码肯定是有BUG，但是我就这么个盲目的自信的心态，觉额没问题。面试看了一下，让我写出这个程序的运行结果。然后发现问题了，于是修改，又错了。然后就没有然后了。

　　说到这里，也许就该笑话我了。一个选择排序，还一直错。回来路上一直琢磨。想了想，问题其实就出在当判断出最小的值的时候，没有进行最小值替换。可当时愣是没发现。这暴露出一个问题，没有阅读代码的良好功底。代码量是很小，但是遇上我那会的性子，小代码的逻辑就开始混乱了，越改越乱。也就这么一个失误，可能就会让自己错过一次机会。

　　　总结 1、急躁使人愚昧。

　　　　　　2、过度自信是犯错的开始。服从程序，而不是想当然的写程序。

　　错了就错了吧。但是回来还是自己重新写一遍。

先梳理下选择排序的思想。选择区间最值---->与当前位置交换---->缩小区间---->选择新区间的最值--->...

下面是回来自己重新写的SelectSort。以后长记性了。

 1 #include "stdio.h"
 2 #include "stdlib.h"
 3 #include "assert.h"
 4 
 5 
 6 void swap(int *a, int *b);//交换位置
 7 int FindKey(int array[], int low, int high);//找到最值
 8 void select(int array[], int len);//选择排序接口
 9 
10 
11 int main()
12 {
13 
14     int array[11] = { 1, 8, 5, 1, 3, 1, 4, 9, 5, 3, 7 };
15     select(array, sizeof(array) / sizeof(int));
16 
17     for (int i = 0; i < 11; i++)
18     {
19         printf("%d ",array[i]);
20     }
21     system("pause");
22     return 0;
23 }
24 
25 void swap(int *a, int *b)
26 {
27     assert(a != NULL && b != NULL);
28     
29     *a = *a ^ *b;
30     *b = *a ^ *b;
31     *a = *a ^ *b;
32 }
33 
34 int FindKey(int array[], int low, int high)
35 {
36     assert(array!=NULL);
37     assert(low >= 0 && high >= low);
38 
39     int minKey = array[low];
40     int pos = low;
41     int i = 0;
42 
43     for (i = low + 1; i < high; i++)
44     {
45         if (array[i] < minKey)
46         {
47             minKey = array[i];//这里就是我犯错的地方。没有重新复制最小值，排序结果无效
48             pos = i;
49         }
50     }
51     return pos;//返回最值下标
52 }
53 
54 void select(int array[], int len)
55 {
56     assert(array != NULL && len >= 0);
57     
58     int i = 0; 
59     for (i = 0; i < len; i++)
60     {
61         int j = FindKey(array, i, len);
62         if (j != i)
63             swap(&array[i], &array[j]);
64     }
65 }