实现选择排序的 C++ 程序

在选择排序技术中，列表分为两部分。一方面，所有元素都已排序，另一方面，项目未排序。首先，我们从数组中取出最大或最小数据。获得数据（比如最小值）后，我们通过用最小数据替换第一位的数据将其放在列表的开头。执行后阵列越来越小。这样这个排序技术就完成了。

选择排序技术的复杂性

• 时间复杂度：O(n ² )

• 空间复杂度：O(1)

Input − The unsorted list: 5 9 7 23 78 20
Output − 排序后的数组： 5 7 9 20 23 78

算法

selectionSort(array, size)

输入：一个数据数组，以及数组中的总数

输出：排序后的数组

Begin
   for i := 0 to size-2 do //找到从第 i 个位置到大小的最小值
      iMin := i;
      for j:= i+1 to size – 1 do
         if array[j] < array[iMin] then
            iMin := j
      done
      swap array[i] with array[iMin].
   done
End

示例代码

#include<iostream>
using namespace std;
void swapping(int &a, int &b) {         //交换 a 和 b 的内容
   int temp;
   temp = a;
   a = b;
   b = temp;
}
void display(int *array, int size) {
   for(int i = 0; i<size; i++)
      cout << array[i] << " ";
   cout << endl;
}
void selectionSort(int *array, int size) {
   int i, j, imin;
   for(i = 0; i<size-1; i++) {
      imin = i;   //获取最小数据的索引
      for(j = i+1; j<size; j++)
         if(array[j] < array[imin])
            imin = j;
         //放置在正确的位置
         swap(array[i], array[imin]);
   }
}
int main() {
   int n;
   cout << "输入元素数量： ";
   cin >> n;
   int arr[n];           //创建具有给定元素数量的数组
   cout << "输入元素：" << endl;
   for(int i = 0; i<n; i++) {
      cin >> arr[i];
   }
   cout << "排序前的数组： ";
   display(arr, n);
   selectionSort(arr, n);
   cout << "排序后的数组： ";
   display(arr, n);
}

输入元素数量： 6
输入元素：
5 9 7 23 78 20
排序前的数组： 5 9 7 23 78 20
排序后的数组： 5 7 9 20 23 78