数据结构排序算法总结（数据结构各种排序方法总结）

本篇文章给大家谈谈数据结构排序算法总结，以及数据结构各种排序方法总结对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。

本文目录一览：

• 1、谁教我：数据结构的各种排序
• 2、数据结构 java开发中常用的排序算法有哪些
• 3、面试经典数据结构和算法汇总
• 4、数据结构的排序方法有哪些？
• 5、数据结构复习总结第八章排序

谁教我：数据结构的各种排序

1.快速排序

#include"stdio.h"

#define N 100

int a[N]={0};//存放要排序的数

int Qsort(int m,int n)//对数组中m到n的元素进行快速排序

{

int p,q;

int head,sign;

if(m!=n)//选定的数列不止一个元素

{

head=a[n];//选择数列的末尾元素作为比较元素

p=m;//p标记数列的首元素

q=n-1;//标记末尾元素的前一个元素

sign=n;//记录比较元素的位置，以其作为空位置

while(p=q)//分别比较p、q所标记的元素与比较元素的大小，比其小的放在左边，比其大的放在右边

{

while(a[p]head)//p所指元素比比较元素小，p右移

{

p++;

if(pq)

{

break;

}

}

a[sign]=a[p];//将p所指元素移入空位置

sign=p;//记录空余位置

p++;

if(pq)

{

break;

}

while(a[q]head)//q所指元素比比较元素大，q左移

{

q--;

if(pq)

{

break;

}

}

a[sign]=a[q];

sign=q;

q--;

}

a[sign]=head;//比较完成后，将比较元素移入空位置

if(sign-1m)

{

Qsort(m,sign-1);//对m到sign-1的数列进行排序

}

if(sign+1n)

{

Qsort(sign+1,n);//对sign+1到n的数列进行排序

}

}

return(1);

}

int Print(int m,int n)//对m到n的数组序列输出

{

int i;

for(i=m;i=n;i++)

{

printf("%d\n",a[i]);

}

return(1);

}

int main()

{

int n,i;

scanf("%d",n);//输入将要排序的数的个数

for(i=0;in;i++)

{

scanf("%d",a[i]);//输入要排序的数

}

Qsort(0,n-1);

Print(0,n-1);

}

二、 详细设计：重要函数中的算法设计，实现流程，传递参数的说明；

三、调试分析与心得体会：

快速排序的思想时从数组序列中选定一个元素，将序列中其余元素与其进行比较，将比其小的放在左边，比其大的放在右边，然后以比较元素为中点，将序列分成两部分，再将它们分别进行快速排序，依次类推，直到序列中只有一个元素为止。

2.合并排序

#include"销银stdio.h"

#define N 10000

int a[N];//用a数组记录所给无序数列

int b[N]={0};//用b数组记录每次排序之后的a数组

int sign=0;

void Merge(int m,int mid,int n)//将两个有序数列合并成为一个有序数列

{

int i,j,k;

i=k=m;

j=mid+1;

while(i=midj=n)//依次比较两亏游宴个有序数列中的元素，从大到小将其放入b数组相应位置中

{

if(a[i]a[j])

{

b[k]=a[i];

k++;

i++;

}

else

{

b[k]=a[j];

k++;

j++;

}

}

if(i=mid)//将比较之后的剩余元素放入b数组相应位置

{

while(i=mid)

{

b[k]=a[i];

k++;

i++;

}

}

else

{

while(j=n)

{

b[k]=a[j];

k++;

j++;

}

}

for(i=m;i=n;i++)//将合并后的数列重新放入a数组相应位置

{

a[i]=b[i];

}

}

int Msort(int m,int n)//对所给无序数列磨伍进行排序

{

int mid;

if(n!=m)

{

mid=(n+m)/2; //将数列一分为二直到其只有一个元素

Msort(m,mid);

Msort(mid+1,n);

Merge(m,mid,n);//将分割后的数列重新合并起来

}

return(1);

}

void Print(int num)//将序列依次输出

{

int i;

for(i=0;inum;i++)

{

printf("%d\n",a[i]);

}

}

int main()

{

int sign;

int i;

int num;

scanf("%d",num);//输入将要排序的数的个数

for(i=0;inum;i++)

{

scanf("%d",a[i]);//依次输入要排序的数

}

sign=Msort(0,num-1);

Print(num);//输出完成排序后的有序数列

}

二、 详细设计：重要函数中的算法设计，实现流程，传递参数的说明；

三、调试分析与心得体会：

合并排序是排序的一种常用方法，其主要思想为：将一个无序数列依次分割直到其每个序列只有一个元素为止，然后再将两个序列合并为一个有序数列，依此类推。

3.我的数据结构实验课题（关于排序）

//问题描述：排序器

//要 求：实现以下六种排序算法，将给定的不同规模大小的数据文件（data01.txt，data02.txt，data03.txt，data04.txt）进行排序，

