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

简单选择排序：

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

#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)。

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