算法---选择排序

选择排序的思路

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

代码

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
13. if __name__ == "__main__":
14.     arr = [8, 0, 4, 6, 1, 2, 7, 3, 5, 9]
15.     s = Solution()
16.     res = s.choose(arr)
17.     print(res)

复制代码

优化点

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

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

复制代码