//并将排序结果分别存储到sorted01.txt，sorted02.txt，sorted03.txt和sorted04.txt文件中。

//1）、Shell排序； 2）、Quick排序

//3）、锦标赛排序； 4）、堆排序

//5）、归并排序； 6）、基数排序

//在实现排序算法1）~4）时，统计数据元素比较的次数和交换的次数，进而对这四种算法在特定数据条件下的效率进行分析和评判。

#include"stdio.h"

#include"math.h"

#include"stdlib.h"

#include"malloc.h"

#define Maxsize 10000000

#define N 20

#define EQ(a,b) ((a)==(b))

#define LT(a,b) ((a)(b))

#define LQ(a,b) ((a)=(b))

#define LEN sizeof(SqList)

#define Maxr 10

#define MAXNUM 100000000

typedef struct node{

int key;

int num;

};

typedef struct {

struct node r[Maxsize+1];

long length;

}SqList,*qSqList;

typedef struct node2{

struct node r;

struct node2 *next;

}RecType;

long shifttimes;//统计移动次数

long comparetimes;//统计比较次数

qSqList creat(char filename[])//读入文件并且将数据保存

{

FILE *fp;

long i;

qSqList L;

L=(qSqList)malloc(LEN);

L-length=0;

if((fp=fopen(filename,"r"))==NULL)//文件不存在时终止程序

{

printf("cannot open file\n");

exit(0);

}

for(i=1;iMaxsize+1;i++)

{

fscanf(fp,"%ld (%d)",(L-r[i].key),(L-r[i].num));

if(L-r[i].key0)

break;

L-length++;//记录读入的数据长度

}

fclose(fp);

return(L);

}

void Print2(qSqList L)//将序列输出到指定的文件中

{

long i;

FILE *fp;

char filename[N];

printf("\n\t请输入存储文件名：");

scanf("%s",filename);//输入将要储存的文件名

fp=fopen(filename,"w");

for(i=1;i=L-length;i++)//将链表中数据逐一写入文件中

{

fprintf(fp,"%d (%d)\n",L-r[i].key,L-r[i].num);

}

fclose(fp);

}

void Print(qSqList L)//打印数据个数以及排序过程中的比较次数和移动次数

{

printf("\n\t数据个数:%ld",L-length);

printf("\n\t比较次数:%ld",comparetimes);

printf("\n\t移动次数:%ld",shifttimes);

}

struct node Min1(struct node a,struct node b)//比较两接点关键字的大小

{

struct node temp;

if(a.keyb.key)

temp=b;

else

temp=a;

comparetimes++;

return(temp);

}

qSqList shellinsert(qSqList L,int dk)//对顺序表以dk为增量作直接插入排序

{

int i,j;

for(i=dk+1;i=L-length;i++)

{

if(LT(L-r[i].key,L-r[i-dk].key))//将L-r[i]插入到有序增量子表

{

L-r[0]=L-r[i];//将L-r[i]暂时存储在L-r[0]

shifttimes++;

for(j=i-dk;j0LT(L-r[0].key,L-r[j].key);j-=dk)//记录后移，查找插入位置

{

L-r[j+dk]=L-r[j];

comparetimes++;

shifttimes++;

}

if(j0)

comparetimes++;

L-r[j+dk]=L-r[0];//插入

shifttimes++;

}

comparetimes++;

}

// Print(L);

return(L);

}

qSqList shell(qSqList L)//希尔排序

{

int i,t=0;

int k;

for(t=0;LQ(pow(2,t),(L-length+1));t++);

t=t-1;

// printf("%d",t);

for(i=1;i=t;++i)

{

k=(int)pow(2,t-i+1)-1;//计算排序增量

L=shellinsert(L,k);

}

Print(L);

Print2(L);

return(L);

}

long Quicksort(qSqList L,long low,long high)//交换顺序表L中子表L-r[low..high]的记录，使枢轴记录到位，并返回其所在位置

{

int pivotkey;

pivotkey=L-r[low].key;//用序列的第一个记录作枢轴记录

while(lowhigh)//从表的两端交替地向中间扫描

{

while(lowhighL-r[high].key=pivotkey)//将比枢轴记录小的记录交换到低端

{

comparetimes++;

high--;

}

comparetimes++;

L-r[0]=L-r[low];

shifttimes++;

L-r[low]=L-r[high];

shifttimes++;

L-r[high]=L-r[0];

shifttimes++;

while(lowhighL-r[low].key=pivotkey)//将比枢轴记录大的记录交换到高端

{

comparetimes++;

low++;

}

comparetimes++;

L-r[0]=L-r[low];

shifttimes++;

L-r[low]=L-r[high];

shifttimes++;

L-r[high]=L-r[0];

shifttimes++;

}

return(low);//返回枢轴所在位置

}

qSqList Quick2(qSqList L,long low,long high)//对顺序表L中的子序列L.r[low..high]作快速排序

