首页 / 软件开发 / 数据结构与算法 / 经典算法（4） 直接选择排序及交换二个数据的正确实现

经典算法（4） 直接选择排序及交换二个数据的正确实现2014-01-03 csdn MoreWindows直接选择排序和直接插入排序类似，都将数据分为有序区和无序区，所不同的是直接播放排序是将无序区 的第一个元素直接插入到有序区以形成一个更大的有序区，而直接选择排序是从无序区选一个最小的元素直 接放到有序区的最后。

设数组为a[0…n-1]。

1. 初始时，数组全为无序区为a[0..n-1]。令 i=0

2. 在无序区a[i…n-1]中选取一个最小的元素，将其与a[i]交换。交换之后a[0…i]就形成了一个 有序区。

3. i++并重复第二步直到i==n-1。排序完成。

直接选择排序无疑是最容易实现的， 下面给出代码：

void Selectsort（int a[], int n）{int i, j, nMinIndex;for （i = 0; i < n; i++）{nMinIndex = i; //找最小元素的位置for （j = i + 1; j < n; j++）if （a[j] < a[nMinIndex]）nMinIndex = j;Swap（a[i], a[nMinIndex]）; //将这个元素放到无序区的开头 //www.bianceng.cn}}

笔试面试时考不用中间数据交换二个数，很多人给出了

inline void Swap1（int &a, int &b）{a ^= b;b ^= a;a ^= b;}

在网上搜索下，也可以找到许多这样的写法。不过这样写存在一个隐患，如果a, b指向的是同一 个数，那么调用Swap1（）函数会使这个数为0。如:

int i = 6;Swap2（i, i）;printf（"%d %d
", i）;

当然谁都不会在程序中这样的写代码，但回到我们的Selectsort（），如果a[0]就是最小的数，那么在交换 时，将会出现将a[0]置0的情况，这种错误相信调试起来也很难发现吧，因此建议大家将交换二数的函数写成 ：

inline void Swap（int &a, int &b）{int c = a;a = b;b = c;}

或者在Swap1（）中加个判断，如果二个数据相等就不用交换了：

inline void Swap1（int &a, int &b）{if （a ！= b）{a ^= b;b ^= a;a ^= b;}}