选择排序算法详解_八大排序算法图解

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全家桶1年46，售后保障稳定

选择排序就是从待排序的元素中选择最小（最大）的元素，将其放在有序序列的相应位置，使这些元素构成有序序列。选择排序主要有两种：简单选择排序和堆排序。

【简单选择排序】

编写算法，要求使用简单选择排序算法对元素65、32、71、28、83、7、53、49进行从小到大排序。

【算法思想】

简单选择排序是一种简单的选择类排序算法，它的基本思想描述如下：

假设待排序的元素有n个，在第一趟排序过程中，从n个元素序列中选择最小的元素，并将其放在元素序列的最前面，即第一个位置。在第二趟排序过程中，从剩余的n-1个元素中，选择最小的元素，将其放在第二位置。以此类推，直到没有待比较的元素，简单选择排序算法结束。

例如：

给定一组元素序列：55、33、22、66、44。简单选择排序的过程如下：

* 第一趟排序：从第1个元素开始，将第1个元素与第2个元素进行比较，因为55>33，所以33是较小的元素；继续将33与第3个元素22比较，因为33>22，所以22成为较小的元素；将22与第4个元素66比较，因为22<66，所以22仍然是比较小的一个元素；最后将22与第5个元素44比较，因为22<44，所以22就是这5个元素中最小的一个元素，并将22与第1个元素交换，此时，完成第1趟排序。第1趟排序过程如下图：

初始时，假设最小元素的下标为0。在比较过程中，用j记下最小元素的下标。经过第1趟排序后，最小的元素位于第1个位置上（处于正确的位置）。

*第二趟排序：从第2元素开始，将第2个元素与第3个元素进行比较，因为33<55，所以33是较小的元素；继续将33与第4个元素66比较，因为33<66，所以33仍然是较小的元素；将33与第5个元素44进行比较，因为33<44，所以33就是最小的元素，并将33与第2个元素进行交换，此时，完成第2趟排序。第2趟排序过程如下图。

在第2趟排序过程中，33收最小的元素，本身就在第2个位置，不需要移动元素。

*第三趟排序：从第3个元素开始，将第3个元素和第4个元素进行比较，因为55<66，所以55是较小的元素；继续将55与第5个元素44比较，因为55>44，所以44是较小的元素，并将44与第3个元素交换，此时，完成第3趟排序，过程如下：

到目前为止前三个元素都已经有序，接下来只需确定第四个元素和第五个元素的顺序即可。

*第四趟排序：比较第4个元素与第5个元素，即66与55的大小，因为66>55，所以55是较小的元素，并将66与55交换，此时，完成第4趟排序。第4趟排序过程如图所示。

此时，前4个元素都已经有序且位于正确的位置上，那么，第5个元素也位于正确的位置上。因此，整个简单选择排序结束。

【示例】

假设待排序元素有8个，分别是65、32、71、28、83、7、53、49。使用简单选择排序对该元素序列过程如图所示。

在简单选择排序过程中，如果待排序元素的个数为n，则需要n-1趟剖需要。对于第i趟排序，需要比较的次数为i-1。当第i趟排序完毕，将该趟排序过程中最小的元素放在第i个位置，此时，前i个元素都已经有序且在正确的位置上。

code:

#include<stdio.h>
void SelectSort(int a[], int n);
void DispArray(int a[], int n);
void main()
{
	int a[] = { 65,32,71,28,83,7,53,49 };
	int n = sizeof(a) / sizeof(a[0]);
	printf("排序前:\n");
	DispArray(a, n);
	SelectSort(a, n);
	printf("最终排序结果:");
	DispArray(a, n);
	getchar();
}
void SelectSort(int a[], int n)
/*简单选择排序*/
{
	int i, j, k, t;
	/*将第i个元素与第i+1...n个元素比较，将最小的的元素放在第i个位置*/
	for (i = 0; i<n - 1; i++)
	{
		j = i;
		for (k = i + 1; k<n; k++)	/*最小的元素的序号为j*/
			if (a[k]<a[j])
				j = k;
		if (j != i)			/*如果序号i不等于j，则需要将序号i和序号j的元素交换*/
		{
			t = a[i];
			a[i] = a[j];
			a[j] = t;
		}
		printf("第%d趟排序结果:", i + 1);
		DispArray(a, n);
	}
}
void DispArray(int a[], int n)
/*输出数组中的元素*/
{
	int i;
	for (i = 0; i<n; i++)
		printf("%4d", a[i]);
	printf("\n");
}

Jetbrains全家桶1年46，售后保障稳定

 result:

【主要用途】

简单选择排序算法实现简单，适用于排序元素较少且对时间要求不高的场合。

【稳定性与复杂度】

简答选择排序森一种不稳定的排序算法。在最坏的情况下，待排序的严肃序列按照非递减排列，则不要移动元素。在最坏的情况下，待排序元素按照非递增排列，则在每一趟都需要移动元素，移动元素的次数为3(n-1)。在任何情况下，简单选择排序算法都需要进行n(n-1)/2 的比较。综上，简单选择排序算法的时间复杂度是O(n^2)。简答选择排序的空间复杂度为O(1)。