排序6(线性时间排序)

  今天看了《算法导论》第八章,这一章介绍了三种排序的思路:计数排序,基数排序,还有桶排序。
  计数排序,就是用一个辅助数组记录每一个数的出现次数。然后,把数挨着放进去,排序。这不是一个排序算法,因为元素之间没有存在比较。计数排序比较稳定,常作为基数排序的一个子过程。
  基数排序,一种老式穿卡机上的算法,就是在多位数中,排序从低位到高位排序,这让我想起对年月日进行排序,用这种方法绝对不错。先对日,再对月,最后对年进行排序。
  桶排序,就是在一个小范围内的输入,不能太大,就是存储有点类似于hash吧!不过hash是随机的,这个是按顺序存储的。形象上,就是摆一排顺序的桶,然后把数据按一定顺序落在桶中。整个桶排序算法就以线性期望时间运行。
  好了,以上三种算法都是以线性时间排序。都是用一些非比较的一些操作来确定排序的顺序。到目前为止,已经有了7种比较排序的方法,这三种还见的不太多(可能见识的少吧!)。觉得有用的还是基数排序的进行排日期的那种思维,这中思路还是值得借鉴的。

排序5(希尔排序)

  今天看了希尔排序,是在直接插入排序上的一种改进,缩小增量的排序。在时间效率上有了较大的改进。
  希尔排序就是用一个递减的序列对数据进行排序。增量序列的取法:没有除了1之外的公因子,而且最后一个元素是1。

#include<stdio.h>
void shellInsert(int *a,int k)
{
int i,j;
for(i=k+1;i<=10;i++)
{
if(a[i]0 && a[0]<a[j];j-=k)
a[j+k]=a[j];
a[j+k]=a[0];
}
}
return;
}
void shellSort(int *a,int *zeng,int t)
{
int k;
for(k=0;k<t;k++)
shellInsert(a,zeng[k]);
return;
}
int main()
{
int i,a[11]={0,4,5,7,8,1,9,3,6,11,2};
int zeng[3]={5,3,1};
shellSort(a,zeng,3);
for(i=1;i<11;i++)
printf(“%d “,a[i]);
printf(“\n”);
return 0;
}

排序4(快速排序–冒泡的改进)

  今天看了《算法导论》的第七章快速排序。
  首先选择一个记录(通常选择第一个)最为枢轴(pivot)(自己理解为用作比较的关键字)。
  其次,开始进行排序,先进行一趟排序,然后进行递归式的排序。
  在一趟排序的时候,还有两种思维的方法:①(注释的partition)直接把比pivot小的移动在低位,把比pivot大的移动在高位,最后了,把pivot放进去。②设立三个指向东西的i,j,p。p是记录低位,不动。j是遍历,i记录低位段的最高位,最后了,再把pivot查到地位段和高位段的中间。
  继续进化:
  当对一个随机的输入数组应用快速排序时,要想在每一层上都有同样的划分是不太可能的。这样每一次的pivot都是第一个元素的话,就会使某些划分比较对称,另一些很不对称。一个好的解决方法:把pivot随机化,这样我们就在期望平均的情况下,对输入数组进行划分能够比较的对称。
  随机化版本的快速排序是对足够大的输入的理想选择。

#include<stdio.h>
void swap(int *a,int *b)
{
int t;
t=*a;
*a=*b;
*b=t;
return;
}
int partition(int * a,int p ,int r)
{
int x=a[r],i=p-1,j;
for(j=p;j<=r-1;j++)
{
if(a[j]<=x)
{
i=i+1;
swap(&a[i],&a[j]);
}
}
swap(&a[i+1],&a[r]);
return i+1;
}
/*int partition(int * a,int low ,int high)
{
int pivot;
a[0]=a[low];
pivot=a[low];
while(low<high)
{
while(low= pivot )
–high;
a[low]=a[high];
while(low ++low;
a[high]=a[low];
}
a[low]=a[0];
return low;
}*/
void quickSort(int *a,int low,int high)
{
int pivot;
if(low<high)
{
pivot=partition(a,low,high);
quickSort(a,low,pivot-1);
quickSort(a,pivot+1,high);
}
return;
}
int main()
{
int i,a[11]={0,4,5,7,8,1,9,3,6,11,2};
quickSort(a,1,10);
for(i=1;i<11;i++)
printf(“%d “,a[i]);
printf(“\n”);
return 0;
}

排序3(堆排序)

  端午节快乐!今天再看一个算法。
  堆排序是采用顺序存储表示,用一个数组表示,但是逻辑上是一个堆,用堆的思维进行排序。
  首先,先建立一个大顶堆(maxHeapFather),就是每一个父亲都比子女的数值大。遍历的每一个元素都确定自己的儿子(包括孙子、重孙子)都是一个大顶堆,
  其次,开始建一个堆,遍历n/2个点后,就成了一个最大的大顶堆。然后进行排序,把顶部的最大数与最后一个数进行调换,之后再把n-1个数,在进行堆排序,一直重复到最后,就成了一个有序的队列。
  算法分析:堆排序方法对记录少的文件效率不高,主要是n很大的文件上,因为运行时间主要花在了建初始的大堆和建新堆时的反复“筛选”上!对深度为k的堆,筛选算法中进行的关键字比较次数最多为2(k-1)次,则在建含有n个元素、深度为h的堆时,总共进行的关键字比较次数不超过4n次。在最坏的情况下,其时间复杂度也为O(nlgn)
  总结反思:
  注意1:在调试的过程中,堆顶应该从1开始,这样左边的树=2*i,右边的树为2*i+1。
  注意2:什么叫伪码?就是非常不能运行的语言。还是自己的功底不行吧,在内容的实现方面还是有点卡壳,伪码与实现的距离很远啊!

