选择排序 O(n^2)
程序员文章站
2022-05-05 17:38:44
...
文章目录
一、选择排序流程
(1)首先从原始数组中选择最小/最大的1个数据,将其和位于第1个位置的数据交换。
(2)接着从剩下的n-1个数据中选择次小/次大的1个元素,将其和第2个位置的数据交换
(3)然后,这样不断重复,直到最后两个数据完成交换。最后,便完成了对原始数组的从小到大/从大到小的排序。
eg.a[3]={4,5,1},
现在进行选择排序
首先:找出a中最大值5,将a[1]与a[0]互换 得到{5,4,1}
其次:找出a[1]-a[2]中剩余数据最大值4,不交换
结束
对于长度为n的数组,第一次取最值遍历n次,第二次遍历n-1次……最后一次。共计(n+1)*n/2次,因此时间复杂度为O(n^2)。
二、选择排序示例代码
#include<iostream>
using namespace std;
#define N 10
void Select_Sort(int* arr, int n) //arr为数据数组,n为数组长度
{
for (int i = 0; i < n-1; i++)
{
int min = i;
for (int j = i; j < n; j++)
{
if (arr[min] > arr[j])
{
min = j;
}
}
if (min != i)
{
swap(arr[i], arr[min]);
}
}
}
int main()
{
int arr[N]= { 1,4,6,3,0,2,5,9,8,7 };
Select_Sort(arr, 10);
for (int i = 0; i < N; i++)
{
cout << arr[i] << ",";
}
cout << endl;
return 0;
}