选择排序

一：基本思想

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。

解释：就是不断的找到最小的放在最左面，然后缩短数组，继续找最小的放在最左面，最后就是一个升序数组。

二：代码

单向选择排序：

void SelectSort(int* a, int n)
{// 初始化begin为数组的第一个元素int begin = 0;// 当begin小于n-1时循环，即只要不是数组的最后一个元素，就继续排序while (begin < n - 1){// 假设当前begin位置的元素是最小的int mini = begin;// 从begin+1到数组最后一个元素之间查找真正的最小元素for (int i = begin + 1; i <= n - 1; i++){// 如果找到一个比当前假设的最小元素还要小的元素，更新mini的值if (a[i] < a[mini]){mini = i;}}// 将找到的最小元素与begin位置的元素交换Swap(&a[mini], &a[begin]);// 交换完成后，begin位置的元素已经是正确的元素，将begin向后移动一位begin++;}
}

解释：

1：n是元素的个数，n-1是元素下标的最大值，begin<n-1即代表begin最大能取到n-2，此时数组还剩2个元素，是最后一次查找，再往下一个数字不用查找了，所以begin < n - 1

2：缩短数组就是代码中的begin++，找到最小并且交换之后，begin向后移动一位，进入新一轮的查找

双向选择排序：

void SelectSort2(int* a, int n)
{// 初始化begin为数组的起始位置，end为数组的末尾位置int begin = 0;int end = n - 1;// 当begin小于end时，表示数组中还有元素未排序while (begin < end){// 初始化最小元素和最大元素的索引为beginint mini = begin;int maxi = begin;// 从begin+1到end遍历数组，寻找当前未排序部分的最小和最大元素for (int i = begin + 1; i <= end; i++){// 如果当前元素大于已知最大元素的值，更新最大元素的索引if (a[i] > a[maxi]){maxi = i;}// 如果当前元素小于已知最小元素的值，更新最小元素的索引if (a[i] < a[mini]){mini = i;}}// 将找到的最小元素交换到begin位置Swap(&a[mini], &a[begin]);// 如果最大元素的索引刚好是begin（此时begin位置的元素已经被最小元素替换了）// 那么需要更新最大元素的索引为mini（因为最小元素已经被交换到begin位置）if (maxi == begin){maxi = mini;}// 将找到的最大元素交换到end位置Swap(&a[maxi], &a[end]);// 缩小未排序部分的范围，end向左移动一位，begin向右移动一位end--;begin++;}
}

解释：

1：和第一种相比区别在于，它每次遍历数组的时候，不仅找最小，还要找最大，然后再通过交换，每次的遍历能确定两个元素的位置

2：在交换时，我们第一步Swap(&a[mini], &a[begin]);将找到的最小元素交换到begin位置，但是如果最大元素的索引刚好是begin（此时begin位置的元素已经被最小元素替换了），那么需要更新最大元素的索引为mini（因为最小元素已经被交换到begin位置），再将找到的最大元素交换到end位置才是正确的交换。

图示如下：

三：代码运行结果

对同一个十万个整形的数组进行选择排序

可以看出：两者相差不大，毕竟都是同一个量级的时间复杂度。 

四：复杂度讲解

时间复杂度：

选择排序的时间复杂度在最好、最坏和平均情况下都是O(n^2)

解释：

• 第一轮需要比较n-1次（对于n个元素的数组）。
• 第二轮需要比较n-2次。
• …
• 最后一轮需要比较1次。 因此，总的比较次数是 (n-1) + (n-2) + … + 1 = n(n-1)/2，大O表示为O(n^2)。

空间复杂度

选择排序的空间复杂度是O(1)。

选择排序是在原地进行排序的，不需要额外的存储空间来存储数据。

五：两种选择排序的对比

单向选择排序和双向选择排序的时间复杂度在理论上是相同的，都是O(n^2)。这是因为两种排序算法都需要遍历整个未排序的部分来找到最小（或最大）的元素，并且在每一轮排序中，都需要进行一定数量的比较。

具体来说：

