选择排序

如果有N个元素需要排序，那么首先从N个元素中找到最小的那个(称为第0小的)放在第0个位子上(和原来的第0个位子上的元素交换位置)，然后再从剩下的N-1个元素中找到最小的放在第1个位子上，然后再从剩下的N-2个元素中找到最小的放在第2个位子上……直到所有的元素都就位。

void SelectionSort(int a[] ,int size)
{
	for( int i = 0; i < size - 1; ++i ){//每次循环后将第i小的元素放好
		int tmpMin = i;
		//用来记录从第i个到第size-1个元素中，最小的那个元素的下标
		for( int j = i+1; j < size ; ++j) {
			if( a[j] < a[tmpMin] )
			tmpMin = j;
		}
		//下面将第i小的元素放在第i个位子上，并将原来占着第i个位子的元素挪到后面
		int tmp = a[i];
		a[i] = a[tmpMin];
		a[tmpMin] = tmp;
	}
}

复杂程度分析

看执行次数最多的语句执行了多少次。

比较语句一共执行了 (s - 1) + (s - 2) + ... + 1 次，即 s * (s - 1) / 2 次，式子的“量级”是 s ^ 2.

插入排序

• 将整个数组a分为有序的部分和无序的两个部分。前者在左边，后者在右边。
• 开始有序的部分只有a[0]，其余都属于无序的部分
• 每次取出无序部分的第一个（最左边）元素，把它加入到有序部分。假设插入到合适位置p, 则原p位置及其后面的有序部分元素，都向右移动一个位子。有序的部分即增加了一个元素。
• 直到无序的部分没有元素

void InsertionSort(int a[] ,int size)
{
	for(int i = 1;i < size; ++i ) {
		//a[i]是最左的无序元素，每次循环将a[i]放到合适位置
		for(int j = 0; j < i; ++j)
			if( a[j]>a[i]) {
			//要把a[i]放到位置j，原下标j到 i-1的元素都往后移一个位子
				int tmp = a[i];
				for(int k = i; k > j; --k)
					a[k] = a[k-1];
				a[j] = tmp;
				break;
			}
	}
}

复杂程度分析

复杂程度的量级仍然是 size ^ 2.