在选择排序技术中,列表分为两部分。一部分将所有元素排序,而另一部分将未排序项目。首先,我们从数组中获取最大或最小数据。获得数据(例如最小值)后,我们将列表中的第一位数据替换为最小数据,从而将其放置在列表的开头。执行后,数组变得越来越小。这样就完成了这种分类技术。
时间复杂度:O(n ^ 2)
空间复杂度:O(1)
Input: The unsorted list: 5 9 7 23 78 20 Output: Array before Sorting: 5 9 7 23 78 20 Array after Sorting: 5 7 9 20 23 78
selectionSort(array, size)
输入-数据数组,以及数组中的总数
输出-排序的数组
Begin for i := 0 to size-2 do //find minimum from ith location to size 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) { //swap the content of a and 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;//get index of minimum data for(j = i+1; j<size; j++) if(array[j] < array[imin]) imin = j; //放置在正确的位置 swap(array[i], array[imin]); } } int main() { int n; cout << "Enter the number of elements: "; cin >> n; int arr[n]; //create an array with given number of elements cout << "输入元素:" << endl; for(int i = 0; i<n; i++) { cin >> arr[i]; } cout << "Array before Sorting: "; display(arr, n); selectionSort(arr, n); cout << "Array after Sorting: "; display(arr, n); }
输出结果
Enter the number of elements: 6 输入元素: 5 9 7 23 78 20 Array before Sorting: 5 9 7 23 78 20 Array after Sorting: 5 7 9 20 23 78