10.3选择排序 基本思想是:每次从待排序的数据元素集合中选取关键字 最小(或最大)的数据元素放到数据元素集合的最前(或最 后),数据元素集合不断缩小,当数据元素集合为空时选择 排序结束。 常用的选择排序算法 (1)直接选择排序 (2)堆排序
10.3 选择排序 基本思想是：每次从待排序的数据元素集合中选取关键字 最小（或最大）的数据元素放到数据元素集合的最前（或最 后），数据元素集合不断缩小，当数据元素集合为空时选择 排序结束。 常用的选择排序算法： （1）直接选择排序 （2）堆排序
1直接选择排序 基本思想是:从待排序的数据元素集合中选取关键字最小的 数据元素并将它与原始数据元素集合中的第一个数据元素交换 位置;然后从不包括第一个位置上数据元素的集合中选取关键 字最小的数据元素并将它与原始数据元素集合中的第二个数据 元素交换位置;如此重复,直到数据元素集合中只剩一个数据 元素为止。 优点:实现简单 缺点:每趟只能确定一个元素,表长为n时需要n-1趟
1.直接选择排序 基本思想是：从待排序的数据元素集合中选取关键字最小的 数据元素并将它与原始数据元素集合中的第一个数据元素交换 位置；然后从不包括第一个位置上数据元素的集合中选取关键 字最小的数据元素并将它与原始数据元素集合中的第二个数据 元素交换位置；如此重复，直到数据元素集合中只剩一个数据 元素为止。 优点：实现简单 缺点：每趟只能确定一个元素，表长为n时需要n-1趟
算法如下 void SelectSort(DataType al, int n) int i,j, small; Data Type temp; for(i=0;i<n-1;i++) small=i /设第个数据元素关键字最小 forgi=i+1;j<n;j++) 找关键字最小的数据元素 if(aj. key< asmall. key)small=j; ∥记住最小元素的下标 if(small =i) /最小元素的下标不为时交换位置 temp=a; ai=a smalll; asmal= temp;
算法如下： void SelectSort(DataType a[], int n) { int i, j, small; DataType temp; for(i = 0; i < n-1; i++) { small = i; //设第i个数据元素关键字最小 for(j = i+1; j < n; j++) //寻找关键字最小的数据元素 if(a[j].key< a[small].key)small=j; //记住最小元素的下标 if(small!= i) //当最小元素的下标不为i时交换位置 { temp = a[i]; a[i] = a[small]; a[small]= temp; } } }
初始关键字序列: 7 89 24 第一次排序结果 {5} 7 89 24 第二次排序结果 7 64 24 第三次排序结果 6 7 64 24 第四次排序结果 {5 6 7 24} 64 第五次排序结果 {5 7 24 64} 89 最后结果序列: 7 64 89} 直接选择排序的排序过程
64 5 7 89 6 24 {5} 64 7 89 6 24 {5 6} 7 89 64 24 {5 6 7} 89 64 24 {5 6 7 24} 64 89 {5 6 7 24 64} 89 初始关键字序列: 第一次排序结果: 第二次排序结果: 第三次排序结果: 第四次排序结果: 第五次排序结果: 最后结果序列: {5 6 7 24 64 89} 直接选择排序的排序过程
算法分析 时间效率:O(n2)虽移动次数较少,但比较次数仍多 空间效率:O(1)没有附加单元(仅用到1个temp) 算法的稳定性:不稳定
算法分析 时间效率： O(n2 )——虽移动次数较少，但比较次数仍多。 空间效率：O(1)——没有附加单元（仅用到1个temp) 算法的稳定性：不稳定