{

long pivot;

if(lowhigh)//序列长度大于1

{

pivot=Quicksort(L,low,high);//将序列一分为二

Quick2(L,low,pivot-1);//对低位子表递归排序

Quick2(L,pivot+1,high);//对高位子表递归排序

}

return(L);

}

qSqList Quick(qSqList L)//对顺序表作快速排序

{

long low,high;

low=1;//将第一个数据所在位置定义为低位

high=L-length;//将最后一个数据所在位置定义为高位

L=Quick2(L,low,high);//对顺序表作快速排序

Print(L);

Print2(L);

return(L);

}

void TourSort(SqList *L,long n)//锦标赛排序

{

qSqList Lp;

long i=0,t=1,k=1,w;

while(tn)//t表示完全二叉树的结点个数

{

t=(long)pow(2,i);

i++;

}

t=2*t;

Lp=(qSqList)malloc((sizeof(SqList)));

Lp-length=t-1;

for(i=t-1;i=t/2;i--)

{

if(kn)

Lp-r[i].key=MAXNUM;

else

{

Lp-r[i]=L-r[k];

}

shifttimes++;

k++;

}

i=t-1;

while(i!=1)

{

Lp-r[i/2]=Min1(Lp-r[i],Lp-r[i-1]);

i-=2;

comparetimes++;

shifttimes++;

}

for(i=1;i=n;i++)

{

L-r[i]=Lp-r[1];

shifttimes++;

w=1;

while(wt/2)

{

if(Lp-r[2*w].key==Lp-r[w].key)

w*=2;

else

w=2*w+1;

}

Lp-r[w].key=MAXNUM;//将其赋为最大值

shifttimes++;

if(w%2)

Lp-r[w/2]=Lp-r[w-1];

else

Lp-r[w/2]=Lp-r[w+1];

shifttimes++;

while(w!=1)

{

if(w%2)

Lp-r[w/2]=Min1(Lp-r[w],Lp-r[w-1]);

else

Lp-r[w/2]=Min1(Lp-r[w],Lp-r[w+1]);

comparetimes++;

shifttimes++;

w/=2;

}

}

Print(L);

Print2(L);

}

void Heapadjust(qSqList L,long s,long m)//调整L-[s]的关键字，使L-r[s..m]成为一个大顶堆

{

long j;

struct node rc;

rc=L-r[s];

for(j=2*s;j=m;j*=2)//沿key较大的接点向下筛选

{

if(jmLT(L-r[j].key,L-r[j+1].key))//j为key较大的记录的下标

{

j++;

comparetimes++;

}

if(!LT(rc.key,L-r[j].key))

{

comparetimes++;

break;

}

L-r[s]=L-r[j];//rc插入位置s

shifttimes++;

s=j;

}

L-r[s]=rc;//插入

shifttimes++;

}

qSqList Heap(qSqList L)//堆排序

{

long i;

for(i=L-length/2;i0;--i)//把L建成大顶堆

Heapadjust(L,i,L-length);

for(i=L-length;i1;--i)//将堆顶记录和当前未经排序子序列中最后一个记录交换

{

L-r[0]=L-r[1];

L-r[1]=L-r[i];

L-r[i]=L-r[0];

shifttimes=shifttimes+3;

Heapadjust(L,1,i-1);//将L重新调整为大顶堆

}

Print(L);

Print2(L);

return(L);

}

void Merge(qSqList L,int low,int m,int high)//将两个有序表R[low..m]he R[m+1..high]归并为一个有序表R[low,high]

{

int i=low,j=m+1,k=0;//k是temp的下标，i,j分别为第1，2段的下标

struct node *temp;

temp=(struct node*)malloc((high-low+1)*sizeof(struct node));//用于临时保存有序序列

while(i=mj=high)//在第1段和第2段均未扫描完时循环

{

if(LT(L-r[j].key,L-r[i].key))//将第1段中的记录放入temp中

{

temp[k]=L-r[j];

j++;

k++;

}

else//将第2段中的记录放入temp中

{

temp[k]=L-r[i];

k++;

i++;

}

}

while(i=m)//将第1段余下的部分复制到temp

{

temp[k]=L-r[i];

k++;

i++;

}

while(j=high)//将第2段余下的部分复制到temp

{

temp[k]=L-r[j];

k++;

j++;

}

for(k=0,i=low;i=high;i++,k++)//将temp复制回L中

{

L-r[i]=temp[k];

}

}

void MSort(qSqList L,int low,int high)//二路归并排序

{

int m;

if (lowhigh)

{

m=(low+high)/2;

MSort(L,low,m);

MSort(L,m+1,high);

Merge(L,low,m,high);

}

}

void Merging(qSqList L)//归并排序

{

MSort(L,1,L-length);

Print2(L);

}

void Radixsort(qSqList L)//基数排序

