C 排序问题
发布网友
发布时间:2022-05-15 04:41
我来回答
共3个回答
热心网友
时间:2022-05-22 02:53
排 序:
程序员可以使用的基本排序算法有5种:
·插入排序(insertionsort.)
·交换排序(exchangesOrt)
·选择排序(selectionsort)
·归并排序(mergesort)
·分布排序(distributionsort)
为了形象地解释每种排序算法是怎样工作的,让我们来看一看怎样用这些方法对桌上一付乱序的牌进行排序。牌既要按花色排序(依次为梅花、方块、红桃和黑心),还要按点数排序(从2到A)。
插入排序的过程为:从一堆牌的上面开始拿牌,每次拿一张牌,按排序原则把牌放到手中正确的位置。桌上的牌拿完后,手中的牌也就排好序了。
交换排序的过程为:
(1)先拿两张牌放到手中。如果左边的牌要排在右边的牌的后面,就交换这两张牌的位置。
(2)然后拿下一张牌,并比较最右边两张牌,如果有必要就交换这两张牌的位置。
(3)重复第(2)步,直到把所有的牌都拿到手中。
(4)如果不再需要交换手中任何两张牌的位置,就说明牌已经排好序了;否则,把手中的牌放到桌上,重复(1)至(4)步,直到手中的牌排好序。
选择排序的过程为:在桌上的牌中找出最小的一张牌,拿在手中;重复这种操作,直到把所有牌都拿在手中。
归并排序的过程为:把桌上的牌分为52堆,每堆为一张牌。因为每堆牌都是有序的(记住,此时每堆中只有一张牌),所以如果把相邻的两堆牌合并为一堆,并对每堆牌进行排序,就可以得到26堆已排好序的牌,此时每一堆中有两张牌。重复这种合并操作,就可以依次得到13堆牌(每一堆中有4张牌),7堆牌(有6堆是8张牌,还有一堆是4张牌),最后将得到52张的一堆牌。
分布排序(也被称作radix sort,即基数排序)的过程为:先将牌按点数分成13堆,然后将这13堆牌按点数顺序叠在一起;再将牌按花色分成4堆,然后将这4堆牌按花色顺序叠在一起,牌就排好序了。
在选用排序算法时,你还需要了解以下几个术语:
(1)自然的(natural)
如果某种排序算法对有序的数据排序速度较快(工作量变小),对无序的数据排序速度却较慢(工作变量大),我们就称这种排序算法是自然的。如果数据已接近有序,就需要考虑选用自然的排序算法。
(2)稳定的(stable)
如果某种排序算法能保持它认为相等的数据的前后顺序,我们就称这种排序算法是稳定的。
例如,现有以下名单:
Mary Jones
Mary Smith
Tom Jones
Susie Queue
如果用稳定的排序算法按姓对上述名单进行排序,那么在排好序后"Mary Jones”和"Tom Jones”将保持原来的Jr顺序,因为它们的姓是相同的。
稳定的排序算法可按主、次关键字对数据进行排序,例如按姓和名排序(换句话说,主要按姓排序,但对姓相同的数据还要按名排序)。在具体实现时,就是先按次关键字排序,再按主关键字排序。
(3)内部排序(internal sort)和外部排序(external sort)
待排数据全部在内存中的排序方法被称为内部排序,待排数据在磁盘、磁带和其它外存中的排序方法被称为外部排序。
查 找:
和排序算法一样,查找(searching)算法也是计算机科学中研究得最多的问题之一。查找算法和排序算法是有联系的,因为许多查找算法依赖于要查找的数据集的有序程度。基本的查找算法有以下4种:
·顺序查找(sequential searching)。
·比较查找(comparison searching)
·基数查找(radix searching)
·哈希查找(hashing)
下面仍然以一付乱序的牌为例来描述这些算法的工作过程。
顺序查找的过程为:从第一张开始查看每一张牌,直到找到要找的牌。
比较查找(也被称作binarysearching,即折半查找)要求牌已经排好序,其过程为:任意抽一张牌,如果这张牌正是要找的牌,则查找过程结束。如果抽出的这张牌比要找的牌大,则在它前面的牌中重复查找操作;反之,则在它后面的牌中重复查找操作,直到找到要找的牌。
基数查找的过程为:先将牌按点数分成13堆,或者按花色分成4堆。然后找出与要找的牌的点数或花色相同的那一堆牌,再在这堆牌中用任意一种查找算法找到要找的牌。
哈希查找的过程为:
(1)在桌面上留出可以放若干堆牌的空间,并构造一个函数,使其能根据点数和花色将牌映射到特定的堆中(这个函数被称为hashfunction,即哈希函数)。
(2)根据哈希函数将牌分成若干堆。
(3)根据哈希函数找到要找的牌所在的堆,然后在这一堆牌中找到要找的牌。
例如,可以构造这样一个哈希函数:
pile=rank+suit
其中,rank是表示牌的点数的一个数值;suit是表示牌的花色的一个数值;pile表示堆值,它将决定一张牌归入到哪一堆中。如果用1,2,……,13分别表示A,2,…….K,用0,1,2和3分别表示梅花、方块、红桃和黑桃,则pile的值将为1,2,……,16,这样就可以把一付牌分成16堆。
哈希查找虽然看上去有些离谱,但它确实是一种非常实用的查找算法。各种各样的程序,从压缩程序(如Stacker)到磁盘高速缓存程序(如SmartDrive),几乎都通过这种方法来提高查找速度,
排序或查找的性能:
有关排序和查找的一个主要问题就是速度。这个问题经常被人们忽视,因为与程序的其余部分相比,排序或查找所花费的时间几乎可以被忽略。然而,对大多数排序或查找应用来说,你不必一开始就花很多精力去编制一段算法程序,而应该先在现成的算法中选用一种最简单的(见3.1和3.4),当你发现所用的算法使程序运行很慢时,再换用一种更好的算法(请参见下文中的介绍)。
下面介绍一种判断排序或查找算法的速度的方法。
首先,引入一个算法的复杂度的概念,它指的是在各种情况(最好的、最差的和平均的)下排序或查找需要完成的操作次数,通过它可以比较不同算法的性能。
算法的复杂度与排序或查找所针对的数据集的数据量有关,因此,引入一个基于数据集数据量的表达式来表示算法的复杂度。
最快的算法的复杂度O(1),它表示算法的操作次数与数据量无关。复杂度O(N)(N表示数据集的数据量)表示算法的操作次数与数据量直接相关。复杂度O(logN)介于上述两者之间,它表示算法的操作次数与数据量的对数有关。复杂度为O(NlogN)(N乘以logN)的算法比复杂度为O(N)的算法要慢,而复杂度为O(N2)的算法更慢。
注意:如果两种算法的复杂度都是O(logN),那么logN的基数较大的算法的速度要快些,在本章的例子中,logN的基数均为10
热心网友
时间:2022-05-22 04:11
我这里用的是简单选择排序
其实思想和冒泡基本一致,沿用前面回答者的答案稍作改动
冒泡思想:相邻两个比较
简单选择排序思想:
1号 与 2号 比较→if(1>2)换位
1号 与 3号 比较→if(1>3)换位
1号 与 4号 比较→if(1>4)换位
#include <stdio.h>
#define N 10
int main()
{
int i,j,k,temp;
int a[N];
for(i=1;i<N;i++)//我从第a[1]个开始存数的,注意输入数字个数
scanf("%d",&a[i]);
for(j=1;j<N;j++)
{
k=j;
for (i=1;i<=N-j;i++)
if (a[j]>a[k+i])
{
temp=a[j];
a[j]=a[k+i];
a[k+i]=temp;
}
}
for(i=1;i<N;i++)
printf("%d ",a[i]);
printf("\n");
return 0;
}
热心网友
时间:2022-05-22 05:46
#include <stdio.h>
int main()
{
int i,j,temp;
int a[10];
for(i=0;i<10;i++)
scanf ("%d,",&a[i]);
for(j=0;j<=9;j++)
{ for (i=0;i<10-j;i++)
if (a[i]>a[i+1])
{ temp=a[i];
a[i]=a[i+1];
a[i+1]=temp;}
}
for(i=1;i<11;i++)
printf("%5d,",a[i] );
printf("\n");
return 0;
}追问大哥 两个啊 。一个选择排序 一个 冒泡排序