算法复习之冒泡排序与选择排序

基础丢的差不多了,是时候该重新捡起来,不然真的心虚啊,于是就从排序开始,上 poj 找基础的排序题居然没有,悲催,太低级了,最后在 hdu 上找到一个排序题,http://acm.hdu.edu.cn/showprob…

忘得差不多也有一个好处,就是可以自己从头再想,这次决定不看任何参考资料,就凭着模糊的印象,慢慢的把算法的思路先理清楚,然后动手写,再手工调,一点点来,这样才能更好的理解,悲催的是,一个冒泡排就搞了一个上午啊

#include <stdio.h>
#define MAX 1005

int get(int arr[])
{
	int n, i;
	scanf("%d", &n);
	for (i=0; i<n; i++)
	{
		scanf("%d", &arr[i]);
	}
	return n;
}

void print(int arr[], int n)
{
	printf("%d", arr[0]);
	int i;
	for (i=1; i<n; i++)
	{
		printf(" %d", arr[i]);
	}
	printf("n");
}

void sort(int arr[], int n)
{
	int i, j;
	for (i=0; i<n-1; i++)
	{
	//	printf("processing arr[%d]:%dn", i, arr[i]);
		for (j=0; j<n-i-1; j++)
		{
		//	printf("checking for arr[%d]:%d and arr[%d]:%dn",
		//		j, arr[j], j+1, arr[j+1]);
			if (arr[j] > arr[j+1])
			{
			//	printf("swapping arr[%d]:%d and arr[%d]:%dn",
			//		j, arr[j], j+1, arr[j+1]);
				int temp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = temp;
			//	print(arr, n);
			}
		}
	}
//	printf("donen");
	return;
}

int main()
{
	int t;
	scanf("%d", &t);
	while (t--)
	{
		int arr[MAX] = {0};
		int n = get(arr);
		sort(arr, n);
		print(arr, n);
	}
	return 0;
}

遇到的问题在于,看高亮的第 32 行,如果把 for 循环的初始条件从 j=0 改成 j=i 就 WA 了,这是为什么呢,有兴趣的可以自己想想

冒泡排序出来了,选择也跟着很快就出来了

#include <stdio.h>
#define MAX 1005

int get(int arr[])
{
	int n, i;
	scanf("%d", &n);
	for (i=0; i<n; i++)
	{
		scanf("%d", &arr[i]);
	}
	return n;
}

void print(int arr[], int n)
{
	printf("%d", arr[0]);
	int i;
	for (i=1; i<n; i++)
	{
		printf(" %d", arr[i]);
	}
	printf("n");
}

void sort(int arr[], int n)
{
	int i, j;
	for (i=0; i<n-1; i++)
	{
		int min = i;
		for (j=i+1; j<n; j++)
		{
			if (arr[j] < arr[min])
			{
				min = j;
			}
		}
		if (min != i)
		{
			int temp = arr[i];
			arr[i] = arr[min];
			arr[min] = temp;
		}
	}
	return;
}

int main()
{
	int t;
	scanf("%d", &t);
	while (t--)
	{
		int arr[MAX] = {0};
		int n = get(arr);
		sort(arr, n);
		print(arr, n);
	}
	return 0;
}

选择排序是我觉得最自然,最好理解的排序方法,我记得当时大一的时候,刚接触 C ,什么都没学,自己琢磨出来的就是选择,倒是冒泡还费劲理解。。

Leave a Reply

Your email address will not be published. Required fields are marked *