{

int g,i,j,k,d=2;

struct node2 *p,*s,*t,*head[10],*tail[10];//定义各链队的首尾指针

for(i=1;i=L-length;i++) //建立链表

{

s = (struct node2*)malloc(sizeof(struct node2));

s-r.key = L-r[i].key;

s-r.num= L-r[i].num;

if(i==1)

{

t = s;

p = s;

g++;}

else

{

t-next = s;

t = s;

g++;

}

t-next = NULL;

}

d=1;

for(i=1;i6;i++)

{

for(j=0;j10;j++)

{head[j] = tail[j] = NULL;} //初始化各链队首、尾指针

while(p!=NULL)//对于原链表中的每个结点循环

{

k = p-r.key/d;

k = k%10;

if(head[k]==NULL)//进行分配

{

head[k]=p;

tail[k]=p;

}

else

{

tail[k]-next=p;

tail[k]=p;

}

p = p-next;//取下一个待排序的元素

}

p=NULL;

for(j=0;j10;j++)//对每一个链队循环

{

if(head[j]!=NULL)//进行搜集

{

if(p == NULL)

{

p = head[j];

t = tail[j];

}

else

{

t-next=head[j];

t = tail[j];

}

}

}

t-next=NULL;//最后一个结点的next置为空

d=d*10;

}

i=1;

while(p!=NULL)

{

L-r[i] = p-r;

i++;

p=p-next;}

Print2(L);

}

char chmenu()//对排序方法进行选择

{

char ch;

printf("\n\t请选择排序方法:"

"\n\t*************"

"\n\t1.Shell排序"

"\n\t2.Quick排序"

"\n\t3.锦标赛排序"

"\n\t4.堆排序"

"\n\t5.归并排序"

"\n\t6.基排序"

"\n\t7.结束"

"\n\t*************");

do{

printf("\n\tplease choose (1-7):");

getchar();

ch=getchar();

}while(!(ch'0'ch'8'));

return(ch);

}

void main()

{

int a=1;

FILE *fp;

char ch,filename[N];

qSqList L;

while(a)

{

printf("\n\t请输入读入文件名:");//输入要读入的文件名

scanf("%s",filename);

if((fp=fopen(filename,"r"))==NULL)

{

printf("cannot open the file\n");

exit(0);

}

L=creat(filename);

while(1)

{

if((ch=chmenu())=='7')

break;

switch(ch)

{

case'1':{shifttimes=comparetimes=0;shell(L);}break;

case'2':{shifttimes=comparetimes=0;Quick(L);}break;

case'3':{shifttimes=comparetimes=0;TourSort(L,L-length);}break;

case'4':{shifttimes=comparetimes=0;Heap(L);}break;

case'5':{shifttimes=comparetimes=0;Merging(L);}break;

case'6':{shifttimes=comparetimes=0;Radixsort(L);}break;

}

}

printf("\n\t***************"

"\n\t1.继续读入文件"

"\n\t0.结束"

"\n\t***************");

do{

printf("\n\tplease choose (0-1):");

getchar();

scanf("%d",a);

}while(!(a==1||a==0));

}

}

[img]

数据结构 java开发中常用的排序算法有哪些

排序算法有很多，所以在特定情景中使用哪一种算法很重要。为了选择合适的算法，可以按照建议的顺序考虑以下标准：

（1）执行时间

（2）存储空间

（3）编程工作

对于数据量较小的情形，（1）（2）差别不大，主要考虑（3）；而对于数据量大的，（1）为首要。

主要排序法有：雀高

一、冒泡（Bubble）排序——相邻交换

二、选择排序——每次最小/大排在相应的位置

三、插入排序——将下一个插入已排好的序列中

四、壳（Shell）排序——缩小增量

五、归并排序

六、快速排序

七、堆排序

八、拓扑排序

一、冒泡（Bubble）排序

----------------------------------Code 从小到大排序n个数------------------------------------

void BubbleSortArray()

{

for(int i=1;in;i++)

{

for(int j=0;in-i;j++)

{

if(a[j]a[j+1])//比较交换相邻元素

{

int temp;

temp=a[j]; a[j]=a[j+1]; a[j+1]=temp;

}

}

}

}

-------------------------------------------------Code------------------------------------------------

效率 O（n²）,适用于排序小列表。

二、选择排序

----------------------------------Code 从小到大排序n个数--------------------------------

void SelectSortArray()

{

int min_index;

for(int i=0;in-1;i++)

{

min_index=i;

for(int j=i+1;jn;j++)//每次扫描选择最小项

if(arr[j]arr[min_index]) min_index=j;

if(min_index!=i)//找到最小项交换，即将这一项移到列表中的正确位置

{

int temp;

temp=arr[i]; arr[i]=arr[min_index]; arr[min_index]=temp;

}

}

}

-------------------------------------------------Code-----------------------------------------

效率O（n²），适用于排序小的列表。

三、插入排序

--------------------------------------------Code 从小到大排序n个数-------------------------------------

void InsertSortArray()

