简单排序算法
时间复杂度均为O(n2)
选择排序
选择排序(selection sort)的工作原理非常简单:开启一个循环,每轮从未排序区间选择最小的元素,将其放到已排序的区间的末尾。
算法流程
设数组长度为n,选择排序的算法流程如下。
- 初识状态下,所有元素未排序,即未排序(索引)区间为[1, n-1]。
- 选取区间[0,n-1]中的最小元素,将其与索引0处的元素交换。完成后,数组前1一个元素已排序。
- 选取区间[1,n-1]中的最小元素,将其与索引1处的元素交换,完成后,数组前2个元素已排序。
- 以此类推。经过n - 1轮选择与交换后,数组前 n-1个元素已排序。
- 仅剩的一个元素必定是最大元素,无需排序,因此数组排序完成。
/*选择排序*/
void selectionSort(vector<int> &nums){
int n = nums.size();
// 外循环:未排序区间为[i , n-1]
for (int i = 0; i < n - 1; ++i){
int k = i;
// 内循环:找到未排序区间的最小元素
for (int j = i; j < n; ++j){
if (nums[j] < nums[k])
k = j;
}
// 将该最小元素与未排序区间的首个元素交换
swap(nums[i], nums[k]);
}
}