简单排序算法

时间复杂度均为O(n²)

选择排序

选择排序（selection sort）的工作原理非常简单：开启一个循环，每轮从未排序区间选择最小的元素，将其放到已排序的区间的末尾。

算法流程

设数组长度为n，选择排序的算法流程如下。

1. 初识状态下，所有元素未排序，即未排序（索引）区间为[1, n-1]。
2. 选取区间[0，n-1]中的最小元素，将其与索引0处的元素交换。完成后，数组前1一个元素已排序。
3. 选取区间[1，n-1]中的最小元素，将其与索引1处的元素交换，完成后，数组前2个元素已排序。
4. 以此类推。经过n - 1轮选择与交换后，数组前 n-1个元素已排序。
5. 仅剩的一个元素必定是最大元素，无需排序，因此数组排序完成。

/*选择排序*/
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]);
	}
}

算法特性

• 时间复杂度为O(n²)、非自适应排序：外循环共n-1轮，第一轮的未排序区间长度为n，最后一轮的未排序区间长度为2，即各轮外循环分别包含
  标签：数据结构,nums,复杂度,元素,算法,冒泡,数组,排序,插入排序
  From： https://www.cnblogs.com/1873cy/p/18430878