排序>>选择排序>>选择排序
List:
| 123 | 0.概念+伪代码+示例分析1.选择排序实现2.Question |
- start
基本概念：
维基百科http://zh.wikipedia.org/wiki/%E9%81%B8%E6%93%87%E6%8E%92%E5%BA%8F
伪代码:
| 123456789101112131415 | function selectSort(A : list[1..n]) { index = n while (index > 1): #共有n-1次选择 { max_index = index for i from index downto 1 { #每次从剩余序列选出最大的 if(A[i] > A[max_index) { max_index = i } } swap(A[index], A[max_index ]) #将最大的换到后面 index = index –1 }} |
示例：
[49, 38, 65, 97, 76, 13, 27]
| 12345678910111213 | Current index 6 value= 27 Max index: 3 value= 97exchange -> [49, 38, 65, 27, 76, 13, 97]Current index 5 value= 13 Max index: 4 value= 76exchange -> [49, 38, 65, 27, 13, 76, 97]Current index 4 value= 13 Max index: 2 value= 65exchange -> [49, 38, 13, 27, 65, 76, 97]Current index 3 value= 27 Max index: 0 value= 49exchange -> [27, 38, 13, 49, 65, 76, 97]Current index 2 value= 13 Max index: 1 value= 38exchange -> [27, 13, 38, 49, 65, 76, 97]Current index 1 value= 13 Max index: 0 value= 27exchange -> [13, 27, 38, 49, 65, 76, 97]Done |
- start
实现代码
| 12345678910 | def select_sort(l): index = len(l) –1 while index: max_index = index for i in range(index): if l[i] > l[max_index]: max_index = i if l[max_index] > l[index]: l[index],l[max_index] = l[max_index], l[index] index -= 1 |
- start
A.概念，过程描述？
B.交换次数，比较次数，赋值次数?
C. 时间复杂度？空间复杂度？是否是稳定排序？
D.适用场景，何种情况下表现最优