04、简单选择排序

厨子大约 4 分钟数据结构算法基础面试题解析排序算法程序厨校招社招算法题精讲

算法简介

我们的冒泡排序不断进行交换，通过交换完成最终的排序，我们的简单选择排序的思想也很容易理解，主要思路就是我们每一趟在 n-i+1 个记录中选取关键字最小的记录作为有序序列的第 i 个记录。

例如上图，绿色代表已经排序的元素，红色代表未排序的元素。我们当前指针指向 4 ，则我们遍历红色元素，从中找到最小值，然后与 4 交换。我们发现选择排序执行完一次循环也至少可以将 1 个元素归位。

下面我们来看一下代码的执行过程，看过之后肯定能写出代码的。

注：我们为了更容易理解，min 值保存的是值，而不是索引，实际代码中保存的是索引

动画模拟

代码

Java Code:

class Solution {
    public int[] sortArray(int[] nums) {

        int len = nums.length;
        int min = 0;
        for (int i = 0; i < len; ++i) {
            min = i;
            //遍历到最小值
            for (int j = i + 1; j < len; ++j) {
                if (nums[min] > nums[j]) min = j;
            }
            if (min != i) swap(nums,i,min);
        }
        return nums;
    }
    public void swap (int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

C++ Code:

#include <vector>

class Solution {
public:
    std::vector<int> sortArray(std::vector<int>& nums) {
        int len = nums.size();
        int minIndex;  // 记录最小值的索引
        for (int i = 0; i < len; ++i) {
            minIndex = i;  // 初始假设当前位置为最小值
            // 遍历待排序部分，找到最小值的索引
            for (int j = i + 1; j < len; ++j) {
                if (nums[minIndex] > nums[j]) {
                    minIndex = j;
                }
            }
            // 如果最小值不在当前位置，则交换
            if (minIndex != i) {
                swap(nums, i, minIndex);
            }
        }
        return nums;
    }

private:
    // 交换数组中两个位置的元素
    void swap(std::vector<int>& nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
};

时间复杂度分析

从简单选择排序的过程来看，他最大的特点就是交换移动数据次数相当少，这样也就节省了排序时间，简单选择和冒泡排序不一样，我们发现无论最好情况和最坏情况，元素间的比较次数是一样的，第 i 次排序，需要 n - i 次比较,n 代表数组长度，则一共需要比较(n-1) + (n-2) +.... + 2 + 1= n*(n-1)/2 次，对于交换而言，最好情况交换 0 次，最坏情况(逆序时)交换 n - 1 次。那么简单选择排序时间复杂度也为 O(n^2) 但是其交换次数远小于冒泡排序，所以其效率是好于冒泡排序的。