欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

选择排序 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;
}

三、附录 其他排序

十大经典算法复杂度及稳定性比较
冒泡排序
插入排序
快速排序
归并排序
堆排序
基数排序
计数排序

参考:
https://blog.csdn.net/alzzw/article/details/98100378