[转载] python选择排序二元选择_选择排序：简单选择排序（Simple Selection Sort）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了[转载] python选择排序二元选择_选择排序：简单选择排序（Simple Selection Sort），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3087字，纯文字阅读大概需要5分钟。

内容图文

参考链接： Python中选择排序Selection Sort

基本思想：

 在要排序的一组数中，选出最小(或者最大)的一个数与第1个位置的数交换；然后在剩下的数当中再找最小(或者最大)的与第2个位置的数交换，依次类推，直到第n-1个元素(倒数第二个数)和第n个元素(最后一个数)比较为止。

 简单选择排序示例

 初始值： 3 1 5 7 2 4 9 6

 第一趟： 1 3 5 7 2 4 9 6

 第二趟： 1 2 5 7 3 4 9 6

 第三趟： 1 2 3 7 5 4 9 6

 第四趟： 1 2 3 4 5 7 9 6

 第五趟： 1 2 3 4 5 7 9 6

 第六趟： 1 2 3 4 5 6 9 7

 第七趟： 1 2 3 4 5 6 7 9

 第八趟： 1 2 3 4 5 6 7 9

 操作方法：

 第一趟，从n 个记录中找出关键码最小的记录与第一个记录交换；

 第二趟，从第二个记录开始的n-1 个记录中再选出关键码最小的记录与第二个记录交换；

 ......

 第 i 趟，则从第 i 个记录开始的 n-i+1 个记录中选出关键码最小的记录与第 i 个记录交换，直到整个序列按关键码有序。

 算法的实现：

 // 输出数组内容

 void print(int array[], int length, int i) {

 printf("i=%d:",i);

 for (int j = 0; j < length; j++) {

 printf(" %d ", array[j]);

 }

 printf("\n");

 }

 // 获取数组最小值下标

 int SelectMinKey(int array[], int length, int i) {

 int k = i;

 for (int j = i + 1; j < length; j ++) {

 if (array[k] > array[j]) {

 k = j;

 }

 }

 return k;

 }

 // 简单选择排序(Simple Selection Sort)

 void SelectSort(int array[], int length) {

 int key, temp;

 for (int i = 0; i < length; i ++) {

 key = SelectMinKey(array, length, i); // 获取最小元素的下标

 if (key != i) { // 最小元素与第i位置元素交换

 temp = array[i];

 array[i] = array[key];

 array[key] = temp;

 }

 print(array, length, i);

 }

 }

 int main(int argc, const char * argv[]) {

 int arraySelectSort[8] = { 3, 1, 5, 7, 2, 4, 9, 6 };

 SelectSort(arraySelectSort, 8);

 printf("\n");

 return 0;

 }

 算法的改进(二元选择排序)

 简单选择排序，每趟循环只能确定一个元素排序后的定位。我们可以考虑改进为每趟循环确定两个元素(当前趟最大和最小记录)的位置,从而减少排序所需的循环次数。改进后对n个数据进行排序，最多只需进行[n/2]趟循环即可。具体实现如下：

 // 二元选择排序

 void SelectSort2(int array[], int length) {

 int i, j, min, max;

 for (i = 0; i < length / 2; i ++) { // i 跑 n / 2 趟排序就会排序完成

 min = max = i; // 先将 min 和 max 都指向待排序的第一个元素

 for(j = i; j < length - i; j ++) {

 if (array[j] < array[min]) {

 min = j;

 continue;

 }

 if (array[j] > array[max]) {

 max = j;

 }

 }

 // 将最小值放在第i处，将最大值放在第length-i-1处

 // 注意:这里不能把 array[max]、array[min] 直接和 array[i] 和 array[length-i-1]调换

 int maxtemp = array[max];

 int mintemp = array[min];

 array[max] = array[length-i-1];

 array[min] = array[i];

 array[i] = mintemp;

 array[length-i-1] = maxtemp;

 print(array, 8, i);

 }

 }

 总结

 在简单选择排序过程中，所需移动记录的次数比较少。最好情况下，即待排序记录初始状态就已经是正序排列了，则不需要移动记录。

 最坏情况下，即待排序记录初始状态是按第一条记录最大，之后的记录从小到大顺序排列，则需要移动记录的次数最多为3(n-1)。简单选择排序过程中需要进行的比较次数与初始状态下待排序的记录序列的排列情况无关。当i=1时，需进行n-1次比较；当i=2时，需进行n-2次比较；依次类推，共需要进行的比较次数是(n-1)+(n-2)+…+2+1=n(n-1)/2，即进行比较操作的时间复杂度为O(n^2)，进行移动操作的时间复杂度为O(n)。

 简单选择排序是不稳定排序。

内容总结

以上是互联网集市为您收集整理的[转载] python选择排序二元选择_选择排序：简单选择排序（Simple Selection Sort）全部内容，希望文章能够帮你解决[转载] python选择排序二元选择_选择排序：简单选择排序（Simple Selection Sort）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---