选择排序的基本思想是:每一趟在n-i+1(i=1,2,3,···,n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录。
程序实现(SelectSort):
#include<stdio.h>
#include"DataType.h"
int SelectMinKey(SqList &L,int i){
// 返回在L.r[i..L.length]中key最小的记录的序号
KeyType minKey;
int j,k;
k=i;//设第i个为最小
minKey=L.r[i].key;
for(j=i+1;j<=L.length;j++){
if(minKey>L.r[j].key){
k=j;
minKey=L.r[j].key;
}
}
return k;
}//SelectMinKey
void SelectSort(SqList &L){
//对顺序表L作简单选择排序
int i,j;
RedType temp;
for(i=1;i<L.length;++i){
j=SelectMinKey(L,i);
if(i!=j){
temp=L.r[i];
L.r[i]=L.r[j];
L.r[j]=temp;
}
}
}//SelectSort
void print(SqList &L){
int i;
for(i=1;i<=L.length;i++){
printf("(%d,%d)",L.r[i].key,L.r[i].otherInfo);
}
printf("\n");
}
#define N 8
void main()
{
RedType d[N]={{49,1},{38,2},{65,3},{97,4},{76,5},{13,6},{27,7},{49,8}};
SqList l;
int i;
for(i=0;i<N;i++)
l.r[i+1]=d[i];
l.length=N;
printf("排序前:\n");
print(l);
SelectSort(l);
printf("排序后:\n");
print(l);
}
DataType.h文件
// DataType.h 待排记录的数据类型
#define MAXSIZE 20 //一个用作示例的小顺序的最大长度
typedef int KeyType;//定义关键字类型为整数类型
typedef int InfoType;//定义其他类型
typedef struct{
KeyType key;//关键字项
InfoType otherInfo;//其他数据项
}RedType; //记录类型
typedef struct{
RedType r[MAXSIZE+1];//r[0]闲置或用作哨兵单元
int length;//顺序表的长度
}SqList;//顺序表类型
复杂度分析:
选择排序的交换操作介于 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^2)。 交换次数O(n),最好情况是,已经有序,交换0次;最坏情况是,逆序,交换n-1次。 交换次数比冒泡排序少多了,由于交换所需CPU时间比比较所需的CPU时间多,n值较小时,选择排序比冒泡排序快。
分享到:
相关推荐
(1) 完成5种常用内部排序算法的演示,5种排序算法为:快速排序,直接插入排序,选择排序,堆排序,希尔排序; (2) 待排序元素为整数,排序序列存储在数据文件中,要求排序元素不少于30个; (3) 演示程序开始,...
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
冒泡排序 简单选择排序 c语言基础 排序算法 数组操作 排序算法实验 简单的c语言程序 排序算法输出
直接插入排序 选择排序 堆排序 归并排序 快速排序 冒泡排序等七种排序方法
选择排序 ss_sort(int e[],int n) 直接插入排序 ss_sort(int e[],int n) 冒泡排序 sb_sort(int e[],int n) 二路合并排序 Merge(int e[],int n) 对给定的数组E[N]={213,111,222,77,400,300,987,1024,632,555} 分别...
插入排序,选择排序,基数排序,冒泡排序的C++实现
选择排序、插入排序、冒泡排序以及快速排序和归并排序的C语言实现,绝对可用
用选择排序法对数组排序,选择排序用函数对立起来。
交换排序 选择排序 冒泡排序 插入排序
希尔排序,堆排序,快速排序,简单选择排序,插入排序,冒泡排序
选择排序法源代码,具体代码与解释,绝对能运行成功的,放心使用。
算法作业的线性选择排序 算法作业的线性选择排序 算法作业的线性选择排序
有一个模板类写出了快速排序,冒泡排序,插入排序,选择排序四种算法。用的是C++哦
用函数实现简单选择排序,并输出每趟排序的结果 Input 第一行:键盘输入待排序关键的个数n 第二行:输入n个待排序关键字,用空格分隔数据 Output 每行输出每趟排序的结果,数据之间用一个空格分隔 Sample Input 10...
插入排序、快速排序、选择排序、选择排序、内部排序方法的比较
7大排序算法(快速排序,冒泡排序,选择排序,归并排序,插入排序,希尔排序,堆排序)实现源码
冒泡排序,选择排序,插入排序,希尔排序,堆排序,归并排序,快速排序源码实现,里面有详细讲解,对新手应该有帮助
六种内部排序算法比较:直接插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序。包含实验报告和源代码设计。
选择排序,比较常见的排序算法之一。这是两个例子,两个关于选择排序的例子。
该代码类实现了选择排序的可视化。 程序的关键点主要有两点: 1. 如何在页面上表示出排序程序的运行过程。 2. 如何将排序程序的运行过程和可视化排序结合起来,保持状态一致。 我的解决方法如下: 我采用了...