C++程序选择排序

选择排序算法 通过重复从未排序的部分中找到最小元素（按升序考虑）并将其放置在开头来对数组进行排序。该算法在给定数组中维护两个子数组。

已排序的子数组。
未排序的剩余子数组。

在选择排序的每次迭代中，从未排序的子数组中选取最小元素（按升序考虑）并将其移动到已排序的子数组中。

选择排序的流程图：

C++程序选择排序

选择排序如何工作？

接下来以以下数组为例： arr[]={64，25，12，22，11}

第一次遍历：

对于已排序数组的第一个位置，从索引0到4依次遍历整个数组。遍历整个数组后，存储 64 的第一个位置，可以明确地得出 11 是最小的值。

64	25	12	22	11

因此，用11替换64。经过一次迭代，最小的值 11 刚好出现在排序列表的第一个位置。

11	25	12	22	64

第二次遍历：

对于25出现的第二个位置，再次按顺序遍历整个数组。

11	25	12	22	64

遍历后，我们发现 12 是数组中第二小的值，它应该出现在数组的第二个位置，因此交换这些值。

11	12	25	22	64

第三次遍历：

现在，对于出现 25 的第三个位置，再次依次遍历剩余的数组，并找到数组中第三个最小的值。

11	12	25	22	64

在遍历时， 22 被确定为第三小的值，它应该出现在数组的第三个位置，因此将 22 与第三个位置上的元素交换。

11	12	22	25	64

第四次遍历：

类似地，对于第4个位置，在剩余数组中找到第四小的元素。
由于 25 是第4小的值，因此它将放置在第4个位置。

11	12	22	25	64

第五次遍历：

最终，数组中最大的值会自动放置在数组的最后一个位置
结果数组是排序后的数组。

11	12	22	25	64

方法：

将最小值(min_idx)初始化为位置0
遍历数组以找到数组中的最小元素
遍历时，如果找到任何小于 min_idx 的元素，则交换这两个值
然后将min_idx增加到下一个元素处
重复直到数组排序完成

下面是上述方法的实现:

// C++ program for implementation of ;
// selection sort
#include <bits/stdc++.h>
using namespace std;
  
//Swap function
void swap(int *xp, int *yp) ;
{ 
    int temp = *xp; 
    *xp = *yp; 
    *yp = temp; 
} ;
  
void selectionSort(int arr[], int n) ;
{ 
    int i, j, min_idx; 
  
    // One by one move boundary of ;
    // unsorted subarray 
    for (i = 0; i < n-1; i++) ;
    {
        
        // Find the minimum element in ;
        // unsorted array ;
        min_idx = i; 
        for (j = i+1; j < n; j++) ;
        if (arr[j] < arr[min_idx]) ;
            min_idx = j; 
  
        // Swap the found minimum element ;
        // with the first element ;
        swap(&arr[min_idx], &arr[i]); 
    } 
} ;
  
//Function to print an array
void printArray(int arr[], int size) ;
{ 
    int i; 
    for (i=0; i < size; i++) ;
        cout << arr[i] << " "; 
    cout << endl; 
} ;
  
// Driver program to test above functions ;
int main() ;
{ 
    int arr[] = {64, 25, 12, 22, 11}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    selectionSort(arr, n); 
    cout << "Sorted array: "; 
    printArray(arr, n); 
    return 0; 
} ;```

输出：