排序算法之四 直接选择排序

发表于

直接选择排序和直接插入排序类似，都将数据分为有序区和无序区，所不同的是直接播放排序是将无序区的第一个元素直接插入到有序区以形成一个更大的有序区，而直接选择排序是从无序区选一个最小的元素直接放到有序区的最后。

设数组为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。排序完成。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
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]); //将这个元素放到无序区的开头  
    }  
}

在这里，要特别提醒各位注意下Swap()的实现，建议用：

1
2
3
4
5
6
inline void Swap1(int &a, int &b)  
{  
    int c = a;  
    a = b;  
    b = c;  
}

一般笔试面试时要求不能用中间数据交换二个数，可以使用以下写法：

1
2
3
4
5
6
inline void Swap2(int &a, int &b)  
{  
    a ^= b;  
    b ^= a;  
    a ^= b;  
}

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

1
2
3
int i = 6;  
Swap2(i, i);  
printf("%d %d\n", i);

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

1
2
3
4
5
6
inline void Swap1(int &a, int &b)  
{  
    int c = a;  
    a = b;  
    b = c;  
}

或者在Swap2()中加个判断，如果二个数据相等就不用交换了：

1
2
3
4
5
6
7
8
9
inline void Swap1(int &a, int &b)  
{  
    if (a != b)  
    {  
        a ^= b;  
        b ^= a;  
        a ^= b;  
    }  
}