• 单向选择排序：在每一轮排序中，算法会找到未排序部分的最小（或最大）元素，并将其放到已排序部分的末尾。每轮排序需要进行n-i次比较，其中i是当前轮次的索引（从0开始）。因此，总的比较次数是 (n-1) + (n-2) + … + 1 = n(n-1)/2，这是O(n^2)的时间复杂度。

• 双向选择排序：在每一轮排序中，算法会同时找到未排序部分的最小和最大元素，并将它们分别放到已排序部分的末尾和开始。尽管每一轮可以处理两个元素，但每轮排序仍然需要遍历整个未排序的部分，因此每轮排序的比较次数与单向选择排序相似。总的比较次数同样是O(n^2)。

虽然双向选择排序在每一轮可以减少交换次数（可能只需要两次交换，而单向选择排序可能需要一次），但是比较次数并没有减少。因此，两种算法在时间复杂度上是等价的。

需要注意的是，尽管时间复杂度相同，双向选择排序在实际执行中可能会有更好的性能，因为它减少了交换次数，而交换操作通常比比较操作更耗时。然而，这种性能提升通常不足以改变算法的时间复杂度类别。

六：代码分享

#include<stdio.h>
#include<time.h>
#include<stdlib.h>
#include<assert.h>
void PrintArray(int* a, int n)
{for (int i = 0; i < n; i++){printf("%d ", a[i]);}printf("\n");
}
void Swap(int* a, int* b)
{int tmp = *a;*a = *b;*b = tmp;
}
void SelectSort(int* a, int n)
{// 初始化begin为数组的第一个元素int begin = 0;// 当begin小于n-1时循环，即只要不是数组的最后一个元素，就继续排序while (begin < n - 1){// 假设当前begin位置的元素是最小的int mini = begin;// 从begin+1到数组最后一个元素之间查找真正的最小元素for (int i = begin + 1; i <= n - 1; i++){// 如果找到一个比当前假设的最小元素还要小的元素，更新mini的值if (a[i] < a[mini]){mini = i;}}// 将找到的最小元素与begin位置的元素交换Swap(&a[mini], &a[begin]);// 交换完成后，begin位置的元素已经是正确的元素，将begin向后移动一位begin++;}
}
void SelectSort2(int* a, int n)
{// 初始化begin为数组的起始位置，end为数组的末尾位置int begin = 0;int end = n - 1;// 当begin小于end时，表示数组中还有元素未排序while (begin < end){// 初始化最小元素和最大元素的索引为beginint mini = begin;int maxi = begin;// 从begin+1到end遍历数组，寻找当前未排序部分的最小和最大元素for (int i = begin + 1; i <= end; i++){// 如果当前元素大于已知最大元素的值，更新最大元素的索引if (a[i] > a[maxi]){maxi = i;}// 如果当前元素小于已知最小元素的值，更新最小元素的索引if (a[i] < a[mini]){mini = i;}}// 将找到的最小元素交换到begin位置Swap(&a[mini], &a[begin]);// 如果最大元素的索引刚好是begin（此时begin位置的元素已经被最小元素替换了）// 那么需要更新最大元素的索引为mini（因为最小元素已经被交换到begin位置）if (maxi == begin){maxi = mini;}// 将找到的最大元素交换到end位置Swap(&a[maxi], &a[end]);// 缩小未排序部分的范围，end向左移动一位，begin向右移动一位end--;begin++;}
}
void TestOP()
{//生成N个随机数srand(time(0));int N = 100000;int* a1 = (int*)malloc(sizeof(int) * N);int* a2 = (int*)malloc(sizeof(int) * N);assert(a1);assert(a2);for (int i = 0; i < N - 1; i++){a1[i] = rand();a2[i] = a1[i];}//clock函数计算排序函数运行的时间int begin1 = clock();SelectSort(a1, N);int end1 = clock();//clock函数计算排序函数运行的时间int begin2 = clock();SelectSort2(a2, N);int end2 = clock();printf("SelectSort:%d\n", end1 - begin1);printf("SelectSort2:%d\n", end2 - begin2);//释放空间free(a1);//释放空间free(a2);}
int main()
{//单向选择排序TestOP();return 0;
}