十大经典排序算法（上篇）：选择排序

前面说的冒泡排序是每一轮比较确定最后一个元素，中间过程不断地交换。而选择排序就是每次选择剩下的元素中最小的那个元素，与当前索引位置的元素交换，直到所有的索引位置都选择完成。

排序的步骤如下：

从第一个元素开始，遍历其后面的元素，找出其后面比它更小的且最小的元素，若有，则两者交换，保证第一个元素最小。

对第二个元素一样，遍历其后面的元素，找出其后面比它更小的且最小的元素，若存在，则两者交换，保证第二个元素在未排序的数中（除了第一个元素）最小。

依次类推，直到最后一个元素，那么数组就已经排好序了。

前面两轮选择排序已经分别将 21 和 34 选择出来，放到最前面的位置。

剩下的排序是确定 56 和 90 的位置，最后一个 98 自然就是最大的数，不需要再排序。

新建一个类 SelectionSort.java，主要函数如下：

public class SelectionSort {

  public static void selectionSort(int[] nums) {
    int times = 0;
    int size = nums.length;
    int minIndex, temp;
    for (int i = 0; i < size - 1; i++) {
      System.out.print("第" + (i + 1) + "轮选择开始：");
      minIndex = i;
      for (int j = i + 1; j < size; j++) {
        times++;
        if (nums[j] < nums[minIndex]) {
          minIndex = j;
        }
      }
      System.out.println("交换 " + nums[i] + "和" + nums[minIndex]);
      temp = nums[i];
      nums[i] = nums[minIndex];
      nums[minIndex] = temp;
      printf(nums);
    }
    System.out.println("比较次数：" + times);
  }
}

测试代码：

public static void main(String[] args) {
    int[]nums = new int[]{98,90,34,56,21};
    printf(nums);
    selectionSort(new int[]{98,90,34,56,21});
}

#include 
using namespace std;

void selectionSort(int nums[],int size);
void printf(int nums[],int size);

int main() {
   int nums[] = {98,90,34,56,21};
   int size =  sizeof(nums)/sizeof(nums[0]);
   printf(nums,size);
   selectionSort(nums,size);
   return 0;
}

void selectionSort(int nums[],int size) {
  int times = 0;
  int minIndex;
  for (int i = 0; i < size - 1; i++) {
    cout<< "第" << (i + 1) << "轮选择开始："< 
Python 解法代码 
class Solution:
    def selectionSort(self, nums):
        times = 0
        size = len(nums)
        minIndex, temp = 0, 0

        for i in range(size - 1):
            print("第", (i + 1), "轮选择开始：")
            minIndex = i
            for j in range(i + 1, size):
                times = times + 1
                if (nums[j] < nums[minIndex]):
                    minIndex = j
            print("交换 ", nums[i], "和", nums[minIndex])
            print(end="")
            temp = nums[i]
            nums[i] = nums[minIndex]
            nums[minIndex] = temp
            self.printNums(nums)
        print("比较次数：", times, end="")

    def printNums(self, nums):
        for i in range(len(nums)):
            print("%d " % nums[i], end="")
        print("")


if __name__ == '__main__':
    solution = Solution()
    nums = [98, 90, 34, 56, 21]
    solution.printNums(nums)
    solution.selectionSort(nums)