选择排序

基本思想

选择排序是不稳定的排序算法。
假设最终结果是递增有序。在长度为N的无序数组中，第一次选定第一个位置上的元素，然后遍历后面n-1个数，找到最小的数值与第一个元素交换；第二次选定第二个位置上的元素，然后遍历后面n-2个数，找到最小的数值与第二个元素交换；依此类推，第n-1次遍历，找到最小的数值与第n-1个元素交换，排序完成。
之所以不稳定，是因为会出现这样的情况：第k次遍历时，数组中还有两个一样的值，其中一个值再第k个位置上，而遍历后面n-k个数找到的最小值在另一个和第k个位置上一样的值的元素位置之后，这样我们一交换，两个一样的值的顺序就不是元素顺序了。

C/C++实现

# include <iostream>
# include <vector>

using namespace std;

class Solution {
public:
    void swap(int &a, int &b) {
        int temp = a;
        a = b;
        b = temp;
    }

    void select_sort(vector<int> &nums) {
        int n = nums.size();
        int loc;
        for (int i = 0; i < n - 1; i++) {
            loc = i;
            for (int j = i + 1; j < n; j++) {
                if (nums[loc] > nums[j])
                    loc = j;
            }
            swap(nums[loc], nums[i]);
        }
    }
};

int main() {
    vector<int> a = {5, 2, 3, 4, 7, 5, 1, 6};
    Solution s;
    s.select_sort(a);
    for (int i : a)
        cout << i << " ";
    cout << endl;
    return 0;
}

Python3实现

class Solution(object):
    def bubble_sort(self, nums):
        n = len(nums)
        for i in range(0, n - 1):
            for j in range(1, n):
                if nums[j - 1] > nums[j]:
                    nums[j - 1], nums[j] = nums[j], nums[j - 1]


a = [5, 2, 3, 4, 7, 5, 1, 6]
s = Solution()
s.bubble_sort(a)
print(a)