{

for(int i=1;in;i++)//循环从第二个数组元素开始，因为arr[0]作为最初已排序答雀部分

{

int temp=arr[i];//temp标记为未排序第一个元素

int j=i-1;

while (j=0 arr[j]temp)/*将temp与已排序元素从小清岁早到大比较，寻找temp应插入的位置*/

{

arr[j+1]=arr[j];

j--;

}

arr[j+1]=temp;

}

}

------------------------------Code--------------------------------------------------------------

最佳效率O（n）；最糟效率O（n²）与冒泡、选择相同，适用于排序小列表

若列表基本有序，则插入排序比冒泡、选择更有效率。

四、壳（Shell）排序——缩小增量排序

-------------------------------------Code 从小到大排序n个数-------------------------------------

void ShellSortArray()

{

for(int incr=3;incr0;incr--)//增量递减，以增量3，2，1为例

{

for(int L=0;L(n-1)/incr;L++)//重复分成的每个子列表

{

for(int i=L+incr;in;i+=incr)//对每个子列表应用插入排序

{

int temp=arr[i];

int j=i-incr;

while(j=0arr[j]temp)

{

arr[j+incr]=arr[j];

j-=incr;

}

arr[j+incr]=temp;

}

}

}

}

--------------------------------------Code-------------------------------------------

适用于排序小列表。

效率估计O（nlog2^n）~O（n^1.5），取决于增量值的最初大小。建议使用质数作为增量值，因为如果增量值是2的幂，则在下一个通道中会再次比较相同的元素。

壳（Shell）排序改进了插入排序，减少了比较的次数。是不稳定的排序，因为排序过程中元素可能会前后跳跃。

五、归并排序

----------------------------------------------Code 从小到大排序---------------------------------------

void MergeSort(int low,int high)

{

if(low=high) return;//每个子列表中剩下一个元素时停止

else int mid=(low+high)/2;/*将列表划分成相等的两个子列表,若有奇数个元素，则在左边子列表大于右侧子列表*/

MergeSort(low,mid);//子列表进一步划分

MergeSort(mid+1,high);

int [] B=new int [high-low+1];//新建一个数组，用于存放归并的元素

for(int i=low,j=mid+1,k=low;i=mid j=high;k++)/*两个子列表进行排序归并，直到两个子列表中的一个结束*/

{

if (arr[i]=arr[j];)

{

B[k]=arr[i];

I++;

}

else

{ B[k]=arr[j]; j++; }

}

for( ;j=high;j++,k++)//如果第二个子列表中仍然有元素，则追加到新列表

B[k]=arr[j];

for( ;i=mid;i++,k++)//如果在第一个子列表中仍然有元素，则追加到新列表中

B[k]=arr[i];

for(int z=0;zhigh-low+1;z++)//将排序的数组B的 所有元素复制到原始数组arr中

arr[z]=B[z];

}

-----------------------------------------------------Code---------------------------------------------------

效率O（nlogn），归并的最佳、平均和最糟用例效率之间没有差异。

适用于排序大列表，基于分治法。

六、快速排序

------------------------------------Code--------------------------------------------

/*快速排序的算法思想：选定一个枢纽元素，对待排序序列进行分割，分割之后的序列一个部分小于枢纽元素，一个部分大于枢纽元素，再对这两个分割好的子序列进行上述的过程。*/ void swap(int a,int b){int t;t =a ;a =b ;b =t ;}

int Partition(int [] arr,int low,int high)

{

int pivot=arr[low];//采用子序列的第一个元素作为枢纽元素

while (low high)

{

//从后往前栽后半部分中寻找第一个小于枢纽元素的元素

while (low high arr[high] = pivot)

{

--high;

}

//将这个比枢纽元素小的元素交换到前半部分

swap(arr[low], arr[high]);

//从前往后在前半部分中寻找第一个大于枢纽元素的元素

while (low high arr [low ]=pivot )

{

++low ;

}

swap (arr [low ],arr [high ]);//将这个枢纽元素大的元素交换到后半部分

}

return low ;//返回枢纽元素所在的位置

}

void QuickSort(int [] a,int low,int high)

{

if (low high )

{

int n=Partition (a ,low ,high );

QuickSort (a ,low ,n );

QuickSort (a ,n +1,high );

}

}

----------------------------------------Code-------------------------------------

平均效率O（nlogn），适用于排序大列表。

此算法的总时间取决于枢纽值的位置；选择第一个元素作为枢纽，可能导致O（n²）的最糟用例效率。若数基本有序，效率反而最差。选项中间值作为枢纽，效率是O（nlogn）。

基于分治法。

七、堆排序

最大堆：后者任一非终端节点的关键字均大于或等于它的左、右孩子的关键字，此时位于堆顶的节点的关键字是整个序列中最大的。

思想：

(1)令i=l,并令temp＝ kl ;

(2)计算i的左孩子j=2i+1;

