思想： 选择排序是将当前元素和之后数组中最小的元素进行比较

    • 如果当前元素大于后面数组中最小的元素，那么执行交换操作
    • 如果当前元素小于等于后面数组中最小的元素，则不执行交换操作，继续往后比较
      选择排序 - 图1

    时间复杂度：选择排序 - 图2#card=math&code=O%28N%5E2%29)

    空间复杂度：选择排序 - 图3#card=math&code=O%281%29)

    稳定性：不稳定，例如5 8 5 2 9，第一轮选择第1个元素5会和2交换，那么原序列中两个5的相对前后顺序就被破坏了

    Java代码实现：

    1. public int[] selectSort(int[] arr){
    2.     if(arr.length < 2){
    3.         return arr;
    4.     }
    6.     for (int i = 0; i < arr.length; i++) {
    7.         // 将当前元素认为是最小的元素
    8.         int index = i;
    9.         System.out.print(arr[i] + " " );
    10.         for(int j = i; j < arr.length; j++){
    11.             // 如果后续有更小的元素，则更新index
    12.             if(arr[j] < arr[index]){
    13.                 index = j;
    14.             }
    15.         }
    16.         // 将当前遍历位置的元素和后续数组中最小的元素互换
    17.         swap(arr, index, i);
    18.         System.out.println(Arrays.toString(arr));
    19.     }
    20.     return arr;
    21. }
    22. public void swap(int[] arr, int i, int j) {
    23.     int temp = arr[i];
    24.     arr[i] = arr[j];
    25.     arr[j] = temp;
    26. }

    Python代码实现：

    1. # 选择排序
    2. # 每一轮都将当前最小的元素放在已排序区间的后面
    3. def select_sort(nums):
    4.     n = len(nums)
    5.     for i in range(0,n - 1):
    6.         min = i                             #最小元素下标标记
    7.         for j in range(i + 1,n):
    8.             if nums[j] < nums[min] :
    9.                 min = j                     #找到最小值的下标
    10.         nums[min],nums[i] = nums[i],nums[min]   #交换两者
    11.         print('index: {} -- {}'.format(i, nums))
    12.     return nums
    15. if __name__ == "__main__":
    16.     nums = [5, 2, 9, 7, 6, 12, 3, 4]
    18.     # 选择排序
    19.     print ('select sort result is: ', select_sort(nums))