实例说明
用直接选择排序方法对数组进行排序。
实例解析
选择排序( Selection Sort )的基本思想是:每趟从待排序的记录中选出关键字最小的记录,顺序放在已排好序的子文件的最后,直到全部记录排序完毕。
常用的选择排序方法有直接选择排序和堆排序。
直接选择排序( Straight Selection Sort )
直接选择排序的基本思想是 n 个记录的文件的直接选择排序可经过 n-1 趟直接选择排序得到有序结果。
① 初始状态:无序区为 R[1..n] ,有序区为空。
② 第 1 趟排序
在无序区 R[1..n] 中选出关键字最小的记录 R[k], 将它与无序区的第 1 个记录 R[1] 交换,使 R[1..1] 和 R[2..n] 分别变为记录个数增加 1 个的新有序区和记录个数减少 1 个的新无序区。
③ 第 I 趟排序
第 I 趟排序开始时,当前有序区和无序区分别为 R[1..i-1] 和 R[i..n](1 ≤ I ≤ n-1) 。该趟排序从当前无序区中选出关键字最小的记录 R[k], 将它与无序区的第 1 个记录 R[i] 交换,使 R[1..i] 和 R[i+1..n] 分别变为记录个数增加 1 个的新有序区和记录个数减少 1 个的新无序区。
这样, n 个记录的文件的直接选择排序即可经过 n-1 趟直接选择排序得到有序结果。
直接选择排序的具体算法如下:
void SelectSort(SeqList R){
int I,j,k;
for(i=1;i<n;i++){ // 做第 I 趟排序 (1 ≤ I ≤ n-1)
k=I;
for(j=i+1;j<=n;j++) // 在当前无序区 R[i..n] 中选 key 最小的记录 R[k]
if(R[j].key<R[k].key)
k=j; // k 记下目前找到的最小关键字所在的位置
if(k!=i){ // 交换 R[i] 和 R[k]
R[0]=R[i];R[i]=R[k];R[k]=R[0]; // R[0] 做暂存单元
}//endif
}//endfor
}//SelectSort
程序代码—直接选择排序
#include <stdio.h>
#define MAX 255
int R[MAX];
void Select_Sort(int n){
int i,j,k;
for(i=1;i<n;i++){ /* 做第 I 趟排序 (1 ≤ I ≤ n-1) */
k=i;
for(j=i+1;j<=n;j++) /*在当前无序区R[i..n] 中选 key 最小的记录 R[k] */
if(R[j]<R[k])
k=j; /* k 记下目前找到的最小关键字所在的位置 */
if(k!=i){ /* 交换 R[i] 和 R[k] */
R[0]=R[i];R[i]=R[k];R[k]=R[0]; /* R[0] 做暂存单元 */
}/* endif */
}/* endfor */
}/* end of Select_Sort */
void main(){
int i,n;
clrscr();
puts("Please input total element number of the sequence:");
scanf("%d",&n);
if(n<=0 || n>MAX){
printf("n must more than 0 and less than %d.\n",MAX);
exit(0);
}
puts("Please input the elements one by one:");
for(i=1;i<=n;i++)
scanf("%d",&R[i]);
puts("The sequence you input is:");
for(i=1;i<=n;i++)
printf("%4d",R[i]);
Select_Sort(n);
puts("\nThe sequence after select_sort is:");
for(i=1;i<=n;i++)
printf("%4d",R[i]);
puts("\n Press any key to quit…");
getch();
}
归纳注释
关键字比较次数:无论文件初始状态如何,在第 I 趟排序中选出最小关键字的记录,需做 n-I 次比较,因此,总的比较次数为 n(n-1)/2=O(n^2 )。
记录的移动次数:当初始文件为正序时,移动次数为 0。文件初态为反序时,每趟排序均要执行交换操作,总的移动次数取最大值 3(n-1)。直接选择排序的平均时间复杂度为 O(n^2 )。
直接选择排序是一个就地排序。
稳定性分析:直接选择排序是不稳定的,反例比如 [2,2,1]。
分享到:
相关推荐
这三份C语言程序示例可以帮助读者深入理解这些排序算法的实现细节。在实际编程中,了解不同排序算法的优缺点和适用场景,能够帮助我们选择最适合的排序方法,提高程序性能。例如,快速排序通常在大多数情况下表现...
本篇将深入探讨七种常见的VB排序算法示例程序,它们包括:冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序和希尔排序。 1. 冒泡排序(Bubble Sort) 冒泡排序是最基础的排序算法之一,通过不断交换相邻...
通过上述代码示例,我们可以清楚地了解到选择排序算法的基本原理及其在 C++ 中的具体实现方式。此外,该程序还提供了交互式的输出功能,帮助用户更好地理解排序过程中每一步的变化情况,这对于教学和学习都非常有...
在编程领域,排序算法是计算机科学中的一个基本概念,它涉及到如何有效地重新排列一组数据,使其按照特定的顺序(如升序或降序)进行排列。...通过阅读和分析`choice.cpp`,我们可以深入学习C++编程和排序算法。
题目中的代码示例分别实现了两种不同的选择排序算法,并对一个包含12个整数的数组进行了排序。我们可以看到,在主函数`main()`中,首先定义了一个数组`a`,然后计算出数组的长度`n`,接着调用排序函数`exchange_sort...
通过分析和实践冒泡排序和选择排序的代码,可以深入了解它们的工作原理,从而更好地选择和优化排序算法。同时,结合不同数据集运行这些示例代码,可以加深对排序过程和性能差异的理解。在实际开发中,开发者应根据...
本书“数据结构与算法分析_Java语言及示例”提供了详细且直观的解释,通过Java语言来阐述这些概念,使得学习过程更为易懂。 首先,我们要了解数据结构。数据结构是组织和存储数据的方式,它决定了我们如何在计算机...
在压缩包文件“VB2010-02-02-如何实现排序算法”中,你可能找到了各个排序算法的VB6.0源代码示例,这些示例可以帮助你理解每种算法的工作原理,并且可以作为学习和参考的起点。通过阅读和分析这些代码,你可以掌握...
《算法分析与设计一书源程序》是由著名计算机科学家陈慧南编著的,这本书深入浅出地探讨了算法的设计技巧、分析方法以及其在实际问题中的应用。源程序是作者为了帮助读者更好地理解和实践书中理论而提供的实际代码...
以下是对标题"《C语言经典排序算法及举例》"中涉及的排序算法进行的详细解释: 1. **冒泡排序**: 冒泡排序是最基础的排序算法之一,它通过重复遍历待排序的数组,依次比较相邻元素并交换顺序,使较大的元素逐渐...
#### 三、排序算法分析 **1. 基本操作** - **关键字比较**:几乎所有排序算法都需要进行关键字之间的比较,这是排序的基本操作之一。 - **记录移动**:除了关键字比较外,还需要移动记录来实现排序。对于顺序存储...
本次实验的主要目的是通过实际操作来比较六种常用的内部排序算法(起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序)在处理随机数据时的关键字比较次数和关键字移动次数,以便直观地了解每种算法...
总的来说,这个"插入排序算法C语言程序"项目提供了一个实践插入排序算法的机会,可以帮助开发者加深对排序算法的理解,尤其是在C语言环境下如何实现和优化排序算法。通过分析和运行代码,可以更好地掌握插入排序的...
### 排序算法实现及比较 #### 冒泡排序 - **原理**:通过重复地遍历列表,比较每对相邻项并交换顺序错误的项。 - **实现步骤**: - 遍历整个数组,比较相邻的元素。 - 如果第一个元素大于第二个元素,则交换它们...
在实际开发中,了解并熟练掌握这些排序算法对于优化程序性能、解决复杂问题具有重要意义。例如,当需要处理大量数据时,选择效率更高的排序算法可以显著减少计算时间和资源消耗。此外,理解排序算法也能帮助开发者在...
这个压缩包中的文档很可能会详细解释每种排序算法的步骤、伪代码、示例代码以及性能分析,帮助读者深入理解排序算法的原理,并通过比较不同算法的优缺点,选择最适合特定场景的排序方法。学习这些排序算法对于提升...
**插入类排序算法详解** 插入类排序是一种基于比较的排序算法,它的主要思想是将待排序的元素逐个插入到已排序部分的适当位置...在实际编程中,选择适合的排序算法对于提高程序性能至关重要,尤其是在处理大量数据时。
在计算机科学领域,排序算法是数据结构和算法分析的重要组成部分,...在"基于JAVA语言的常见排序算法分析与比较.pdf"文件中,你将找到更详细的算法实现、性能测试和可视化示例,这将对学习和掌握Java排序算法大有裨益。
在计算机科学领域,排序算法是数据处理中至关重要的一部分,它涉及到如何有效地组织和排列一系列数据。本主题将深入探讨六种常见的排序算法:...通过实验和理论分析,我们可以更好地理解和优化排序算法,提高程序性能。
在PHP编程语言中,排序算法是处理数据时...根据具体需求和数据特性,可以选择合适的排序算法来优化程序性能。在PHP开发中,除了内置的`sort()`和`asort()`等函数,自定义排序算法可以帮助开发者更好地控制排序过程。