C语言实现直接选择排序
一、直接选择排序的思路
如果从小到大排序：直接选择排序就是每一次从序列中找出一个最小（大）的数放在序列的起始位置（末尾），然后起始位置往后移一位（末尾往前移一位）。 如果从大到小排序：直接选择排序就是从每一次从序列中找出一个最大（小）的数放在序列的起始位置（末尾），然后起始位置往后移一位（末尾往前移一位）。 举个例子：玩斗地主时，一次性把牌拿起，然后把牌大的放最右边，再把次大的放在最大牌的前面，依次排序，就把牌次小到大排好了，直接选择排序就类似如此。
二、如何实现直接选择排序
这里我采用的是从小到大排序，代码如下：
#include<stdio.h>
void PrintArray(int* a, int n)//把数组中的元素打印出来
{
for (int i = 0; i < n; ++i)
{
printf("%d ", a[i]);
}
printf("
");
}
void Swap(int* p1, int* p2)//交换两个值
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
void SelectSort(int* a, int n)
{
int end = n - 1;
while (end > 0)
{
int maxi = end;
for (int i = 0; i <= end; i++)
{
if (a[i] > a[maxi])
{
maxi = i;
}
}
Swap(&a[end], &a[maxi]);//一定要传地址，不然两个值不会交换
end--;
}
}
void TestSelectSort()
{
int a[] = {
5,6,4,2,1,3,7,8,9,0 };
SelectSort(a, sizeof(a) / sizeof(int));
PrintArray(a, sizeof(a) / sizeof(int));
}
int main()
{
TestSelectSort();
return 0;
}
三、直接选择排序的优化
前面的直接选择排序一次我们只排一个数，现在我们每一次从序列中找出一个最大和最小的数，分别放在两边，这样排序就会快一些。 图解： 在最后那里我们可以看到end<begin,此时排序就结束了
代码如下：
#include<stdio.h>
void PrintArray(int* a, int n)//把数组中的元素打印出来
{
for (int i = 0; i < n; ++i)
{
printf("%d ", a[i]);
}
printf("
");
}
void Swap(int* p1, int* p2)//交换两个值
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
void SelectSort(int* a, int n)
{
int begin = 0;
int end = n - 1;
while (begin < end)
{
int mini = begin;
int maxi = end;
for (int i = begin; i <= end; i++)
{
if (a[i] < a[mini])
{
mini = i;
}
if (a[i] > a[maxi])
{
maxi = i;
}
}
Swap(&a[begin], &a[mini]);
/*当begin=maxi的时候，交换a[begin]和a[mini]
会导致a[maxi]的值发生改变*/
if (begin == maxi)
{
maxi = mini;
}
Swap(&a[maxi],&a[end]);
++begin;
--end;
}
}
}
void TestSelectSort()
{
int a[] = {
5,6,4,2,1,3,7,8,9,0 };
SelectSort(a, sizeof(a) / sizeof(int));
PrintArray(a, sizeof(a) / sizeof(int));
}
int main()
{
TestSelectSort();
return 0;
}
四、直接选择排序的时间复杂度
直接选择排序的时间复杂度没有最好和最坏的情况，不管序列是有序还是无序，它的时间复杂度都是O(N^2)，因此直接选择排序的效率比较低，使用它的时候数据规模要尽量小，否则要运行很久才会出结果。
