【排序算法】选择排序(C语言)
【排序算法】—— 选择排序
一、选择排序的原理
选择排序算法是通过遍历数组,选择出数组的最小或最大值,与指定位置交换数据,遍历完整个数组的所有位置就完成排序
- 遍历第一趟数组,找出数组的最小值,与第一个数据交换
- 遍历第二趟数组,继续找出最小值,与第二个数据交换
- 重复上述动作,遍历完数组就得到一个有序数组
二、选择排序的代码实现
//交换两个数据
void Swap(int* a, int* b)
{
int temp = *a;
*a = *b;
*b = temp;
}
//选择排序
void SelectSort(int* arr, int size)
{
int i = 0;
for (i = 0; i < size-1; i++)
{
int min = i;
int j = 0;
for (j = i+1; j < size; j++)
{
if (arr[j] < arr[min])
{
min = j;
}
}
Swap(&arr[i], &arr[min]);
}
}
三、选择排序的优化
1. 优化思路
以上算法是每次找出最小的放在指定位置,一共要找n-1
次,如果我们每次不但找到最小的,还找到最大的,将最小的与左端交换,最大的与右端交换,那么就少了一半的遍历次数,从而提高效率
- 变量
begin
和变量end
是数组的两端,min
和max
分别找小和大的下标
- 先交换
min
与begin
位置的数值,再交换max
与end
位置的数值
-
begin
右移,end
左移,继续找大找小,继续交换
- 重复上述操作,直到遍历完所有数组
2. 排序优化后问题
若是max
的位置与begin
重合,则begin
先与min
的位置交换,此时max
位置的最大值被交换走,导致end
与max
交换的数值是错误的
-
max
与begin
重合
-
begin
先与min
的位置交换数据,此时max
位置的已经不是最大值了
-
max
再与end
位置交换数据,排序就发生了错误
如何解决问题呢?
当max
与begin
重合时,begin
与min
交换后导致max
指向的不再是最大值,所以当我们对begin
交换后,就要对max
进行一个修正,让max
指向最大值,然后完成end
的交换
-
max
与begin
重合,并且begin
此时完成了交换,此时最大值已经交换到了min
所指向的位置
- 对
max
进行修正并完成与end
的交换
3. 优化代码的实现
//交换两个数据
void Swap(int* a, int* b)
{
int temp = *a;
*a = *b;
*b = temp;
}
//选择排序
void SelectSort(int* arr, int size)
{
int begin = 0;
int end = size - 1;
while (begin < end)
{
int max = begin;
int min = begin;
int i = 0;
for (i = begin+1; i <= end; i++)
{
if (arr[i] < arr[min])
{
min = i;
}
if (arr[i] > arr[max])
{
max = i;
}
}
Swap(&arr[begin], &arr[min]);
if (begin == max) //修正max
{
max = min;
}
Swap(&arr[end], &arr[max]);
begin++;
end--;
}
}
四、选择排序的效率
- 时间复杂度:
O
(
n
2
)
O(n^2)
- 空间复杂度:
O
(
1
)
O(1)
选择排序是不稳定的排序
选择排序是最简单的排序算法之一,最大的优点就是很好理解,但是无论排序数组是否有序,选择排序的执行次数都不发生改变,效率一直保持这比较低的水平,所以在实际应用中几乎不使用
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
二维码