数据结构笔记 - 排序算法 简单选择排序算法

简单选择排序:

假设待排序数组长度为n,通过n-1此循环进行数组元素间的比较,每一轮中,假设该轮为第i轮,从n-i+1个元素中选出最小的,并和第i个元素进行交换。

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
33
34
#include <stdio.h>    

#define MAXSIZE 100 /* 待排序数组的大小 */

typedef struct
{
int r[MAXSIZE+1]; /* 待排序数组r,r[0]为哨兵或临时变量 */
int length; /* 待排序数组的长度,为了方便理解,不包含r[0]元素 */
}SortList;

/* 简单选择排序算法 */
void SelectSort(SortList *L)
{
int i,j,min;
int temp;
for(i=1;i<L->length;i++)
{
/* 首先设置i为当前最小下标 */
min = i;
/* 循环之后的数据和选定的r[min]比较 */
for (j = i+1;j<=L->length;j++)
{
/* 发现更小的元素,把对应的下标赋给min */
if (L->r[min]>L->r[j])
min = j;
}
if(i!=min){
/* 交换r[i]与r[min]的值 */
temp=L->r[i];
L->r[i]=L->r[min];
L->r[min]=temp;
}
}
}

简单选择排序的时间复杂度分析:

相比于冒泡排序算法,由于选择排序每次寻找最小元素使用的是数组下标作为标记,直到最后才进行交换移动的,所以减少了交换的次数。

需要的比较次数是固定的:n-1+n-2+n-3+…+1=n(n-1)/2次。

需要的交换次数:最好情况下为0此,最差情况下需要交换n-1次,总得时间复杂度为O(n^2)。

随意时间复杂度与冒泡排序相同,但是简单选择排序的性能还是要比冒泡排序好一点。

arthinking wechat
欢迎关注itzhai公众号