选择排序

选择排序

每次找出第$i$小的元素（$Ai..n$中最小的元素），然后将这个元素和数组中第$i$个元素交换位置

时间复杂度： $O(n^2)$

因为交换操作的存在，所以选择排序是不稳定排序

伪代码

$ \begin{array}{ll} 1 & \textbf{Input. } \text{An array } A \text{ consisting of }n\text{ elements.} \newline 2 & \textbf{Output. } A\text{ will be sorted in nondecreasing order.} \newline 3 & \textbf{Method. } \newline 4 & \textbf{for } i\gets 1\textbf{ to }n-1 \newline 5 & \qquad ith\gets i\newline 6 & \qquad \textbf{for }j\gets i+1\textbf{ to }n\newline 7 & \qquad\qquad\textbf{if }A[j] < A[ith]\newline 8 & \qquad\qquad\qquad ith\gets j\newline 9 & \qquad \text{swap }A[i]\text{ and }A[ith]\newline \end{array} $

Java实现

public void selectionSort(int[] nums){
    for(int i = 0; i<nums.length; i++){
        int ith = i; // 记录当前需要选取的第i个最小元素
        for(int j = i+1; j<nums.length; j++){
            if(nums[j] < nums[ith]){
                ith = j;
            }
        }
        int temp = nums[i];
        nums[i] = nums[ith];
        nums[ith] = temp;
    }
}

over