一、什么是选择排序？
1. 选择排序的主要思想是每一趟从待排序列中选取一个关键字值最小的记录，也即第1趟从n个记录中选取关键字最小的记录，在第2趟中，从剩下的n-1个记录中选取关键字值最小的记录，直到整个序列中的记录都选完位置，这样，由选取记录的顺序便可得到按关键字有序的排序。
2. 常见的三种选择排序方式：
直接选择排序
树形选择排序
堆排序
二、直接选择排序
1）概述
首先在所有记录中选出关键字值最小的记录，把它与第一个记录进行位置交换，
然后在其余的记录中再选出关键字值次小的记录，与第二个记录进行位置交换
依次类推，直到所有记录排好序。
2）示意图
3）算法分析
主要步骤：
置i 的初值为0
当i＜n-1时，重复下列步骤：
1.在无序子序列{r[i+1], ... , r[n-1]}中选出一个关键字值最小的记录r[min]
2. 若r[min]不是r[i]（即min != i），则交换r[i]和r[min]的位置，否则不进行交换
3.将i的值加1
4）算法代码实现
代码
//【算法】直接选择排序 public void selectSort() { // System.out.println("直接选择排序"); RecordNode temp; //辅助结点 for (int i = 0; i < this.curlen - 1; i++) {//n-1趟排序 //每趟在从r[i]开始的子序列中寻找最小元素 int min = i; //设第i条记录的关键字最小 for (int j = i + 1; j < this.curlen; j++) {//在子序列中选择关键字最小的记录 if (r[j].key.compareTo(r[min].key) < 0) { min = j; //记住关键字最小记录的下标 } } if (min != i) { //将本趟关键字最小的记录与第i条记录交换 temp = r[i]; r[i] = r[min]; r[min] = temp; } System.out.print("第" + (i + 1) + "趟: "); display(); } }
- 测试
public class TestSeqList7_select { public static void main(String[] args) throws Exception { int[] arr = {52,39,67,95,70,8,95,25}; SeqList seqList = new SeqList(arr.length); System.out.print("序列号:"); for (int i = 0; i < arr.length; i++) { System.out.print(" " + i); seqList.insert(i, new RecordNode(arr[i])); } System.out.println(); // 直接选择排序 seqList.selectSort(); } } //直接选择排序 //序列号: 0 1 2 3 4 5 6 7 //第1趟: 8 39 67 95 70 52 95 25 //第2趟: 8 25 67 95 70 52 95 39 //第3趟: 8 25 39 95 70 52 95 67 //第4趟: 8 25 39 52 70 95 95 67 //第5趟: 8 25 39 52 67 95 95 70 //第6趟: 8 25 39 52 67 70 95 95 //第7趟: 8 25 39 52 67 70 95 95
5）性能分析
对n个记录进行简单选择排序，所需进行的关键字间的比较次数总计为：
移动记录的次数，最小值为0，最大值为3(n-1)
时间复杂度：O(n2)
空间复杂度：O(1) ，仅用一个辅助单元
直接选择排序是不稳定排序算法。
6）练习
练习1：使用直接选择排序，写出每一趟的排序结果。
序列：16, 15, 50, 53, 64, 7
练习2：使用直接选择排序，写出每一趟的排序结果。
序列：2,5,8,3,6,9,1,4,7
练习3：使用直接选择排序，写出每一趟的排序结果
序列：9 , 20 , 13 , 20 , 12
三、树形选择排序
1）概述
在直接选择排序中，关键字的总比较次数是n(n-1)/2 。
实际上，该方法中，有许多关键字之间进行了不止一次的比较，也就是说，两个关键字之间可能进行了两次以上的比较。能否在选择最小关键字值记录的过程中，把关键字比较的结果保存下来，以便在以后需要的时候直接查看这个比较结果，而不需要再进行比较呢。 答案是肯定的。
树形选择排序（Tree Selection Sort）的原理与此类似。
树形选择排序又称为锦标赛排序。
也就是，体育比赛中的淘汰制，每两个对手经过比赛留下 获胜者继续参加下一轮的淘汰赛，直到最后剩下两个对手进行决赛争夺冠军。
2）算法分析
待排序序列为：52, 39, 67, 95, 70, 8, 25, 52
首先针对n个记录进行两两比较，比较的结果是把关键字值较小者作为优胜者上升到父节点，得到n/2个优胜者，作为第一步比较的结果保留下来。
然后对n/2个记录再进行关键字的两两比较，如此重复，直到选出一个关键字值最小的记录为止。
这个过程可用一个含有n个叶子节点的完全二叉树来表示，这种树称为胜者树。
接着，再求出次小关键字记录，只需将叶子节点中最小的关键字值改为∞，然后从该叶子节点开始与其左(或右)兄弟的关键字进行比较，用较小关键字修改父节点关键字，用此方法，从下到上修改从该叶子结点到根节点路径上的所有结点的关键字，则可得到次小关键字记录。
以此类推，可依次选出从小到大的所有关键字。
3）树结点类
class TreeNode { //胜者树的结点类 public RecordNode data; //排序记录结点数据值 public int index; //结点在满二叉树中的序号 public int active; //参加选择标志，1表示参选，0表示不参选 }
4）算法：树形选择排序
1.【算法】 树形选择排序(锦标赛排序)
//【算法】 树形选择排序(锦标赛排序) //建立树的顺序存储数组tree,并对其排序，并将结果返回到r中 void tournamentSort() { TreeNode[] tree; // 胜者树结点数组 int leafSize = 1; // 胜者树的叶子结点数 // 得到胜者树叶子结点(外结点)的个数，该个数必须是2的幂，例如：7个结点，需要8个叶子 while (leafSize < this.curlen) { leafSize *= 2; } int TreeSize = 2 * leafSize - 1; // 胜者树的所有节点数 P178 int loadindex = leafSize - 1; // 叶子结点(外结点)存放的起始位置 tree = new TreeNode[TreeSize]; int j = 0; //用于处理每层中的所有结点，每次处理2个，j和j+1 //给叶子结点填充数据 //把待排序结点复制到胜者树的叶子结点中，如果有数据active为1，如果没有数据active为0 for (int i = loadindex; i < TreeSize; i++) { tree[i] = new TreeNode(); tree[i].index=i; if (j < this.curlen) { // 复制结点 tree[i].active=1; tree[i].data=r[j++]; } else { tree[i].active=0; // 空的外结点，叶子结点没有填满，相当于∞ } } // 给非叶子结点赋值，值的来源是两个叶子节点的获胜者 // 使用i记录每一层第一个结点的索引值 int i = loadindex; // 进行初始比较查找关键码最小结点 while (i > 0) { // 产生胜者树，先下层后上层，每层从头开始 j = i; // 处理某一层中的所有结点，获胜者将赋值给父节点，处理数据2个2个处理 while (j < 2 * i) { // 处理各对比赛者，处理当前层，每次处理2个结点 if (tree[j + 1].active == 0 || ((tree[j].data).key.compareTo((tree[j + 1].data).key)) <= 0) { tree[(j - 1) / 2] = tree[j]; // 左孩子(胜者)赋值给父结点 } else { tree[(j - 1) / 2] = tree[j + 1]; // 右孩子(胜者)赋值给父结点 } j += 2; // 下【一对】比赛者（2个结点） } i = (i - 1) / 2; // 处理上层结点（获得上层第一个结点的下标） } // 依次更新数据，将不参赛的结点剔除，tree[0]存放每次比较的获胜者 for (i = 0; i < this.curlen - 1; i++) { // 处理剩余的n-1个记录 r[i] = tree[0].data; // 将胜者树的根(最小者)存入数组r tree[tree[0].index].active=0; // 该元素相应外结点不再比赛 updateTree(tree, tree[0].index); // 调整胜者树，将最小元素移至到根元素 display(); } // 整理n-1完成后，树中存放最后一个结点，也就是最大值 r[this.curlen - 1] = tree[0].data; }
2.【算法】树形选择排序的调整算法
//【算法】树形选择排序的调整算法，i是当前最小关键字记录的下标 void updateTree(TreeNode[] tree, int i) { int j; // 当前记录i已经参选，将对手存放到父节点 if (i % 2 == 0) { // i为偶数，对手为左结点 tree[(i - 1) / 2] = tree[i - 1]; } else { // i为奇数，对手为右结点 tree[(i - 1) / 2] = tree[i + 1]; } i = (i - 1) / 2; // 最小元素输出后，其对手上升到父结点 while (i > 0) { // 直到i==0 // 获得对手的索引，左孩子(i)的对手右孩子(i+1)；右孩子(i)的对手左孩子(i-1) if (i % 2 == 0) { // i为偶数，对手为左结点 j = i - 1; } else { // i为奇数，对手为右结点 j = i + 1; } // 比赛对手中有一个为空 if (tree[i].active == 0 || tree[j].active == 0) { if (tree[i].active == 1) { tree[(i - 1) / 2] = tree[i]; // i可参选，i上升到父结点 } else { tree[(i - 1) / 2] = tree[j]; // 否则，j上升到父结点(j可参选或不可参选) } } else { // 双方都可参选 // 关键码小者上升到父结点 if ((tree[i].data).key.compareTo((tree[j].data).key) <= 0) { tree[(i - 1) / 2] = tree[i]; } else { tree[(i - 1) / 2] = tree[j]; } } i = (i - 1) / 2; // i上升到父结点 } }
3.测试
public class TestSeqList8_tree { public static void main(String[] args) throws Exception { int[] arr = {52,39,67,95,70,8,25,52}; SeqList seqList = new SeqList(arr.length); System.out.print("序列号:"); for (int i = 0; i < arr.length; i++) { System.out.print(" " + i); seqList.insert(i, new RecordNode(arr[i])); } System.out.println(); // 树形选择排序(锦标赛排序) seqList.tournamentSort(); seqList.display(); } } //树形选择排序(锦标赛排序)
5）性能分析
空间复杂度：树形选择排序虽然减少了排序时间，但使用了较多的附加存储空间（多了2n-1个）。
时间复杂度：O(nlog2n)
树形选择排序是一种==稳定==的排序算法。
6）练习
练习1：使用树形选择排序，写出每一趟的排序结果
序列：16, 15, 50, 53, 64, 7
