直接选择排序
选择排序(Selection Sort)的基本思想是:每一趟从待排序的记录中选出关键字最小的记录,顺序放在已排好序的子文件的最后,直到全部记录排序完毕。
常用的选择排序方法有直接选择排序和堆排序。
直接选择排序(Straight Selection Sort)
1、直接选择排序的基本思想
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趟直接选择排序得到有序结果。
2、直接选择排序的过程
对初始关键字为49、38、65、97、76、13、27和49的文件进行直接选择排序的过程【参见动画演示】
3、算法描述
直接选择排序的具体算法如下:
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
} //SeleetSort
4、算法分析
(1)关键字比较次数
无论文件初始状态如何,在第i趟排序中选出最小关键字的记录,需做n-i次比较,因此,总的比较次数为:
n(n-1)/2=0(n2)
(2)记录的移动次数
当初始文件为正序时,移动次数为0
文件初态为反序时,每趟排序均要执行交换操作,总的移动次数取最大值3(n-1)。
直接选择排序的平均时间复杂度为O(n2)。
(3)直接选择排序是一个就地排序
(4)稳定性分析
直接选择排序是不稳定的
【例】反例[2,2,1]
算法程序
void selectsort(int n,int[])
//选择排序
//选择排序(Selection Sort)的基本思想是:每一趟从待排序的记录中选出关键字最小的记录,
//顺序放在已排好序的子文件的最后,直到全部记录排序完毕。
//常用的选择排序方法有直接选择排序和堆排序。
//复杂度n^2
//直接选择排序是不稳定的
{
int i,j,x,l;
for(i=n-1;i>=1;i--)
{
x=a[i];
l=i;
for(j=0;j<i;j++)
{
if(a[j]>x)
{
x=a[j];
l=j;
}
}
a[l]=a[i];
a[i]=x;
}
}
分享到:
相关推荐
数据结构课程设计直接选择排序 数据结构课程设计直接选择排序 数据结构课程设计直接选择排序 数据结构课程设计直接选择排序 数据结构课程设计直接选择排序 数据结构课程设计直接选择排序 数据结构课程设计直接选择...
数据结构--内部排序算法 1、下列排序算法中,_____________排序在某趟结束后不一定能选出一个元素放到其最 终的位置上。 (1)选择 (2)冒泡 (3)归并 (4)堆 2、下列排序算法中,依次将待排序列中的元素和前面...
此文件为数据结构中的九种排序算法,包含一些排序方法的过程,其九种排序包括:直接插入排序,折半插入排序,希尔排序,冒泡排序,快速排序,选择排序,堆排序,归并排序,基数排序!
本资源是博文【数据结构】手撕排序NO.2----直接插入排序与希尔排序的配套演示资料,包含直接插入排序、希尔排序的动画演示以及两种插入排序的复杂度分析。可结合以下博文查看:http://t.csdn.cn/pljVV
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
数据结构-3期(KC002) 直接选择排序算法.docx 学习资料 复习资料 教学资源
包括冒泡排序,直接选择排序,希尔排序,快速排序,堆排序。 (2) 待排序的元素的关键字为整数。其中的数据要用随机数产生(如10000个),至少用5组不同的数据做比较,再使用各种算法对其进行排序,记录其排序时间,再...
编写程序实现直接插入排序、希尔排序(d=5)、直接选择排序、快速排序和二路归并排序算法。
关于数据结构,是C++语言实现的,能实现直接选择排序、希尔排序
数据结构 综合排序 冒泡排序 直接插入排序 快速排序 希尔排序,完整的代码,有每种排序时间的比较
数据结构从入门到精通-直接选择排序
数据结构-3期(KC002) 直接插入排序算法.docx 学习资料 复习资料 教学资源
(1)对以下6种常用的内部排序算法进行比较:冒泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。 (2)待排序表的表长不小于100,其中的数据要用伪随机数产生程序产生,至少要用5组不同的输入...
用函数实现直接插入排序,并输出每趟排序的结果. Input 第一行:键盘输入待排序关键的个数n 第二行:输入n个待排序关键字,用空格分隔数据 Output 每行输出一趟排序结果,数据之间用一个空格分隔 Sample Input 10 ...
漫话数据结构
数据结构---直接插入排序/快速排序/选择排序/冒泡排序(详细实现算法和性能比较)
数据结构课程中直接插入排序的示例程序 完整示例
8.7.2 置换-选择排序 253 8.7.3 佳归并树 254 8.7.4 败者树 255 8.7.5 时间与空间复杂度相关问题 257 8.8 排序知识点小结 258 ▲真题仿造 259 真题仿造答案与解析 259 习题 真题精选 260 习题答案 真题精选答案 265 ...
实现直接插入排序、折半插入、冒泡、快速、直接选择、堆、归并排序算法。比较各种 算法的运行速度和时间复杂度,是否为稳定排序。分析每一趟排序结果。
包括冒泡排序,直接选择排序,希尔排序,快速排序,堆排序。 (2) 待排序的元素的关键字为整数。其中的数据要用随机数产生(如10000个),至少用5组不同的数据做比较,再使用各种算法对其进行排序,记录其排序时间,再...