选择排序概述
选择排序是一种简单的排序算法,在C语言中也常被使用。它的基本思想是每一次从待排序的元素中选出一个最小或最大的元素,放入已经排好序的元素的末尾。循环进行这个过程,直到所有的元素都排好序。
选择排序过程
第一轮排序
在第一轮排序时,假设待排序数组为arr,数组长度为n。首先,从arr[0]到arr[n-1]中选出最小的元素,假设这个元素为arr[k],将它与arr[0]交换。此时,arr[0]就是最小的元素。接下来,在剩余的arr[1]到arr[n-1]中选出最小的元素arr[k],将它与arr[1]交换。此时,arr[0]和arr[1]已经排好序了。
代码实现如下:
int i, j, k;
for (i = 0; i < n - 1; i++)
{
k = i;
for (j = i + 1; j < n; j++)
{
if (arr[j] < arr[k])
{
k = j;
}
}
if (k != i)
{
swap(arr[k], arr[i]);
}
}
上述代码中的swap函数用于交换数组中两个元素的位置。
第二轮排序
通过第一轮排序, arr[0]和arr[1]已经排好序了。接下来,在剩余的arr[2]到arr[n-1]中选出最小的元素arr[k],将它与arr[2]交换。此时,arr[0]、arr[1]和arr[2]已经排好序了。
代码实现如下:
int i, j, k;
for (i = 0; i < n - 1; i++)
{
k = i;
for (j = i + 1; j < n; j++)
{
if (arr[j] < arr[k])
{
k = j;
}
}
if (k != i)
{
swap(arr[k], arr[i]);
}
}
上述代码中的swap函数用于交换数组中两个元素的位置。
第三轮排序
通过前两轮排序, arr[0]、arr[1]和arr[2]已经排好序了。接下来,在剩余的arr[3]到arr[n-1]中选出最小的元素arr[k],将它与arr[3]交换。此时,arr[0]、arr[1]、arr[2]和arr[3]已经排好序了。
代码实现如下:
int i, j, k;
for (i = 0; i < n - 1; i++)
{
k = i;
for (j = i + 1; j < n; j++)
{
if (arr[j] < arr[k])
{
k = j;
}
}
if (k != i)
{
swap(arr[k], arr[i]);
}
}
上述代码中的swap函数用于交换数组中两个元素的位置。
第n轮排序
通过前面n-1轮排序, arr[0]到arr[n-2]已经排好序了。接下来,在剩余的arr[n-1]中选出最小的元素arr[k],将它与arr[n-1]交换。此时,arr[0]到arr[n-1]已经排好序了。
代码实现如下:
int i, j, k;
for (i = 0; i < n - 1; i++)
{
k = i;
for (j = i + 1; j < n; j++)
{
if (arr[j] < arr[k])
{
k = j;
}
}
if (k != i)
{
swap(arr[k], arr[i]);
}
}
上述代码中的swap函数用于交换数组中两个元素的位置。
选择排序的优缺点
优点
选择排序是一种简单直观的排序算法,实现简单易懂。在小规模数据排序时表现良好,排序的基本操作是比较和交换,所以性能不会差到哪里去。
缺点
选择排序的时间复杂度为O(n2),效率相对较低。在数据规模较大时,性能表现不佳。选择排序没有考虑待排序元素的初始位置,所以它并不是稳定排序算法。
总结
选择排序虽然效率不是最优,但作为算法学习的入门级算法来使用,可以很好的帮助我们理解和掌握各种排序算法的基本思想。同时,我们需要根据实际情况选择合适的排序算法。