7. 插入排序 Insertion Sort
插入排序最好的运行时间是O(n),已经排序好了情况下,平均情况最情况都是O(n2),所以处理随机的未排序数据时并不是好的算法。
通过将每个新元素与已经排序好的元素做比较,并将其插入到正确的位置来建立一个排序的数组,就像玩扑克一样,拿到新的牌放入到已经排序好的中间。
插入排序是稳定的原地排序算法,特别适合对小的数据集合进行排序,通常作为其他更复杂的排序算法的构建模块。
void insertionSort(int *a, int len) {
for (int which=1; which<len; which++) {
int val = a[which];
for (int i=0; i<which; i++) {
if (a[i] > val) {
// do shift to
for (int j=which; j>i; j--) {
a[j] = a[j-1];
}
a[i] = val;
break;
}
}
}
}
8. 位排序 Bit Sort
用整数位的每一位来表示一个数字。详细参考《编程珠玑》。
#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F
#define N 10000000
int a[1 + N/BITSPERWORD];
void set(int i) { a[i>>SHIFT] |= (1<<(i & MASK)); }
void clr(int i) { a[i>>SHIFT] &= ~(1<<(i & MASK)); }
int test(int i){ return a[i>>SHIFT] & (1<<(i & MASK)); }
int main(void)
{
int i;
for (i = 0; i < N; i++)
clr(i);
while (scanf("%d", &i) != EOF)
set(i);
for (i = 0; i < N; i++)
if (test(i))
printf("%d\n", i);
return 0;
}