简单选择排序（c语言代码实现）

目录

  

选择排序：简单选择排序（不稳定的排序）

下面我们来看一下顺序存储的代码如何实现

还可以用链式存储的方法实现简单选择排序

其实每一趟排序都可以确定一个元素的最终位置，这样经过n-1次就可以使整个排序表有序

---

  选择排序：简单选择排序（不稳定的排序）

简单选择排序是一种基础的排序算法，它的基本思路是在未排序的序列中选择最小（或最大）的元素，将其与序列的第一个元素进行交换，然后在剩余的未排序序列中继续使用同样的方式进行选择和交换，直到整个序列排序完成。

以下是简单选择排序的实现过程：

1. 从序列中选择最小的元素，将其与序列的第一个元素进行交换；

2. 在剩下的未排序序列中继续进行选择，找到最小的元素，将其与序列的第二个元素进行交换；

3. 依此类推，直到整个序列排序完成

时间复杂度：O(n^2) 。

空间复杂度：O(1) 。

下面我们来看一下顺序存储的代码如何实现

void selectsort(int a[],int sz)
{
	int i = 0;
	int j = 0;
	int min = 0;
	int temp = 0;
	for (i = 1; i < sz - 1; i++)//进行sz-1趟
	{
		min = i;//记录最小元素下标
		for (j = i + 1; j < sz; j++)//在i到sz-1中选择最小元素
		{
			if (a[j] < a[min])//更新最小元素的位置
				min = j;
		}
		if (min != i)
		{
			temp = a[min];
			a[min] = a[i];
			a[i] = temp;
		}
	}
}

完整测试代码

#include<stdio.h>
void selectsort(int a[],int sz)
{
	int i = 0;
	int j = 0;
	int min = 0;
	int temp = 0;
	for (i = 1; i < sz - 1; i++)//进行sz-1趟
	{
		min = i;//记录最小元素下标
		for (j = i + 1; j < sz; j++)//在i到sz-1中选择最小元素
		{
			if (a[j] < a[min])//更新最小元素的位置
				min = j;
		}
		if (min != i)
		{
			temp = a[min];
			a[min] = a[i];
			a[i] = temp;
		}
	}
}
int main()
{
	int a[] = { 0,49,38,65,97,76,13,27 };
	int sz = sizeof(a) / sizeof(a[0]);
	int j = 0;
	printf("原始待排序的数组为：");
	for(j = 1; j < sz; j++)
		printf("%d ", a[j]);
	selectsort(a,sz);
	printf("\n简单排序后的数组为：");
	for (j = 1; j < sz; j++)
		printf("%d ", a[j]);
	return 0;
}

 

还可以用链式存储的方法实现简单选择排序

让我们来看一下代码该如何实现

void selectsort(linklist* L)
{
	lnode* p = (*L)->next, * pre = *L;
	lnode* minp = p, * minpre = pre;
	lnode* r = p;
	(*L)->next = NULL;
	lnode* s = *L;
	while (r)
	{
		minp = p = r;
		minpre = pre = NULL;
		while (p)
		{
			if (p->data < minp->data)
			{
				minp = p;
				minpre = pre;
			}
			pre = p;
			p = p->next;
		}
		if (minp == r)
			r = r->next;
		else
			minpre->next = minp->next;
		s->next = minp;
		s = minp;
	}
}

完整测试代码为

#include<stdio.h>
#include<stdlib.h>
typedef struct  lnode
{
	int data;
	struct lnode* next;
}lnode,*linklist;
int a[10] = { 2,4,5,3,1,6,9,8,7,10 };
int n = 10;
void buildlinklist(linklist* L)
{
	* L = (lnode*)malloc(sizeof(lnode));
	(*L)->next = NULL;
	lnode* s, * r = *L;
	int i = 0;
	for (i = 0; i < n; i++)
	{
		s = (lnode*)malloc(sizeof(lnode));
		s->data = a[i];
		s->next = r->next;
		r->next = s;
		r = s;
	}
	r->next = NULL;
}
void print(linklist* L)
{
	lnode* k = (*L)->next;
	while (k)
	{
		printf("%d ", k->data);
		k = k->next;
	}
}
void selectsort(linklist* L)
{
	lnode* p = (*L)->next, * pre = *L;
	lnode* minp = p, * minpre = pre;
	lnode* r = p;
	(*L)->next = NULL;
	lnode* s = *L;
	while (r)
	{
		minp = p = r;
		minpre = pre = NULL;
		while (p)
		{
			if (p->data < minp->data)
			{
				minp = p;
				minpre = pre;
			}
			pre = p;
			p = p->next;
		}
		if (minp == r)
			r = r->next;
		else
			minpre->next = minp->next;
		s->next = minp;
		s = minp;
	}
}
int main()
{
	linklist L;
	buildlinklist(&L);
	selectsort(&L);
	print(&L);
	return 0;
}

实验结果为

这里看是十次才完成简单选择排序

其实每一趟排序都可以确定一个元素的最终位置，这样经过n-1次就可以使整个排序表有序