简单算法思想01|排序

1.桶排序：把对应的数放入对应的桶，然后输出桶。

#include <stdio.h>

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

优点：简单
缺点：浪费空间

2.冒泡排序：每次比较两个相邻的元素，如果它们的顺序错误就把它们交换 过来。

#include <stdio.h>
int main() {
	int a[100],i,j,t,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-1;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("%d\t",a[i]);
		
		return 0;
		
}

优点：可以结合字符串输出信息。

3.最常用的排序：快速排序（基于一种二分的思想）

首先选择一个数作为基准数（用来参照的数）

#include <stdio.h>
int a[100],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() {
	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\t",a[i]);
	return 0;
}