大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新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");
}
result:
【主要用途】
简单选择排序算法实现简单，适用于排序元素较少且对时间要求不高的场合。
【稳定性与复杂度】
简答选择排序森一种不稳定的排序算法。在最坏的情况下，待排序的严肃序列按照非递减排列，则不要移动元素。在最坏的情况下，待排序元素按照非递增排列，则在每一趟都需要移动元素，移动元素的次数为3(n-1)。在任何情况下，简单选择排序算法都需要进行n(n-1)/2 的比较。综上，简单选择排序算法的时间复杂度是O(n^2)。简答选择排序的空间复杂度为O(1)。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/219177.html原文链接：https://javaforall.net
