简单选择排序,任意输入n个数，按由小到大的顺序排列并显示输出。（排序算法--选择法排序）

简单选择排序,任意输入n个数，按由小到大的顺序排列并显示输出。（排序算法--选择法排序）详细介绍

本文目录一览： 选择排序

选择排序（Selection sort）是一种简单直观的排序算法。
它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。
选择排序的时间复杂度：
选择排序的交换操作介于 0 和 (n - 1)次之间。选择排序的比较操作为 n (n - 1） / 2 次之间。选择排序的赋值操作介于 0 和 3 (n - 1） 次之间。比较次数O(n^2），比较次数与关键字的初始状态无关，总的比较次数N=(n-1）+(n-2）+...+1=n*(n-1）/2。
交换次数O(n），最好情况是，已经有序，交换0次；最坏情况交换n-1次，逆序交换n/2次。交换次数比冒泡排序少多了，由于交换所需CPU时间比比较所需的CPU时间多，n值较小时，选择排序比冒泡排序快。

选择排序 和 简单选择排序 有什么区别？（C语言）

选择排序有很多种，简单选择排序只是其中一种：
1、简单选择排序
一般分为多趟，每一趟从待排数据中选出最小（或最大）的一个元素，顺序放在已排好序的
数列的最后
2、树形选择排序
对n个记录的关键字进行两两比较，然后在n/2个较小者之间再进行两两比较，如此重复，直
至选出最小的记录为止，又称锦标赛排序
3、堆排序
分大根堆和小根堆，大根堆（或小根堆）堆顶记录的关键字最大（或最小）
选择排序
每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。
选择排序是不稳定的排序方法。
冒泡排序：
冒泡排序（bubblesort）的基本概念是：依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的数放到了最后。在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。如此下去，重复以上过程，直至最终完成排序。

选择排序法的基本思想

选择排序的基本思想是：每一趟在n-i+1（i=1，2，…n-1）个记录中选取关键字最小的记录作为有序序列中第i个记录。基于此思想的算法主要有简单选择排序、树型选择排序和堆排序。简单选择排序的基本思想：第1趟，在待排序记录r[1]~r[n]中选出最小的记录，将它与r[1]交换；第2趟，在待排序记录r[2]~r[n]中选出最小的记录，将它与r[2]交换；以此类推，第i趟在待排序记录r[i]~r[n]中选出最小的记录，将它与r[i]交换，使有序序列不断增长直到全部排序完毕。以下为简单选择排序的存储状态，其中大括号内为无序区，大括号外为有序序列：初始序列：{ 49 27 65 97 76 12 38 }第1趟：12与49交换：12 { 27 65 97 76 49 38 }第2趟：27不动　：12 27 { 65 97 76 49 38 }第3趟：65与38交换：12 27 38 { 97 76 65 49}第4趟：97与49交换：12 27 38 49 { 97 76 65 }第5趟：76与65交换：12 27 38 49 65 { 97 76 }第6趟：97与76交换：12 27 38 49 65 76 97 完成简单选择排序的算法具体描述如下：void SelectSort(RecordType r[], int length)　/*对记录数组r做简单选择排序，length为待排序记录的个数*/{int temp;for ( i=0 ; i< length-1 ; i++) //n-1趟排序{int index=i；　//假设index处对应的数组元素是最小的for ( j=i+1 ; j < length ; j++) 　//查找最小记录的位置if (r[j].key < r[index].key )index=j；if ( index!=i) 　//若无序区第一个元素不是无序区中最小元素，则进行交换{ temp= r[i]； r[i]= r[index]； r[index]=temp; }　//利用temp作为临时空间，两个值交换的桥梁}}

任意输入n个数，按由小到大的顺序排列并显示输出。（排序算法--选择法排序）

c语言的算法 先输入n（问题的规模） 再输入n个数#include

void main()

{int min,a[100],i,j,n,temp;

scanf("%d",&n); （输入排序数字数量）

for(i=0;i
<n;i++)
scanf("%d",&a[i]); （输入参与排序的数）

for(i=0;i
<n-1;i++) （n-1次筛选）
{min=i;

for(j=i+1;j
<n;j++) （每次选出最小的数与第i个数交换）
if(a[j]
<a[min]) min="j;
temp=a[i];a[i]=a[min];a[min]=temp;

}

for(i=0;i
<n;i++)
printf("%d ",a[i]); （输出排好的序）

}

思路：将数组中第一个元素的值与其后的所有元素的值进行比较，如果前者大于后者就互换，这样将所有元素中最小值就放在第一一个元素中。依次类推，直到最后一个元素为止。那么具体代码显示如下：

#include

#define n 5 /*对5个数按升序排列

main(){

int a[n],i,j, t;

printf(" input 5 number\n");

for(i=0;i
<n- 1;i++)
for(j=i+1;j
<n;j++)
if(a[i]>a[j]) {

t=a[j];

a[j]=a[i];

a[i]=t；

}

具体运行结果如下：

扩展资料：

简单选择排序的基本思想：

第1趟，在待排序记录r[1]~r[n]中选出最小的记录，将它与r[1]交换；第2趟，在待排序记r[2]~r[n]中选出最小的记录，将它与r[2]交换；以此类推，第i趟在待排序记录r[i]~r[n]中选出最小的记录，将它与r[i]交换，使有序序列不断增长直到全部排序完毕。

以下为简单选择排序的存储状态，其中大括号内为无序区，大括号外为有序序列：

初始序列：{49 27 65 97 76 12 38}

第1趟：12与49交换：12{27 65 97 76 49 38}第2趟：27不动　：12 27{65 97 76 49 38}第3趟：65与38交换：12 27 38{97 76 49 65}第4趟：97与49交换：12 27 38 49{76 97 65}第5趟：76与65交换：12 27 38 49 65{97 76}第6趟：97与76交换：12 27 38 49 65 76 97 完成
</n;j++)

</n;i++)

</n;i++)

选择排序法的算法

简单选择排序算法分析：在简单选择排序过程中，所需移动记录的次数比较少。最好情况下，即待排序记录初始状态就已经是正序排列了，则不需要移动记录。最坏情况下，需要移动记录的次数最多为3（n-1）（此情况中待排序记录并非完全逆序，给完全逆序记录排序的移动次数应为(n/2)*3，其中n/2向下取整）。简单选择排序过程中需要进行的比较次数与初始状态下待排序的记录序列的排列情况无关。当i=1时，需进行n-1次比较；当i=2时，需进行n-2次比较；依次类推，共需要进行的比较次数是∑ =(n-1)+(n-2)+…+2+1=n(n-1)/2，即进行比较操作的时间复杂度为O(n2)。选择排序法 是对 定位比较交换法（也就是冒泡排序法） 的一种改进。在讲选择排序法之前我们先来了解一下定位比较交换法。为了便于理解，设有10个数分别存在数组元素a[0]～a[9]中。定位比较交换法是由大到小依次定位a[0]～a[9]中恰当的值（和武林大会中的比武差不多），a[9]中放的自然是最小的数。如定位a[0],先假定a[0]中当前值是最大数，a[0]与后面的元素一一比较，如果a[4]更大，则将a[0]、a[4]交换，a[0]已更新再与后面的a[5]～a[9]比较，如果a[8]还要大，则将a[0]、a[8]交换，a[0]又是新数，再与a[9]比较。一轮比完以后，a[0]就是最大的数了，本次比武的武状元诞生了，接下来从a[1]开始，因为状元要休息了，再来一轮a[1]就是次大的数，也就是榜眼，然后从a[2]开始，比出探花，真成比武大会了，当比到a[8]以后，排序就完成了。下面给大家一个例子：int main(void){int a[10];int i,j,t;for ( i = 0; i < 10; i ++ ) scanf("%d",&a[ i ]); /*输入10个数，比武报名，报名费用10000￥ ^_^*/for ( i = 0; i < 9; i ++ )for ( j = i + 1; j < 10; j ++)if ( a[ i ] < a[ j ] ) { t = a[ i ]; a[ i ] = a[ j ]; a[ j ] = t; } /*打不过就要让出头把交椅，不过a[ i ]比较爱面子，不好意思见 a[ j ]，让t帮忙*/for( i = 0; i < 10; i ++) printf("%4d",a[ i ]); /*显示排序后的结果*/return 0;}好啦，啰嗦了半天总算把定位比较排序法讲完了，这个方法不错，容易理解，就是有点麻烦，一把椅子换来换去，哎～所以就有了下面的选择排序法，开始的时候椅子谁也不给，放在一边让大家看着，找个人k记录比赛结果，然后发椅子。具体来讲呢就是，改进定位比较排序法，但是这个改进只是一部分，比较的次数没变，该怎么打还是怎么打，就是不用换椅子了。每次外循环先将定位元素的小标i值记录到K，认为a[k]是最大元素其实k=i还是a[ i ]最大，a[k]与后面的元素一一比较，该交换的也交换，就是把K的值改变一下就完了，最后在把a[k]与a[ i ]交换，这样a就是最大的元素了。然后进入下一轮的比较。选择排序法与定位比较排序法相比较，比的次数没变，交换的次数减少了。下面也写个例子：由大到小时：int main(void){int a[10];int i,j,t,k;for ( i = 0; i < 10; i ++ ) scanf("%d",&a[ i ]); /*输入10个数，比武报名，报名费用10000￥ ^_^*/for ( i = 0;i < 9;i ++ ) /*10个数，所以只需比9次*/{k = i; /*裁判AND记者实时追踪报道比赛情况*/for ( j = i + 1; j < 10; j ++)if ( a[ k ] < a[ j ] ) k = j; /*使a[k]始终表示已比较的数中的最大数*/if （k！=i）{ t = a[ i ]; a[ i ] = a[ k ]; a[ k ] = t;} /* t 发放奖品* /}for( i = 0; i < 10; i ++) printf("%4d",a[ i ]); /*显示排序后的结果*/return 0;}由小到大时：int main(void){int a[10];int i,j,t,k;for ( i = 0; i < 10; i ++ ) scanf("%d",&a[ i ]); /*输入10个数，比武报名，报名费用10000￥ ^_^*/for ( i = 0; i < 9; i ++ ){k = i; /*裁判AND记者实时追踪报道比赛情况*/for ( j = i + 1; j < 10; j ++)if ( a[ k ] > a[ j ] ) k = j;if （k！=i）{ t = a[ i ]; a[ i ] = a[ k ]; a[ k ] = t; }/* t 发放奖品*/}for( i = 9; i >= 0; i --) printf("%4d",a[ i ]); /*显示排序后的结果*/return 0;}java选择排序法代码　public static void main(String[] args) {Random random=new Random();int[] pData=new int[10];for(int i=0;i
<pdata.length;i++){ 随机生成10个排序数integer a="pData[j];pData[j]=pData[i];pData[i]=a;}}}return" a;system.out.print(pdata[i]+" ");}system.out.println();pdata="Choose(pData);for(int" i ");}system.out.println();}public static int[] choose(int[] pdata){system.out.println();for (int < pdata.length; i++) {for j j++) {if(pdata[j]<pdata[i]){int pdata;}

选择排序法

常用的选择排序方法有两种： 直接选择排序 和 堆排序 。 直接排序简单直观，但性能略差； 堆排序是一种较为高效的选择排序方法，但实现起来略微复杂。
直接选择排序的思路很简单，它需要经过n-1趟比较。
直接选择排序的优点是算法简单，容易实现。 直接选择排序的缺点是每趟只能确定一个元素，n个数组需要进行n-1趟比较。
封装的实体类
具体的算法与测试
假设有n个数据元素的序列k0，k1，…，kn-1，当且仅当满足如下关系时，可以将这组数据称为小顶堆（小根堆）。 ki <= k2i+1且ki <= k2i+2（其中i=0, 2,…，(n-1)/2） 或者，满足如下关系时，可以将这组数据称为大顶堆（大根堆）。 ki >= k2i+1且ki >=k2i+2（其中i=0, 2,…，(n-1)/2） 对于满足小顶堆的数据序列k0，k1，…，kn-1，如果将它们顺序排成一棵完全二叉树，则此树的特点是：树中所有节点的值都小于其左右子节点的值，此树的根节点的值必然最小。反之，对于满足大顶堆的数据序列k0，k1，…，kn-1，如果将它们顺序排成一棵完全二叉树，则此树的特点是：树中所有节点的值都大于其左右子节点的值，此树的根节点的值必然最大。 通过上面介绍不难发现一点，小顶堆的仁义子树也是小顶堆，大顶堆的任意子树还是大顶堆
例：判断数据序列 9,30,49,46,58,79是否为堆，将其转换为一个完全二叉树
判断数据序列：93,82,76,63,58,67,55是否为堆，将其转换为一个完全二叉树
堆排序的关键在于建堆，它按如下步骤完成排序。
通过上面介绍不难发现，堆排序的步骤就是重复执行以下2步。 （1）建堆； （2）拿堆的根节点和最后一个节点交换。 由此可见，对于包含n个数据元素的数据组而言，堆排序需要经过n-1次建堆，每次建堆的作用就是选出该堆的最大值或最小值。因为堆排序的本质上依然是一种选择排序。
例如如下数据组： 9，79，46，30，58，49 建堆过程
具体算法

选择法排序

选择法排序是一种简单的容易实现的对数据排序的算法，以整形数组元素为例，有数组A[10]，即A[0]，A[1]…A[8]，A[9]（假设其元素均互不相同），要求对其元素排序使之递增有序。
首先以一个元素为基准，从一个方向开始扫描，比如从左至右扫描，以A[0]为基准，接下来从A[0]…A[9]中找出最小的元素，将其与A[0]交换。
C语言选择排序详解
工作原理是每一次从无序组的数据元素中选出最小（或最大）的一个元素，存放在无序组的起始位置，无序组元素减少，有序组元素增加，直到全部待排序的数据元素排完。
以升序为例的图解：
代码：
#include

void SelectionSort(int *num,int n)

{

int i = 0;

int min = 0;

int j = 0;

int tmp = 0;

for(i = 0;i < n-1;i++)

{

min = i;//每次讲min置成无序组起始位置元素下标。

for(j = i;j < n;j++)//遍历无序组，找到最小元素。

{

if(num[min]>num[j])

{

min = j;

}

}

if(min != i)//如果最小元素不是无序组起始位置元素，则与起始元素交换位置。

{

tmp = num[min];

num[min] = num[i];

num[i] = tmp;

}

}

}

（此处空一行）

int main()

{

int num[6] = {5,4,3,2,9,1};

int i = 0;

SelectionSort(num,6);//这里需要将数列元素个数传入，有心者可用sizeof在函数内求得元素个数。

for(i = 0;i < 6;i++)

{

printf("%d ",num[i]);

}

return 0;

}

为什么简单选择排序所需移动的最坏情况下为3（n-1），急求，有没有大神……

n个元素进行简单选择排序，每一轮从未排序的序列中找到最小的，和未排序序列第一个元素交换，注意这里是直接交换，通过辅助变量移动三次。一共要进行n-1轮上述的交换过程
满意回答
第1趟：首先选出最小的1和排在第一位的4交换
第2趟：选出次小的2和排在剩下来的第一位的3交换
第3趟：选出剩下最小的3，原地不交换
这个3的意思就是交换一次需要用中间变量，结果是记录移动3次
最坏时，每一趟都要交换，排序共n-1趟，因此移动最多3(n-1)次，你的4321就没有这么多

采用简单选择排序算法，将数组中n个元素（52、49、80、36、14、58、61、23）由小到大进行排序。

【答案】：数组采用简单选择排序算法的排序过程如下：
（52、49、80、36、14、58、61、23）
（14、49、80、36、52、58、61、23）
（14、23、80、36、52、58、61、49）
（14、23、36、80、52、58、61、49）
（14、23、36、49、52、58、61、80）
解析：简单选择排序的处理流程如下：
(1)从待排序序列中，找到关键字最小的元素；
(2)如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换；
(3)从余下的N-1个元素中，找出关键字最小的元素，重复(1)、(2)步，直到排序结束。
本题可以根据这个原则求出排序的过程。