#include<stdio.h>
#define PARENT(i) ((i)/2)
#define LEFT(i) (2*i)
#define RIGHT(i) (2*i+1)
static heapSize=10;

void maxHeapFather(int * a,int i)
{
int l=LEFT(i);
int r=RIGHT(i);
int largest=i,t;
if(la[i])
largest=l;
if(ra[largest])
largest=r;
if(largest!=i)
{
t=a[i];
a[i]=a[largest];
a[largest]=t;
maxHeapFather(a,largest);
}
return;
}
void buildMaxHeap(int *a)
{
int i;
for(i=heapSize/2;i>=1;i–)
maxHeapFather(a,i);
return;
}
void heapSort(int *a)
{
int i,t;
buildMaxHeap(a);
for(i=heapSize;i>1;i–)
{
t=a[1];
a[1]=a[i];
a[i]=t;
heapSize–;
maxHeapFather(a,1);
}
}
int main()
{
int i,a[11]={0,4,5,7,8,1,9,3,6,11,2};
heapSort(a);
for(i=1;i<11;i++)
printf(“%d “,a[i]);
printf(“\n”);
return 0;
}

排序2(递归归并排序)

  今天继续看了《算法导论》的第二章,的确讲的有点深,花费了不少的时间实现了递归归并排序,好了,长话短说,先分析一下:
  递归归并排序需要和得排序记录等长的空间,需要的时间是n lg n。因为对数的增长速度比任何线性函数增长的都慢,当输入的规模大时,合并排序在最坏的情况下都要比(插入||冒泡||选择)快!
时间的算法思路:假设是满树,共2的n次方个,那么递归树就是lgn+1层,每一层花费的代价都是cn,所以总共用的时间是cn(lgn+1)=cnlgn+cn,忽略低阶项和常量,就是nlgn了。

  反思:思想看懂了,用C写了一边之后,竟然没有成功,用VC6.0一步一步的调试,才发现原来递归调用中的for循环没有写对,这也是自己编程习惯的失误,命名简单结果遇到复杂的题时,那些abcijk的不知搞啥用了,结果就错了。以后得记住改正。
  总结到此,代码附上。
#include <stdio.h>
int b[10]={0};
void merge(int *sr,int i,int m,int n)
{
int al,ar,k,j;
for(ar=m+1,al=i,k=i;al<=m&&ar<=n;k++)
{
if(sr[al]<sr[ar])
b[k]=sr[al++];
else
b[k]=sr[ar++];
}
while(al<=m)
b[k++]=sr[al++];
while(ar<=n)
b[k++]=sr[ar++];
for(k=i,j=0;k<=n;j++,k++)
sr[i+j]=b[i+j];
return;
}
void mergeSort(int *sr,int s,int t)
{
int m;
if(s==t)
b[s]=sr[s];
else
{
m=(s+t)/2;
mergeSort(sr,s,m);
mergeSort(sr,m+1,t);
merge(sr,s,m,t);
}
return;
}
int main()
{
int i,a[10]={4,5,7,8,1,9,3,6,11,2};
mergeSort(a,0,9);
for(i=0;i<10;i++)
printf(“%d “,a[i]);
printf(“\n”);
return 0;
}

链表1(链表节点的交换)

  今天遇见一个问题,就是链表排序的时候,节点如何交换。方法很多种,最优的一种:一个函数实现如何用一个指针参数,实现交换。看了好几遍才看懂,代码粘贴上,仔细的分析一下:
void swap_node(stu_t * p)
{
stu_t * tmp = p->next;
p->next = p->next->next;
tmp->next = p->next->next;
p->next->next = tmp;
return;
}

——>①——>②——>③——>④——

这是一个完整的链表,现在要交换②③,P指针指向①。

tmp
  ↘
——>①——>②——>③——>④——

声明一个临时变量tmp,使tmp指向②,此时tmp中存储着②的地址

tmp
  ↘
——>①   ②——>③——>④——
   |       ↑
   ———————

使①的next指向③

tmp       ____________
  ↘     |       ↓
——>①    ②   ③——>④——
    |       ↑
    ————————

使②的next指向④,此时②用tmp找到的,④是通过①找到

tmp        ______________
↘        |        ↓
——>①    ②<——③    ④——
    |        ↑
    ———————

最后,使③指向②,③用p->next找到,就是把③中的next的值,等于②的地址,②的地址存储在tmp中。

排序1(直接插入排序)

  今天看《算法导论》,出现的第一个算法,直接插入排序,我就试着实现了一下,思路也能看懂,但是实现起来,还是费了不少的力气,实现出来之后,还发现一个问题,在VC下面运行正常,在Mac下面就出现了错误。
  总是搞不明白,后来发现了,原来是数组的下标越界造成的,访问了一个不存在的元素,在Mac下面是0,在VC下面是未知的很大的数,结果VC下面看着冒死很正确 @_@ !
  把代码给写出来,经过gcc vision4.2.1 && VC6.0测试通过。
#include <stdio.h>
void insertSort(int * a)
{
int i,j,flag=a[0];
for(i=1;i<10;i++)
{
if(a[i]<a[i-1])
{
flag=a[i];
for(j=i;flag<a[j-1]&&j-1>=0;j--)
a[j]=a[j-1];
a[j]=flag;
}
else
flag=a[i];
}
return;
}
int main()
{
int a[10]={1,7,9,4,5,2,3,11,8,6};
int i;
insertSort(a);
for(i=0;i<10;i++)
printf("%d ",a[i]);
printf("\n");
return 0;
}