(3)若j＝n－1，则转(4),否则转(6);

(4)比较kj和kj+1,若kj+1kj,则令j＝j＋1，否则j不变；

(5)比较temp和kj，若kjtemp，则令ki等于kj，并令i=j,j=2i+1,并转(3),否则转(6)

(6)令ki等于temp，结束。

-----------------------------------------Code---------------------------

void HeapSort(SeqIAst R)

{ //对R[1..n]进行堆排序，不妨用R[0]做暂存单元 int I; BuildHeap(R)； //将R[1-n]建成初始堆for(i=n;i1；i--) //对当前无序区R[1..i]进行堆排序，共做n-1趟。{ R[0]=R[1]; R[1]=R[i]; R[i]=R[0]; //将堆顶和堆中最后一个记录交换 Heapify(R,1,i-1); //将R[1..i-1]重新调整为堆，仅有R[1]可能违反堆性质 } } ---------------------------------------Code--------------------------------------

堆排序的时间，主要由建立初始堆和反复重建堆这两部分的时间开销构成，它们均是通过调用Heapify实现的。

堆排序的最坏时间复杂度为O(nlgn)。堆排序的平均性能较接近于最坏性能。 由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。 堆排序是就地排序，辅助空间为O(1)， 它是不稳定的排序方法。

堆排序与直接插入排序的区别:

直接选择排序中，为了从R[1..n]中选出关键字最小的记录，必须进行n-1次比较，然后在R[2..n]中选出关键字最小的记录，又需要做n-2次比较。事实上，后面的n-2次比较中，有许多比较可能在前面的n-1次比较中已经做过，但由于前一趟排序时未保留这些比较结果，所以后一趟排序时又重复执行了这些比较操作。

堆排序可通过树形结构保存部分比较结果，可减少比较次数。

八、拓扑排序

例 ：学生选修课排课先后顺序

拓扑排序：把有向图中各顶点按照它们相互之间的优先关系排列成一个线性序列的过程。

方法：

在有向图中选一个没有前驱的顶点且输出

从图中删除该顶点和所有以它为尾的弧

重复上述两步，直至全部顶点均已输出（拓扑排序成功），或者当图中不存在无前驱的顶点（图中有回路）为止。

---------------------------------------Code--------------------------------------

void TopologicalSort()/*输出拓扑排序函数。若G无回路，则输出G的顶点的一个拓扑序列并返回OK，否则返回ERROR*/

{

int indegree[M];

int i,k,j;

char n;

int count=0;

Stack thestack;

FindInDegree(G,indegree);//对各顶点求入度indegree[0....num]

InitStack(thestack);//初始化栈

for(i=0;iG.num;i++)

Console.WriteLine("结点"+G.vertices[i].data+"的入度为"+indegree[i]);

for(i=0;iG.num;i++)

{

if(indegree[i]==0)

Push(thestack.vertices[i]);

}

Console.Write("拓扑排序输出顺序为：");

while(thestack.Peek()!=null)

{

Pop(thestack.Peek());

j=locatevex(G,n);

if (j==-2)

{

Console.WriteLine("发生错误，程序结束。");

exit();

}

Console.Write(G.vertices[j].data);

count++;

for(p=G.vertices[j].firstarc;p!=NULL;p=p.nextarc)

{

k=p.adjvex;

if (!(--indegree[k]))

Push(G.vertices[k]);

}

}

if (countG.num)

Cosole.WriteLine("该图有环，出现错误，无法排序。");

else

Console.WriteLine("排序成功。");

}

----------------------------------------Code--------------------------------------

算法的时间复杂度O（n+e）。

面试经典数据结构和算法汇总

如果说数据结构是骨架，那么算法就是灵魂。没了骨架，灵魂没有实体寄托；没了灵魂，骨架也是个空壳。两者相辅相成，缺一不可，在开发中起到了砥柱中流的作用。镇没或

现在我对各种数据结构和算法做一总结，对比一下它们的效率

1.数据结构篇

1. 如果让你手写个栈和队列，你还会写吗？

2. 开发了那么多项目，你能自己手写个健壮的链表出来吗？

3. 下次面试若再被问到二叉树，希望你能对答如流！

4. 面试还在被红-黑树虐？看完这篇轻御伍松搞定面试官 ！

2.排序算法篇

1. 几个经典的基础排序算法，你还记得吗？

2. 手把手教你学会希尔排序，很简单！

3. 快速排序算法到底有多快？

4. 五分钟教你学会归并排序

5. 简单说下二叉树排序

6. 学会堆排序只需要几分钟

7. 图，这个玩意儿竟然还可以用来排序！

掌握了这些经典的数据结构和算法，面试啥的基本上没什么问题了，特别是对于那些应届生来说。接下来再总结一下不同数据结构和算法的效率问题，做一下对察码比，这也是面试官经常问的问题。

数据结构常用操作效率对比：

常用排序算法效率的对比：

关于经典的数据结构和算法，就总结到这，本文建议收藏，利用等公交、各种排队之时提升自己。这世上天才很少，懒蛋却很多，你若对得起时间，时间便对得起你。

数据结构的排序方法有哪些？

冒泡排序，快速排序，堆排序。

冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。

它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换如世，也就是说该数列已经排序完成。

这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端，故名“冒泡排序”。

快速排序（Quicksort）是对冒泡排序的一种改进。

快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。大庆橡梁根堆的要求是每个节点誉运的值都不大于其父节点的值，即A[PARENT[i]] = A[i]。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。

数据结构复习总结第八章排序

第八章排序

基本概念

文件有一组记录组成 记录有若干数据项组成 唯一标识记录的数据项称关键字;

排序是将文件按关键字的递增(减)顺序排列;

排序文件中有相同的关键字时 若排序后相对次序保持不变的称稳定排序 否则称不稳定排序;

在排序过程中 文件放在内存中处理不涉及数据的内 外存交换的称内部排序 反之称外部排序;

排序算法的基本操作 )比较关键字的大小; )改变指向记录的指针或移动记录本身

