Gun's Blog

DataStructure

Word count: 305Reading time: 1 min
2019/11/24 Share

选择排序算法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// TIA.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
using namespace std;
void selectSort(int a[], const int n);
int index_min(int a[], int m);
int main()
{
int array[8],length=0;
for (int i = 0; i < 8; i++)
{
cin >> array[i];
length++;
}
selectSort(array, length);
}

void selectSort(int a[], const int n)
{
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j <= n - 1; j++) {
if (a[j] < a[i]) {
int temp = a[j];
a[j] = a[i];
a[i] = temp;
}
}//循环结束时,a[i]得到的是最小的元素值
}
for(int i=0;i<n;i++)
cout << a[i]<<" ";
}

算法的时间复杂度分析:
选择排序的时间复杂度=比较时间+交换时间
比较时间:$T(n)=(n-1)+(n-2)+(n-3)+…+[n-(n-1)]=(n^2-n)/2$
交换时间:

  • 最好的情况:数组已经排好序了,此时交换时间为0;
  • 最坏情况: 数组全部逆序,此时,比较的同时也需要交换,所以与交换的次数一样。
    对交换时间取平均值,为$(n^2-n)/4$
    综上所述,根据Big O的加法原理,算法总的时间复杂度为$O(n^2)$
CATALOG