C/C++/Java编程语言中的选择排序

在上一篇文章中，我们分析了气泡排序算法它在C程序中的实现。在本文中，我们将看到另一种排序算法，名为选择排序。就像““气泡排序”，选择排序也被认为是一种低效的排序算法。如果你想知道这个原因，请仔细阅读关于冒泡排序的文章。平均冒泡排序中涉及的比较次数是0.5*(n*n-n)。选择排序的索引也是一样的。

注:-由于该算法是在2用于循环只有这样，它才能用于任何编程语言，如C/C++或Java

让我们进入算法分析。考虑3, 4, 5、1, 2阶的数组。让我们使用选择排序算法按升序对该数组进行排序。气泡排序算法基于对数组中连续元素的重复比较，并在必要时交换元素。在选择排序上有一点不同。数组中的一个元素（通常是第一个/最后一个元素）被假定为整个数组元素的最小值/最大值。现在，将所有其他成员与该假定的最小/最大元素进行比较。根据该比较结果，在最小/最大元素和其他元素之间进行交换。

让我们通过一个例子来研究这个算法。下面给出了在C中实现选择排序的代码片段。代码使用选择排序按升序执行排序。


/*limit=数组中的元素数*/
/*min=用于保存假定最小元素的变量*/

对于（i=0；i a[j]）//使用内部FOR循环将最小元素与所有其他成员进行比较。
{
温度=a[j]；//以下3项陈述交换了要素
a[j]=a[min]；
a[分钟]=温度；
}
}
}


请参阅下面给出的两张图片。

外部FOR循环的所有四个通道如下图所示

选择排序的工作

通过解释上面给出的两幅图像&示例代码片段，您可以轻松理解选择排序的工作原理。假设第一个位置的元素为最小值。然后将其与其他元素逐一进行比较（使用第二个FOR循环）。在第一个FOR循环的第一次传递之后，整个数组的最小值（在本例中为1）被放置在数组的第一个位置。当第一个FOR循环的第二个过程开始时，假定下一个元素（即第二个元素）最小，整个过程重复。

选择排序算法也是一种低效的算法（就像气泡排序一样）。选择排序需要0.5*（n*n-n）个比较。气泡排序和选择排序所需的比较总数几乎相同。但是，选择排序所需的交换总数（在平均情况下）非常低。我们可以假设，在一般情况下，选择排序比气泡排序算法效率更高。

就像我们对Bubble排序算法做了一些改进一样，我们也可以对Selection排序算法做一些改进。您可以通过C/C中的气泡排序++文章并了解如何对算法进行修改。思考如何修改选择排序算法以获得更好的性能。