学步园

想快速把《啊哈，算法》读完，简要记录一下书的内容，挺萌的书，挺适合用来入门的，用严蔚敏的入门太让人拙计了。^_^o~ 努力！

一、桶排序

书中是简化版的桶排序，主要思想就是把数据存入数组，数组下标用来表示数据本身，数组的内容表示每个数据出现的次数。这个简易版的桶排序时间复杂度是O（m+n），直接上代码了，代码简易，有点C语言基础就能看懂。

#include<stdio.h>
int main(void)
{
	int book[1001];
	int i, j, t, n;
	for(i = 0; i <= 1000; i++) {
		book[i] = 0;
	} 
	scanf("%d", &n);
	for(i = 1; i <= n; i++) {
		scanf("%d", &t);
		book[t]++;
	}
	for(i = 1000; i >=0; i--) {
		for(j = 1; j <= book[i]; j++) {
			printf("%d ", i);
		}
	}
	return 0;
}

二、冒泡排序

基本思想：每次比较两个相邻的元素，如果他们的顺序错误就对两元素进行交换。时间复杂度为O（N^2）。

核心代码：

#include<stdio.h>

int main(void)
{
	int a[100], t;
	int i, j, n;
	scanf("%d", &n);
	for(i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
	} 
	for(i = 1; i <= n-1; i++) {
		for(j = 1; j <= n-i; j++) {
			if(a[j] < a[j+1]) {
				t = a[j];
				a[j] = a[j+1];
				a[j+1] = t;
			}
		}
	}
	for(i = 1; i <= n; i++) {
		printf("%s\n", a[i]);
	}
	return 0;
}

三、快速排序

排序的时候设置一个基准点，将小于等于基准点的数全部放到基准点的左边，将大于等于基准点的数全部放到基准点的右边。最坏的情况下，仍可能是相邻的两个数进行了交换，所以最差的时间复杂度和冒泡一样都是O（N^2），平均时间复杂度为O（NlogN）。

核心代码：

#include<stdio.h>
int a[101], n;

void quicksort(int left, int right) {
	int i, j, t, temp;
	
	if(left > right) return;
	
	temp = a[left];
	i = left;
	j = right;
	while(i != j) {
		
		//先从右往左找
		while(a[j] >= temp && i < j) {
			j--;
		} 
		//再从左往右找 
		while(a[i] <= temp && i < j) {
			i++;
		}
		if(i < j) {
			
			t = a[i];
			a[i] = a[j];
			a[j] = t;
		}
	}
	//最终将基准数定位
	a[left] = a[i];
	a[i] = temp;
	
	quicksort(left, i - 1);//继续处理左边的，这里是一个递归的过程 
	quicksort(i + 1, right); //继续处理右边的，这里是一个递归的过程 
}


int main(void)
{
	int i, j, t;
	scanf("%d", &n);
	for(i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
	}
	quicksort(1, n);
	
	for(i = 1; i <= n; i++) {
		printf("%d ", a[i]);
	}
	
	return 0;
}