评价排序方法的标准 )执行时间; )所需辅助空间 辅助空间为O( )称就地排序;另要注意算法的复杂程度

若关键字类型没有比较运算符 可事先定义宏或函数表示比较运算

插入排序

直接插入排序

实现过程

void insertsort(seqlist R)

{

int i j;

for(i= ;i=n;i++)

if(R[i] key R[i ] key{

R[ ]=R[i];j=i ;

do{R[j+ ]=R[j];j ;}

while(R[ ] key r[j].key); p="" /r[j].key);

R[j+1]=R[0];

}

}

算法中引入监视哨R[0]的作用是：1)保存R[i]的副本;2)简化边界条件，防止循环下标越界。WiNgwit

关键字比较次数最大为(n+2)(n-1)/2;记录移动次数最大为(n+4)(n-1)/2;

算法的最好时间是O(n);最坏时间是O(n^2);平均时间是O(n^2);是一种就地的稳定的排序;

8.2.2希尔排序

实现过程：是将直接插入排序的间隔变为d。d的取值要注意：1)最后一次必为1;2)避免d值互为倍数;

关键字比较次数最大为n^1.25;记录移动次数最大为1.6n^1.25;

算法的平均时间是O(n^1.25);是一种就地的不稳定的排序;

8.3交换排序

8.3.1冒泡排序

实现过程：从下到上相邻两个比较，按小在上原则扫描一次，确定最小值，重复n-1次。

关键字比较次数最小为n-1、最大为n(n-1)/2;记录码含移动次数最小为0，最大为3n(n-1)/2;

算法的最好时间是O(n);最坏时间是O(n^2);平均时间是O(n^2);是一种就地的稳定的排序;

8.3.2快速排序

实现过程：将第一个值作为基准，设置i,j指针交替从两头与基准比较含轮，有交换后,交换j，i。i=j时确定基准，并以其为界限将序列分为两段。重复以上步骤。

关键字比较次数最好为nlog2n+nC(1)、最坏为n(n-1)/2;

算法的最好时间是O(nlog2n);最坏时间是O(n^2);平均时间是谈模信O(nlog2n);辅助空间为O(log2n);是一种不稳定排序;

8.4选择排序

8.4.1直接选择排序

实现过程：选择序列中最小的插入第一位，在剩余的序列中重复上一步，共重复n-1次。

关键字比较次数为n(n-1)/2;记录移动次数最小为0，最大为3(n-1);

算法的最好时间是O(n^2);最坏时间是O(n^2);平均时间是O(n^2);是一种就地的不稳定的排序;

8.4.2堆排序

实现过程：把序列按层次填入完全二叉树，调整位置使双亲大于或小于孩子，建立初始大根或小根堆，调整树根与最后一个叶子的位置，排除该叶子重新调整位置。

算法的最好时间是O(nlog2n);最坏时间是O(nlog2n);平均时间是O(nlog2n);是一种就地的不稳定排序;

8.5归并排序

实现过程：将初始序列分为2个一组，最后单数轮空，对每一组排序后作为一个单元，对2个单元排序，直到结束。

算法的最好时间是O(nlog2n);最坏时间是O(nlog2n);平均时间是O(nlog2n);辅助空间为O(n);是一种稳定排序;

8.6分配排序

8.6.1箱排序

实现过程：按关键字的取值范围确定箱子的个数，将序列按关键字放入箱中，输出非空箱的关键字。

在桶内分配和收集，及对各桶进行插入排序的时间为O(n),算法的期望时间是O(n),最坏时间是O(n^2)。

8.6.2基数排序

实现过程：按基数设置箱子，对关键字从低位到高位依次进行箱排序。

算法的最好时间是O(d*n+d*rd);最坏时间是O(d*n+d*rd);平均时间是O(d*n+d*rd);辅助空间O(n+rd);是一种稳定排序;

