算法---选择排序

选择排序的思路

• 在乱序数组中查找到最小元素（升序），存放到起始位置
  
• 重复第一步，直到数组有序
  

代码

1. class Solution:
3.     def choose(self, arr):
4.         n = len(arr)
5.         for i in range(n - 1):
6.             min_index = i
7.             for j in range(i + 1, n):
8.                 if arr[j] < arr[min_index]:
9.                     min_index = j
10.             arr[i], arr[min_index] = arr[min_index], arr[i]
11.         return arr
14. if __name__ == "__main__":
15.     arr = [8, 0, 4, 6, 1, 2, 7, 3, 5, 9]
16.     s = Solution()
17.     res = s.choose(arr)
18.     print(res)

复制代码

优化点

使用双向指针可以进行优化

1. class Solution:
4.     def selecttion_sort(self, arr):
5.         n = len(arr)
6.         for i in range(n):
7.             min_index = i
8.             left = i + 1
9.             right = n - 1
10.             while left <= right:
11.                 if arr[left] < arr[min_index]:
12.                     min_index = left
13.                 if arr[right] < arr[min_index]:
14.                     min_index = right
15.                 left += 1
16.                 right -= 1
17.             arr[i], arr[min_index] = arr[min_index], arr[i]
18.         return arr
21. if __name__ == "__main__":
22.     arr = [8, 0, 4, 6, 1, 2, 7, 3, 5, 9]
23.     s = Solution()
24.     res = s.selecttion_sort(arr)
25.     print(res)

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。