选择排序(C++)算法(超详细)

冒泡排序在处理大型数组时的效率不够理想,因为经常需要重复的数据交换来将单个项目放置到正确的位置。选择排序和冒泡排序一样,每趟只放置一个项目到正确的位置。但是,通常情况下它执行的交换会比较少,因为它会立即将项目移动到数组中正确的位置。

像任何其他排序一样,选择排序可以按照升序或降序的方式修改排序。按升序排序的方法如下:数组中最小的值被定位并移动到 Element 0,然后定位下一个最小值并移动到 Element 1,这个过程一直持续到所有元素都按照正确的顺序排列。

现在来看一看在排列下面数组的元素时,选择排序是如何工作的:


选择排序从 Element 0 开始扫描数组,并找到最小值的元素。这个元素的内容然后与 Element 0 的内容交换。在该示例中,Element 5 中存储的 1 是最小的值,所以它与存储在 Element 0 中的 5 交换。这完成了第一趟,现在的数组显示如下:


该算法然后重复该过程,但是因为 Element 0 已经包含数组中的最小值,所以可以将其排除在过程之外。接下来进行第二趟,算法在 Element 1 处开始扫描。它在数组的未排序部分中查找最小值,结果找到了 Element 2 中的 2。因此,Element 2 与 Element 1 交换。数组现在显示如下:


再次重复这个过程,但是这次扫描从 Element 2 开始。算法将发现 Element 5 包含下一个最小值,于是将该元素的内容与 Element 2 的内容交换,导致数组显示如下:


 
接下来,扫描从 Element 3 开始。其内容与 Element 5 的内容交换,导致数组显示如下:


 
到现在这个阶段,只剩下两个元素需要排序。选择排序算法发现 Element 5 的值小于 Element 4 的值,所以两者交换。于是数组完成了最终的排列:


以下是选择排序算法的伪代码:
For startScan = 0 to the next-to-last array subscript
    Set index to startScan
    Set minIndex to startScan
    Set minValue to array[startScan]
    For index = (startScan + 1) to the last subscript in the array
        If array[index] is less than minValue
            Set minValue to array[index]
            Set minIndex to index
        End If
        Increment index
    End For
    Set array[minIndex] to array[startScan]
    Set array[startScan] to minValue
End For
与冒泡排序一样,选择排序使用一对嵌套循环,在这个例子中是两个 for 循环

外循环在每一趟排序时迭代一次。其循环控制变量是 startScan,它保存了数组元素的下标,该下标所代表的元素将在排序时接收其正确的值:
  1. 第一趟排序时,startScan 取值为 0,在找到最小值之后,最小值所在位置和 Element 0 位置进行值的交换,Element 0 获得了最小值。
  2. 在第二趟排序时,startScan 取值为 1,在剩下的值中寻找最小值,找到之后即和 Element 1 位置进行值的交换。

这个过程不断进行,直到从 Element 0 位置到倒数第 2 个位置的元素都已经获得了正确的值。一旦该过程完成,则数组最后一个元素的值自然也是最大值,于是就不需要外部循环再次迭代了。由此可见,如果数组中有 N 个数据,则意味着需要迭代 N-1 趟。

每一趟排序过程中,内部循环的任务是查找最小值,以便与 startScan 位置中的值进行交换。在迭代开始之前,minIndex 被设置为 startScan,并且 minValue 被设置为 startScan 位置中的当前值。内部循环然后从 startScan+1 的下标位置开始查找数组中剩余的值。如果它发现一个值要小于当前存储在 minValue 中的值,则使用这个新的更小的值取代 minValue 中原有的值,并且使用新最小值所在的下标取代 minIndex 中存储的下标。

一旦内部循环完成其迭代,则 minIndex 将保存最小元素的下标索引,然后外部循环就会将该元素的内容和 array[startScan] 的内容交换,并且使 startScan 递增 1。请注意,如果未发现比 startScan 位置的值更小的元素,则 minIndex 仍将等于 startScan,那么 startScan 位置中的值就会和它自己交换,实际上就是保持不变。

以下函数使用了选择排序方法,以升序方式排列整数数组中的值。它接收两个参数。第一个形参 array 接收要排序的数组,第二个形参 size 则指示数组中存储了多少个值。
void selectionSort (int array[], int size)
{
    int startScan, minIndex, minValue;
    for (startScan = 0; startScan < (size - 1); startScan++)
    {
        minIndex = startScan;
        minValue = array[startScan];
        for (int index = startScan + 1; index < size; index++)
        {
            if (array[index] < minValue)
            {
                minValue = array[index];
                minIndex = index;
            }
        }
        array[minIndex] = array[startScan];
        array[startScan] = minValue;
    }
}
如前所述,选择排序需要交换的次数要少于冒泡排序。事实上,正如上例所示,它每一趟只需要交换一个数据。外部循环的每一次迭代都可以将一个值放置到正确的位置,不仅如此,己经正确的值和数组位置在后面的排序中还无须再次检测。

但是,值得注意的是,选择排序不使用标记变量(冒泡排序中的 madeAswap 就是一个标记变量)。这是因为,即使某个数组位置已经保存了下一个最小的值,从而导致它的值在下一趟排序过程中不会改变,但这并不意味着数组已经完成排序,因为其他值可能尚未移动到它们的正确位置。

下面的程序演示了选择排序函数的用法:
//This program uses the selection sort algorithm to sort an array in ascending order.
#include <iostream>
using namespace std;
//Function prototypes
void selectionSort (int [], int);
void showArray(const int [], int);

int main()
{
    const int SIZE = 6;
    // Array of unsorted values
    int values[SIZE] = {5, 7, 2, 8, 9, 1};
    // Display the values
    cout << "The unsorted values are\n";
    showArray(values, SIZE);
    //Sort the array
    selectionSort(values, SIZE);
    // Display the values again
    cout << "The sorted values are\n";
    showArray(values, SIZE);
    return 0;
}
void selectionSort(int array[], int size)
{
    int startScan, minIndex, minValue;
    for (startScan = 0; startScan < (size - 1); startScan++)
    {
        minIndex = startScan;
        minValue = array[startScan];
        for(int index = startScan + 1; index < size; index++)
        {
            if (array[index] < minValue)
            {
                minValue = array[index];
                minIndex = index;
            }
        }
        array[minIndex] = array[startScan];
        array[startScan] = minValue;
    }
}
void showArray(const int array[], int size)
{
    for (int count = 0; count < size; count++)
        cout << array [count] << " ";
    cout << endl;
}
程序输出结果:

The unsorted values are
5 7 2 8 9 1
The sorted values are
1 2 5 7 8 9