【七类排序】之第三种：选择排序

注：若无特殊说明， 排序以递增为目的。

选择排序（Select Sort)思想和插入排序（Insertion Sort）接近。

令长度为n的数组a[0..n-1]。

选择排序则是将无序区a[i..n-1]中的最小值a[k]插入有序区a[0..i-1]的末位使得a[0..i]成为有序区。
还记得之前的插入排序么， 重温一下， 其思想是：将a[ i ]并入有序区a[0..i-1]使得a[0..i]]成为有序区。

实现非常简单， 每一次遍历记录最小值的位置， 然后与a[ i ]交换即可。
程序核心部分代码为：

for (int i=0; i<n; i++) {
    int flag=i;
    for (int j=i+1; j<n; j++)
         if (a[ j ]<a[ flag ])
             flag = j;

     swap(a[ i ], a[ flag ])
}

就这么直接能写出， 我也想不到什么优化了， 各位有啥ideas的欢迎提出来。

就这样没了好像比较水， 再写一点关于swap函数的东西。
这里， 笔者默认各位懂得指针，形参等概念。
一般来说， swap函数是通过中间变量实现的，推荐的常规写法为:

void swap(int &p, int &q) {
        int temp = p;
        p=q;
        q=temp;
}



然而， 若面试官不允许用中间变量怎么办？ 介绍两种方式。

第一种：


p^=q;
q^=p;
p^=q;

点评：这是经典的异或位运算方式， 不需要中间变量即可完成交换， 但是有一点问题就是， 若p和q指向的是同一个指针， 那么结果会导致p和q置零。 若在选择排序算法中的某次遍历中， flag等于i， 那么执行swap(a[flag], a)则会出现问题，而且很难发现，最严重的情况就是数组原来就有序，那么每次置换都失败。

所以在原函数的基础上加一层判断：
if (p!=q）{
  p^=q;
  q^=p;
  p^=q;

}


第二种：

p=p+q;
q=p-q;
p=p-q;

点评： 很容易理解， but very impressive....

根据KISS原则，交换还是带一个中间变量吧，代码可读性好。

第一个代码最后一行有小错哦，应是 swap(a[ i ], a[ flag ])