首页 > 编程笔记 > C++笔记

选择排序（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，它保存了数组元素的下标，该下标所代表的元素将在排序时接收其正确的值：

第一趟排序时，startScan 取值为 0，在找到最小值之后，最小值所在位置和 Element 0 位置进行值的交换，Element 0 获得了最小值。
在第二趟排序时，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

选择排序（C++）算法（超详细）

所有教程

优秀文章