您的位置:首页 > 科技 > 能源 > 国际新闻最新消息今天100字_公司网站开发教程_百度账号人工客服_宣传推广文案

国际新闻最新消息今天100字_公司网站开发教程_百度账号人工客服_宣传推广文案

2024/12/23 9:24:46 来源:https://blog.csdn.net/a921876874/article/details/143442919  浏览:    关键词:国际新闻最新消息今天100字_公司网站开发教程_百度账号人工客服_宣传推广文案
国际新闻最新消息今天100字_公司网站开发教程_百度账号人工客服_宣传推广文案

1、基本思想

        选择排序是一种简单直观的排序算法。它的基本思想是:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

2、算法步骤

2.1、算法步骤描述:

1. 排序前

        设定一个变量(假设为i),初始值为 0,用于标记每轮待排序序列的起始位置。假设待排序数组共有n个元素,假设为升序排序

2. 外层循环(排序轮次)

        开始一个循环,条件为 i < n - 1。这里之所以是 n - 1,是因为当进行到第 n - 1 轮排序时,只剩下最后一个元素未排序,此时整个数组实际上已经完成排序了,所以总共需要进行 n - 1 轮排序操作。

3. 内层循环(寻找每轮的最小元素)

        在每一轮排序中,首先设定一个变量 minIndex,用于记录当前轮次待排序序列中最小元素的下标,初始值设为 i(如果没有发生交换下标操作,那么i即为最小值的下标)。然后从 i +1下标位置开始,到n-1下标位置结束(即遍历当前轮次的整个待排序序列),为一个内层循环。

        内层循环将当前待排序序列的最小值放到待排序序列的起始位置(也就是已排序序列的末尾)。在这个内层循环中:对于每一个元素 arr [j](其中 j 的取值范围是从 i + 1 到 n - 1),将其与当前认定的最小元素 arr [minIndex] 进行比较。

        如果 arr [j] < arr [minIndex],则更新 minIndex 的值为 j(证明找到了一个更小的元素,要记录下这个元素的下标)。

4. 交换元素

        当内层循环结束后,就找到了当前轮次待排序序列中的最小元素,其索引为 minIndex。接下来,将找到的最小元素 arr [minIndex] 与当前轮次待排序序列的起始元素 arr [i] 进行交换(可以采用定义临时交换变量temp交换)。使得当前轮次的最小元素被放置到了已排序序列的末尾。

5. 重复上述过程, 进行多轮选择交换

        每完成一轮排序,已排序序列的长度就会加一。直到进行n-1轮排序后,已排序序列长度达到n-1,整个数组所有元素完成排序。

        总结起来,选择排序就是通过不断重复上述步骤,在每一轮从剩余的待排序元素中选择出最小元素并将其放置到已排序序列的末尾,经过 n - 1 轮操作后,实现对整个数组的排序。

2.2、选择排序算法动态演示图:

动态演示图来源网站URL:​​​​​​https://visualgo.net

3、代码实现

c语言代码实现如下:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 10
void sort(int arr[])
{int i, j;for(i = 0; i < N-1; i++){//进行排序的轮数int minIndex = i;//记录每轮中最小下标的变量for(j = i + 1; j < N; j++) {//找当前轮数待排序序列最小值的下标if(arr[minIndex] > arr[j]){minIndex = j;}}if(i != minIndex){//将最小值放到已排序序列的末尾int tmp = arr[i];arr[i] = arr[minIndex];arr[minIndex] = tmp;}}
}
int main(int argc, char *argv[])
{srand(time(NULL));int a[N];int i;puts("排序前数组为:");for(i = 0; i < N; i++){a[i] = rand()%100;//为数组随机赋值printf("%d ",a[i]);//输出排序之前数组值}puts("");sort(a);//排序puts("排序后的数组为:");for(i = 0; i < N; i++){printf("%d ",a[i]);//输出排序之后的数组值}puts("");return 0;
}

4、时间复杂度和空间复杂度

平均时间复杂度:O(n^2)

空间复杂度:O(1)

稳定性:不稳定

5、适用情况

        当对空间复杂度要求较高,即希望在原地对数据进行排序,不希望占用过多额外空间时,选择排序是一个可考虑的选择,由于其空间复杂度为O(1),不会因为排序而大量消耗额外的内存空间。

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com