C语言简单选择排序算法的实现

简单选择排序从元素中跳出最小关键字，将其放在已排序列的最后，未排序的序列最前，直到全部排序完成为止，其空间复杂度为O(1)，时间复杂度为O(n²)。下面是实现代码：

首先仍然是预定义和类型定义：

#define OK 1
#define ERROR 0

typedef int Status;
typedef int ElemType;

typedef struct{
	ElemType *data;
	int length;
}SqList;

顺序表的插入：

Status EnSqList(SqList *L, ElemType e,int n)
{
	if (L->length >= n)
		return ERROR;
	L->data[L->length + 1] = e;
	L->length++;
	return OK;
}

简单选择排序算法：

void SelectSort(SqList *L)
{
	int i, j, k;
	for (i = 1; i <= L->length; i++)
	{
		k = i;
		for (j = i + 1; j <= L->length; j++)
		{
			if (L->data[k]>L->data[j])
				k = j;
		}
		if (k != i)
		{
			L->data[0] = L->data[k];
			L->data[k] = L->data[i];
			L->data[i] = L->data[0];
		}
	}
}

从下标为1的元素开始，先初始化k为i，并判断之后是否存在下标为j的元素比下标k元素值小，若发现，则让k值赋值为j，继续判断直到j大于顺序表的长度(即将最小元素值的下标记下来)，然后将下标k的元素和下标i的元素交换。

加入main():

int main(void)
{
	int n, i;
	ElemType e;
	SqList L;
	L.length = 0;
	printf("输入要保存的元素个数：");
	scanf("%d", &n);
	L.data = (int *)malloc(sizeof(int)*n);
	srand((int)time(0));
	for (i = 0; i < n; i++)
	{
		e = rand();
		EnSqList(&L, e, n);
	}
	printf("排序前：");
	for (i = 1; i <= L.length; i++)
		printf("%d ", L.data[i]);
	printf("\n");
	SelectSort(&L);
	printf("排序后：");
	for (i = 1; i <= L.length; i++)
		printf("%d ", L.data[i]);
	printf("\n");
	return 0;
}