8.7各种内部排序方法的比较和选择

按平均时间复杂度分为：

1) 平方阶排序：直接插入、直接选择、冒泡排序;

2) 线性对数阶：快速排序、堆排序、归并排序;

3) 指数阶：希尔排序;

4) 线性阶：箱排序、基数排序。

选择合适排序方法的因素：1)待排序的记录数;2)记录的大小;3)关键字的结构和初始状态;4)对稳定性的要求;5)语言工具的条件;6)存储结构;7)时间和辅助空间复杂度。

结论：

1) 若规模较小可采用直接插入或直接选择排序;

2) 若文件初始状态基本有序可采用直接插入、冒泡或随机快速排序;

3) 若规模较大可采用快速排序、堆排序或归并排序;

4) 任何借助于比较的排序，至少需要O(nlog2n)的时间，箱排序和基数排序只适用于有明显结构特征的关键字;

5) 有的语言没有提供指针及递归，使归并、快速、基数排序算法复杂;

6) 记录规模较大时为避免大量移动记录可用链表作为存储结构，如插入、归并、基数排序，但快速、堆排序在链表上难以实现，可提取关键字建立索引表，然后对索引表排序。

附二:

第八章排序

*************************************************************************************

记录中可用某一项来标识一个记录，则称为关键字项，该数据项的值称为关键字。

排序是使文件中的记录按关键字递增(或递减)次序排列起来。·基本操作：比较关键字大小;改变指向记录的指针或移动记录。

·存储结构：顺序结构、链表结构、索引结构。

经过排序后这些具有相同关键字的记录之间的相对次序保持不变,则称这种排序方法是稳定的，否则排序算法是不稳定的。

排序过程中不涉及数据的内、外存交换则称之为"内部排序"(内排序)，反之，若存在数据的内外存交换，则称之为外排序。

内部排序方法可分五类：插入排序、选择排序、交换排序、归并排序和分配排序。

评价排序算法好坏的标准主要有两条：执行时间和所需的辅助空间，另外算法的复杂程序也是要考虑的一个因素。

*************************************************************************************

插入排序：·直接插入排序： ·逐个向前插入到合适位置。

·哨兵(监视哨)有两个作用： ·作为临变量存放R[i]

·是在查找循环中用来监视下标变量j是否越界。

·直接插入排序是就地的稳定排序。时间复杂度为O(n^2)，比较次数为(n+2)(n-1)/2;移动次数为(n+4)(n-1)/2;

·希尔排序： ·等间隔的数据比较并按要求顺序排列，最后间隔为1。

·希尔排序是就地的不稳定排序。时间复杂度为O(n^1.25)，比较次数为(n^1.25);移动次数为(1.6n^1.25);

交换排序：·冒泡排序：·自下向上确定最轻的一个。·自上向下确定最重的一个。·自下向上确定最轻的一个，后自上向下确定最重的一个。

·冒泡排序是就地的稳定排序。时间复杂度为O(n^2)，比较次数为n(n-1)/2;移动次数为3n(n-1)/2;

·快速排序：·以第一个元素为参考基准，设定、动两个指针，发生交换后指针交换位置，直到指针重合。重复直到排序完成。

·快速排序是非就地的不稳定排序。时间复杂度为O(nlog2n)，比较次数为n(n-1)/2;

选择排序：·直接选择排序： ·选择最小的放在比较区前。

·直接选择排序就地的不稳定排序。时间复杂度为O(n^2)。比较次数为n(n-1)/2;

·堆排序 ·建堆：按层次将数据填入完全二叉树，从int(n/2)处向前逐个调整位置。

·然后将树根与最后一个叶子交换值并断开与树的连接并重建堆，直到全断开。

·堆排序是就地不稳定的排序，时间复杂度为O(nlog2n)，不适宜于记录数较少的文件。。

归并排序： ·先两个一组排序，形成(n+1)/2组，再将两组并一组，直到剩下一组为止。

·归并排序是非就地稳定排序，时间复杂度是O(nlog2n),

分配排序：·箱排序： ·按关键字的取值范围确定箱子数，按关键字投入箱子，链接所有非空箱。

·箱排序的平均时间复杂度是线性的O(n).

·基数排序：·从低位到高位依次对关键字进行箱排序。

·基数排序是非就稳定的排序，时间复杂度是O(d*n+d*rd)。

各种排序方法的比较和选择： ·.待排序的记录数目n;n较大的要用时间复杂度为O(nlog2n)的排序方法;

·记录的大小(规模);记录大最好用链表作为存储结构，而快速排序和堆排序在链表上难于实现;

·关键字的结构及其初始状态;

·对稳定性的要求;

·语言工具的条件;

·存储结构;

·时间和辅助空间复杂度。

lishixinzhi/Article/program/sjjg/201311/23750

关于数据结构排序算法总结和数据结构各种排序方法总结的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。