| 词条 | 选择排序 |
| 释义 | § 关键词 选择排序 § 情况连接 1. 基本思想： 每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。 2. 排序过程： § 【示例】： 初始关键字 【49 38 65 97 76 13 27 49】 第一趟排序后 13 ［38 65 97 76 49 27 49】 第二趟排序后 13 27 ［65 97 76 49 38 49】 第三趟排序后 13 27 38 【97 76 49 65 49】 第四趟排序后 13 27 38 49 【49 97 65 76】 第五趟排序后 13 27 38 49 49 【97 97 76】 第六趟排序后 13 27 38 49 49 76 【76 97】 第七趟排序后 13 27 38 49 49 76 76 【 97】 最后排序结果 13 27 38 49 49 76 76 97 3. void selectionSort(Type* arr,long len) { long i=0,j=0;/*iterator value*/ long maxPos; assertF(arr!=NULL,"In InsertSort sort,arr is NULL\"); for(i=len-1;i>=1;i--) { maxPos=i; for(j=0;j<i;j++) if(arr【maxPos】<arr【j】)maxPos=j; if(maxPos!=i)swapArrData(arr,maxPos,i); } } 选择排序 § 选择排序法 的第一层循环从起始元素开始选到倒数第二个元素,主要是在每次进入的第二层循环之前,将外层循环的下标赋值给临时变量,接下来的第二层循环中,如果发现有比这个最小位置处的元素更小的元素,则将那个更小的元素的下标赋给临时变量,最后,在二层循环退出后,如果临时变量改变,则说明,有比当前外层循环位置更小的元素,需要将这两个元素交换。 § 复杂度分析 选择排序的交换操作介于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),最好情况是，已经有序，交换0次；最坏情况是，逆序，交换n-1次。 交换次数比冒泡排序少多了，由于交换所需CPU时间比比较所需的CPU时间多，n值较小时，选择排序比冒泡排序快。 |
| 随便看 |
百科全书收录594082条中文百科知识，基本涵盖了大多数领域的百科知识，是一部内容开放、自由的电子版百科全书。