选择排序

算法描述（从小到大）

首先找到数组中最小的元素，并将这个元素与数组的第1个元素交换位置。然后找数组中剩下的元素中最小的元素，再与数组的第2个元素交换位置。以此类推完成排序。

代码

vector<int> selection_sort(vector<int>& nums) {
	int n = nums.size();
	for (int i=0; i<n; i++) {
		int min_index = i;
		for (int j=i+1; j<n; j++) {
			if (nums[j]<nums[min_index]) {
				min_index=j;
			}
		}
		swap(nums[i], nums[min_index]);
	}
	return nums;
}

选择排序的特点

因为没有提前终止循环的可能性，即便输入已经排好序的数组，选择排序也将需要完整进行两次循环，也就是说，选择排序在所有情况下的时间复杂度都是O(n^2)级别。

插入排序

算法描述（从小到大）

扑克牌整理手牌的排序算法。遍历从第2张牌开始的每一张牌，然后把这张牌插入到前面合适的位置。

代码

void insertion_sort(int arr[], int n) {
	for (int i=1; i<n; i++) {
		int temp = arr[i];
		for (int j=i-1; j>=0; j--) {
			if (nums[j]>temp) {
				nums[j+1] = nums[j];
				nums[j] = temp;
			} else {
				break;
			}
		}
	}
}

插入排序的特点

插入排序针对近乎有序的数组有很高的性能，甚至在一些测试用例（比如完全有序）会快于O(nlogn)级别的排序算法，达到O(n)级别。