选择排序的基本思想是: 每一趟在 n-i+1(i=1,2,n-1)个记录中选取关键字最小的记录作为有序序列中第 i 个记录基于此思想的算法主要有简单选择排序树型选择排序和堆排序[1]
简单选择排序的基本思想: 第 1 趟, 在待排序记录 r[1]~r[n]中选出最小的记录, 将它与 r[1]交换; 第 2 趟, 在待排序记录 r[2]~r[n]中选出最小的记录, 将它与 r[2]交换; 以此类推, 第 i 趟在待排序记录 r[i]~r[n]中选出最小的记录, 将它与 r[i]交换, 使有序序列不断增长直到全部排序完毕
以下为简单选择排序的存储状态, 其中大括号内为无序区, 大括号外为有序序列:
初始序列:{49 27 65 97 76 12 38}
第 1 趟: 12 与 49 交换: 12{27 65 97 76 49 38}
第 2 趟: 27 不动: 12 27{65 97 76 49 38}
第 3 趟: 65 与 38 交换: 12 27 38{97 76 49 65}
第 4 趟: 97 与 49 交换: 12 27 38 49{76 97 65}
第 5 趟: 76 与 65 交换: 12 27 38 49 65{97 76}
第 6 趟: 97 与 76 交换: 12 27 38 49 65 76 97 完成
写一个程序, 对任意数组做从小到大排列:
- #!/usr/bin/env python
- # -*- coding: UTF-8 -*-
- # Author:show530
- def find_minmunber(list):
- smallest_munber=list[0]
- smallest_index=0
- for i in range(1,len(list)):
- if list[i]<smallest_munber:
- smallest_munber=list[i]
- smallest_index=i
- return smallest_index
- def from_small_arr(arr):
- new_arr=[]
- for i in range(len(arr)):
- min_munber=find_minmunber(arr)
- new_arr.append(arr.pop(min_munber))
- return new_arr
- my_list=[9,24,56,97,82,1,3,6,997,642,352]
- print("列表从小到大排列为:")
- print(from_small_arr(my_list))
C:\Users\Administrator\PycharmProjects\untitled\venv\Scripts\python.exe C:/Users/Administrator/PycharmProjects/untitled/DAY1/SX.py
列表从小到大排列为:
- [1, 3, 6, 9, 24, 56, 82, 97, 352, 642, 997]
- Process finished with exit code 0
- View Code
换成从大到小排列:
- #!/usr/bin/env python
- # -*- coding: UTF-8 -*-
- # Author:show530
- def find_max_munber(list):
- max_munber=list[0]
- max_munber_index=0
- for i in range(1,len(list)):
- if list[i]>max_munber:
- max_munber=list[i]
- max_munber_index=i
- return max_munber_index
- def form_large_small(arr):
- new_arr=[]
- for i in range(len(arr)):
- largest_number=find_max_munber(arr)
- new_arr.append(arr.pop(largest_number))
- return new_arr
- my_list=[7,56,89,41,8,2,46,92,478,1,896,74,66]
- print("数组从大到小排列顺序为:")
- print(form_large_small(my_list))
C:\Users\Administrator\PycharmProjects\untitled\venv\Scripts\python.exe C:/Users/Administrator/PycharmProjects/untitled/DAY1/sx2.py
数组从大到小排列顺序为:
- [896, 478, 92, 89, 74, 66, 56, 46, 41, 8, 7, 2, 1]
- Process finished with exit code 0
- View Code
来源: http://www.bubuko.com/infodetail-2523285.html