排序

发表于 | 更新于: | 分类于 | 阅读次数: |
字数统计: 573 字 | 阅读时长 ≈ 2 分钟

c刚看到数组，只会写个简单的冒泡排序。发现自己还真是菜，抱着ljr老师的算法书半天都看不懂，没办法只能自己慢慢啃了。

算法原理(摘自百度百科)

  1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
  2. 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
  3. 针对所有的元素重复以上的步骤，除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

下面用python实现

1
2
3
4
5
6
7
8
def bubble_sort(nums):
    n = len(nums)
    for i in range(1,n):  # n个数，比较n-1趟
        for j in range(n - i):#n个数，去掉最后面排好序的(i-1)个数，剩余n-i+1个数比较n-1次，[0,n-i-1]每次判断到下标j=n-1-i即可，因为前闭后开，所以要+1
            if nums[j] > nums[j + 1]:
                nums[j], nums[j + 1] = nums[j + 1], nums[j]
    return nums
print(bubble_sort([1,4,5,3]))

下面用c实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<stdio.h>
#define maxn 100000
int a[maxn];
int main()
{
	int x,n=0;
	while(scanf("%d",&x)==1) a[n++]=x;//最后一次n又加1,所以,数组下标0到n-1 ,n个数 
	for(int i=1;i<=n-1;i++)//n个数,比较(n-1)趟
	{
		for(int j=0;j<=n-i-1;j++)//n个数,去掉最后面(i-1)个数,剩余n-i+1个数比较n-i次.每次判断到下标j=n-1-i即可 
		{
			if(a[j]>a[j+1]) 
			{
				a[j] = a[j]+a[j+1];
				a[j+1] = a[j]-a[j+1];
				a[j]=a[j]-a[j+1];
			}
		 } 
	}
	for(int i=0;i<=n-1;i++)printf("%d ",a[i]);
	return 0;	
}

学会选择法排序了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <stdio.h>
void sort(int *pa,int n)
{
	int index,i,k,temp;
	for(k=0;k<n-1;k++)
	{
		index=k;
		for(i=k+1;i<n;i++)
		{
			if(pa[i]<pa[index])index=i;
		}
		if(index!=k)
		{
			temp=pa[index];
			pa[index]=pa[k];
			pa[k]=temp;
		}
	}
	
}
int main()
{
	int n,i;
	scanf("%d",&n);
	int a[n];
	for(i=0;i<=n-1;i++)scanf("%d",&a[i]);
	sort(a,n);
	for(i=0;i<=n-1;i++)printf("%d ",*(a+i));
	return 0;
}