计算智能1

一。问题重述：

定义一个n个元素的一维数组，输出较小的k个数。

二。算法设计思路：

快速排序思路：

（1） 如果不多于1个数据，直接返回。

（2） 一般选择序列最左边的值作为支点数据。

（3） 将序列分成2部分，一部分都大于支点数据，另外一部分都小于支点数据。

（4） 对两边利用递归排序数列。

堆排序思路：

堆排序会将所有的数据建成一个堆，最大的数据在堆顶，然后将堆顶数据和序列的最后一个数据交换。接下来再次重建堆，交换数据，依次下去，就可以排序所有的数据。

三。算法描述：

1.快速排序：

#include

#include

#include

int pivotkey,pivotloc;

int partition(int r[],int low,int high)

{

r[0]=r[low];

pivotkey=r[low];

while(low

while(low=pivotkey)

--high;

r[low]=r[high];

while(low

++low;

r[high]=r[low];

}

r[low]=r[0];

return low;

}

void quick_sort(int r[],int low,int high)

{

if(low

{

pivotloc=partition(r,low,high);

quick_sort(r,low,pivotloc-1);

quick_sort(r,pivotloc+1,high);

}

}

void main()

{

printf("规定输入n个元素，输出较小k个的个数：");

int n,k;

scanf("%d %d",&n,&k);

printf("输入元素值：");

int*p,i,r[100];

p=r;

for(i=0;i

scanf("%d",++p);

p=r;

quick_sort(r,1,n);

for(p=r,i=0;i

{printf("%d ",*++p);}

}

2.堆排序：

#include

#include

#include

void heap_adjust(int h[],int l,int m)

{

int j,x=h[l]; //假设根 h[l]

for(j=2*l;j<=m;j*=2) //根的左孩子 h[2*l]

{ //根的右孩子 h[2*l+1]

if(j

j++; //j 指向右孩子

if(x

{

h[l]=h[j]; //移到根位置

l=j; //l 指向大值

}

else

break;

} //最后l指向最大元素

h[l]=x; //h[l] = root node

}

void heap_sort(int h[],int i)

{

int m;

m=h[i];

h[i]=h[1];

h[1]=m;

heap_adjust(h,1,i-1);

}

void main()

{

printf("规定输入n个元素，输出较小k个的个数：");

int n,k;

scanf("%d %d",&n,&k);

printf("输入元素值：");

int*p,i,h[100];

p=h;

for(i=0;i

scanf("%d",++p);

p=h;

for(i=n/2;i>=1;i--)

heap_adjust(h,i,n); //i: n/2 --> 1

for(i=n;i>=2;i--) //i: n --> 2

heap_sort(h,i);

for(p=h,i=0;i

{printf("%d ",*++p);}

}

四。时空效率：均为O(nlogn)

五。遇到的问题与解决方法：

1.思索用哪种排序方法：遇到遗忘问题，解决方法便是复习过去的知识。

2.在编程中遇到很多error:慢慢排查

3．快速排序法输出时总会把枢轴的值也输出，于是把i的值从0改为1，把指针p的值也相应做了调整。

六。体会

刚一看题觉得比较简单，然后顺手就用了选择排序法，程序和算法思路以及遇到的问题如下：

1.算法思路：

开辟一个数组空间，让用户输入n个元素，并让用户决定输出较小的k个数。建立子函数voidsort(int x[],int n)，用选择排序法从小到大排列n个数,把重新排列顺序的n个数传回到主函数，输出较小的k个数。

2.算法描述：

#include

#include

#include

void main()

{void sort(intx[],int n);

printf("规定输入n个元素，输出较小k个的个数：");

int s,t;

scanf("%d,%d",&s,&t);

printf("输入元素值：");

int *p,i,a[100];

p=a;

for(i=0;i

scanf("%d",p++);

p=a;

sort(p,s);

for(p=a,i=0;i

{printf("%d ",*p);p++;}

}

void sort(intx[],int n)

{int i,j,k,t;

for(i=0;i

{k=i;

for(j=i+1;j

if(x[j]

if(k!=i)

{t=x[i];x[i]=x[k];x[k]=t;}

}

}

3.算法分析：

时空复杂度：O（n）= 1+ 1 +3n+2 + 1 +1 + 1 + 10*(n-2)+1+1+ 1 +3k+1= 13n-9 +3k=O(n)

4.遇到问题和解决方法

遇到问题：程序不出结果

解决方法：仔细检查程序无误，发现输入k和n值时忘了加“，” 而是直接用了空格造成没有成功赋值。

然后，直到听了老师的提醒，才想到要去思考程序的优越问题。

要想成功输出较小的k个数比较简单，但要想做到时空效率都最低的优秀程序却很难。所以思考用哪种存储方式以及哪种排序方式便成了久久思索的问题。于是我回顾了以前所学的知识。

由数据结构所学知识得知：

排序法 平均时间 最差情形 稳定度 额外空间 备注

冒泡 O(n2) O(n2) 稳定 O(1) n小时较好

交换 O(n2) O(n2) 不稳定 O(1) n小时较好

选择 O(n2) O(n2) 不稳定 O(1) n小时较好

插入 O(n2) O(n2) 稳定 O(1) 大部分已排序时较好

基数 O(logRB) O(logRB) 稳定 O(n) B是真数(0-9)，

R是基数(个十百)

Shell O(nlogn) O(ns) 1

快速 O(nlogn) O(n2) 不稳定 O(nlogn) n大时较好

归并 O(nlogn) O(nlogn) 稳定 O(1) n大时较好

堆 O(nlogn) O(nlogn) 不稳定 O(1) n大时较好

知识点回顾：

冒泡排序是最慢的排序算法。在实际运用中它是效率最低的算法。

交换排序（ExchangeSort）和选择排序（SelectSort）这两种排序方法都是交换方法的排序算法，效率都是 O(n2)。在实际应用中处于和冒泡排序基本相同的地位。它们只是排序算法发展的初级阶段，在实际中使用较少。

快速排序比大部分排序算法都要快。尽管我们可以在某些特殊的情况下写出比快速排序快的算法，但是就通常情况而言，没有比它更快的了。快速排序是递归的，对于内存非常有限的机器来说，它不是一个好的选择。

归并排序比堆排序稍微快一点，但是需要比堆排序多一倍的内存空间，因为它需要一个额外的数组。

堆排序适合于数据量非常大的场合（百万数据）。堆排序不需要大量的递归或者多维的暂存数组。这对于数据量非常巨大的序列是合适的。比如超过数百万条记录，因为快速排序，归并排序都使用递归来设计算法，在数据量非常大的时候，可能会发生堆栈溢出错误。

Shell排序比冒泡排序快5倍，比插入排序大致快2倍。Shell排序比起QuickSort，MergeSort，HeapSort慢很多。但是它相对比较简单，它适合于数据量在5000以下并且速度并不是特别重要的场合。它对于数据量较小的数列重复排序是非常好的。

在复习中我发现快速排序和堆排序是速度最快且性能较好的。

花费了很长时间复习，思考，编程，不过在学习过程中还是感觉有所收获的，很高兴能开计算智能这门课，让学习形式变得更丰富的同时也培养了兴趣和锻炼了能力。其实一直对编程很苦手，不过希望这学期能够一直坚持好好思考好好编程。