数据结构的排序算法动画演示

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

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

⑵ 用flash模拟二叉树线索化

B树的删除
B树的生长过程
三元组表的转置
中序线索化二叉树
串的顺序存储
二分查找
二叉排序树的删除
二叉排序树的生成
二叉树的建立
克鲁斯卡尔算法构造最小生成树
冒泡排序
分块查找
单链表结点的删除
单链表结点的插入
图的深度优先遍历
基数排序
堆排序
头插法建单链表
寻找中序线索化二叉树指定结点的前驱
寻找中序线索化二叉树指定结点的后继
尾插法建表
希儿排序
开放寻址法建立散列表
循环队列操作演示
快速排序
拉链法创建散列表
拓扑排序
数据结构和算法Flash动画演示.rar
最短路径
朴素串匹配算法过程示意
构造哈夫曼树的算法模拟
构造哈夫曼树过程
栈与递归

⑶ 数据结构 10.10 堆排序算法演示（一）

希赛教育计算机专业考研专业课辅导招生

希赛教育计算机专业考研专业课辅导视频

希赛教育计算机考研专业课在线测试系统

已知关键字序列{ }是大顶堆 当将 和 互换之后 它就不再是个堆 但此时 已是选出的最大关键字 不需要再参加排序 由此只要对其余关键字进行排序 如果能将它重新调整为一个大顶堆 这就等于选出了第二个最大关键字 而此时的关键字序列有下列特点 除根结点之外 其左子树和右子树都仍然是堆 由此只要从上到下进行筛选可将该序列重新调整为大顶堆

⑷ 数据结构中有关拓扑排序的相关知识

将入度为0的结点入队，删除后同时将所有相邻顶点的先决条件减一。当某个顶点的计数为0时，将它入队。这是关键思想。

⑸ 面试必会八大排序算法（Python）

一、插入排序

介绍

插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据。

算法适用于少量数据的排序，时间复杂度为O(n^2)。

插入排算法是稳定的排序方法。

步骤

①从第一个元素开始，该元素可以认为已经被排序

②取出下一个元素，在已经排序的元素序列中从后向前扫描

③如果该元素（已排序）大于新元素，将该元素移到下一位置

④重复步骤3，直到找到已排序的元素小于或者等于新元素的位置

⑤将新元素插入到该位置中

⑥重复步骤2

排序演示

算法实现

二、冒泡排序

介绍

冒泡排序（Bubble Sort）是一种简单的排序算法，时间复杂度为O(n^2)。

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

这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

原理

循环遍历列表，每次循环找出循环最大的元素排在后面；

需要使用嵌套循环实现：外层循环控制总循环次数，内层循环负责每轮的循环比较。

步骤

①比较相邻的元素。如果第一个比第二个大，就交换他们两个。

②对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。

③针对所有的元素重复以上的步骤，除了最后一个。

④持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

算法实现：

三、快速排序

介绍

快速排序（Quicksort）是对冒泡排序的一种改进，借用了分治的思想，由C. A. R. Hoare在1962年提出。

基本思想

快速排序的基本思想是：挖坑填数 + 分治法。

首先选出一个轴值(pivot，也有叫基准的)，通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

实现步骤

①从数列中挑出一个元素，称为 “基准”（pivot）；

②重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）；

③对所有两个小数列重复第二步，直至各区间只有一个数。

排序演示

算法实现

四、希尔排序

介绍

希尔排序（Shell Sort）是插入排序的一种，也是缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法，时间复杂度为：O(1.3n)。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

·插入排序在对几乎已经排好序的数据操作时， 效率高， 即可以达到线性排序的效率；

·但插入排序一般来说是低效的， 因为插入排序每次只能将数据移动一位。

基本思想

①希尔排序是把记录按下标的一定量分组，对每组使用直接插入算法排序；

②随着增量逐渐减少，每组包1含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法被终止。

排序演示

算法实现

五、选择排序

介绍

选择排序(Selection sort)是一种简单直观的排序算法，时间复杂度为Ο(n2)。

基本思想

选择排序的基本思想：比较 + 交换。

第一趟，在待排序记录r1 ~ r[n]中选出最小的记录，将它与r1交换；

第二趟，在待排序记录r2 ~ r[n]中选出最小的记录，将它与r2交换；

以此类推，第 i 趟，在待排序记录ri ~ r[n]中选出最小的记录，将它与r[i]交换,使有序序列不断增长直到全部排序完毕。

排序演示

选择排序的示例动画。红色表示当前最小值，黄色表示已排序序列，蓝色表示当前位置。

算法实现

六、堆排序

介绍

堆排序（Heapsort）是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。

利用数组的特点快速指定索引的元素。

基本思想

堆分为大根堆和小根堆，是完全二叉树。

大根堆的要求是每个节点的值不大于其父节点的值，即A[PARENT[i]] >=A[i]。

在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。

排序演示

算法实现

七、归并排序

介绍

归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

基本思想

归并排序算法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

算法思想

自上而下递归法（假如序列共有n个元素）

① 将序列每相邻两个数字进行归并操作，形成 floor(n/2)个序列，排序后每个序列包含两个元素；

② 将上述序列再次归并，形成 floor(n/4)个序列，每个序列包含四个元素；

③ 重复步骤②，直到所有元素排序完毕。

自下而上迭代法

① 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；

② 设定两个指针，最初位置分别为两个已经排序序列的起始位置；

③ 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；

④ 重复步骤③直到某一指针达到序列尾；

⑤ 将另一序列剩下的所有元素直接复制到合并序列尾。

排序演示

算法实现

八、基数排序

介绍

基数排序（Radix Sort）属于“分配式排序”，又称为“桶子法”。

基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m) ，其中 r 为采取的基数，而m为堆数。

在某些时候，基数排序法的效率高于其他的稳定性排序法。

基本思想

将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。

基数排序按照优先从高位或低位来排序有两种实现方案：

MSD（Most significant digital） 从最左侧高位开始进行排序。先按k1排序分组, 同一组中记录, 关键码k1相等,再对各组按k2排序分成子组, 之后, 对后面的关键码继续这样的排序分组, 直到按最次位关键码kd对各子组排序后. 再将各组连接起来,便得到一个有序序列。MSD方式适用于位数多的序列。

LSD （Least significant digital）从最右侧低位开始进行排序。先从kd开始排序，再对kd-1进行排序，依次重复，直到对k1排序后便得到一个有序序列。LSD方式适用于位数少的序列。

排序效果

算法实现

九、总结

各种排序的稳定性、时间复杂度、空间复杂度的总结：

平方阶O(n²)排序：各类简单排序：直接插入、直接选择和冒泡排序；

从时间复杂度来说：

线性对数阶O(nlog₂n)排序：快速排序、堆排序和归并排序；

O(n1+§))排序，§是介于0和1之间的常数：希尔排序 ；

线性阶O(n)排序：基数排序，此外还有桶、箱排序。

⑹ 数据结构十种排序算法总结

部分来自 https://mp.weixin.qq.com/s/feQDjby4uYGRLbYUJq7Lpg?

首先先上张图 好好记住

图中的名字的意思：
n: 数据规模
k: “桶”的个数
In-place: 占用常数内存，不占用额外内存
Out-place: 占用额外内存
这么一看感觉很乱 我们分下类，瞬间感觉很简单

然后最后三种非比较的算法的区别是：
基数排序：根据键值的每位数字来分配桶
计数排序：每个桶只存储单一键值
桶排序：每个桶存储一定范围的数值

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

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(p>q)
{
break;
}
}
a[sign]=a[p];//将p所指元素移入空位置
sign=p;//记录空余位置
p++;
if(p>q)
{
break;
}
while(a[q]>head)//q所指元素比比较元素大，q左移
{
q--;
if(p>q)
{
break;
}
}
a[sign]=a[q];
sign=q;
q--;
}
a[sign]=head;//比较完成后，将比较元素移入空位置
if(sign-1>m)
{
Qsort(m,sign-1);//对m到sign-1的数列进行排序
}
if(sign+1<n)
{
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;i<n;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<=mid&&j<=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;i<num;i++)
{
printf("%d\n",a[i]);
}
}
int main()
{
int sign;
int i;
int num;
scanf("%d",&num);//输入将要排序的数的个数
for(i=0;i<num;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;i<Maxsize+1;i++)
{
fscanf(fp,"%ld (%d)",&(L->r[i].key),&(L->r[i].num));
if(L->r[i].key<0)
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.key>b.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;j>0&<(L->r[0].key,L->r[j].key);j-=dk)//记录后移，查找插入位置
{
L->r[j+dk]=L->r[j];
comparetimes++;
shifttimes++;
}
if(j>0)
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(low<high)//从表的两端交替地向中间扫描
{
while(low<high&&L->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(low<high&&L->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(low<high)//序列长度大于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(t<n)//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(k>n)
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(w<t/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(j<m&<(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;i>0;--i)//把L建成大顶堆
Heapadjust(L,i,L->length);
for(i=L->length;i>1;--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<=m&&j<=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 (low<high)
{
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;i<6;i++)
{
for(j=0;j<10;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;j<10;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));

}
}

⑻ 数据结构堆排序算法

初始堆： 49 a[1] 38 65 a[2] a[3] 97 76 13 27 a[4] a[5] a[6] a[7] 50 a[8]procere heap(nn,ii:integer); var x,i,j:integer; begin i:=ii;x:=a[ii];j:=2*ii; while j<=nn do begin if (j<nn) and(a[j]<a[j+1] then j:=j+1; if x<a[j] then begin a[i]:=a[j];i:=j;j:=2*i;end else j:=nn+1; end; end;主程序：for i:=n div 2 downto 1 do heap(n,i); /heap相当于搜索顶点i的所有子节点，找出最大的和它替换for i:=n downto 2 do begin temp:=a[1];a[1]:=a[i];a[i]:=temp; /将当前最大的数（放在a[1]）和第i个数交换，保证从后面往前数是 heap(i-1,1); 从大到小，则程序完成时，数组a从前往后是从小到大 end; 至于过程自己用笔算，很快就会明白，不明白算了就明白。

⑼ 基数排序怎么排

.example-btn{color:#fff;background-color:#5cb85c;border-color:#4cae4c}.example-btn:hover{color:#fff;background-color:#47a447;border-color:#398439}.example-btn:active{background-image:none}div.example{width:98%;color:#000;background-color:#f6f4f0;background-color:#d0e69c;background-color:#dcecb5;background-color:#e5eecc;margin:005px0;padding:5px;border:1pxsolid#d4d4d4;background-image:-webkit-linear-gradient(#fff,#e5eecc100px);background-image:linear-gradient(#fff,#e5eecc100px)}div.example_code{line-height:1.4em;width:98%;background-color:#fff;padding:5px;border:1pxsolid#d4d4d4;font-size:110%;font-family:Menlo,Monaco,Consolas,"AndaleMono","lucidaconsole","CourierNew",monospace;word-break:break-all;word-wrap:break-word}div.example_result{background-color:#fff;padding:4px;border:1pxsolid#d4d4d4;width:98%}div.code{width:98%;border:1pxsolid#d4d4d4;background-color:#f6f4f0;color:#444;padding:5px;margin:0}div.codediv{font-size:110%}div.codediv,div.codep,div.example_codep{font-family:"couriernew"}pre{margin:15pxauto;font:12px/20pxMenlo,Monaco,Consolas,"AndaleMono","lucidaconsole","CourierNew",monospace;white-space:pre-wrap;word-break:break-all;word-wrap:break-word;border:1pxsolid#ddd;border-left-width:4px;padding:10px15px}排序算法是《数据结构与算法》中最基本的算法之一。排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。以下是基数排序算法：
基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。
1.基数排序vs计数排序vs桶排序基数排序有两种方法：
这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：
基数排序：根据键值的每位数字来分配桶；计数排序：每个桶只存储单一键值；桶排序：每个桶存储一定范围的数值；2.LSD基数排序动图演示
代码实现javaScript实例//LSDRadixSortvarcounter=[];functionradixSort(arr,maxDigit){varmod=10;vardev=1;for(vari=0;i<maxDigit;i++,dev*=10,mod*=10){for(varj=0;j<arr.length;j++){varbucket=parseInt((arr[j]%mod)/dev);if(counter[bucket]==null){counter[bucket]=[];}counter[bucket].push(arr[j]);}varpos=0;for(varj=0;j<counter.length;j++){varvalue=null;if(counter[j]!=null){while((value=counter[j].shift())!=null){arr[pos++]=value;}}}}returnarr;}Java实例/***基数排序*考虑负数的情况还可以参考：https://code.i-harness.com/zh-CN/q/e98fa9*/{@Overridepublicint[]sort(int[]sourceArray)throwsException{//对arr进行拷贝，不改变参数内容int[]arr=Arrays.Of(sourceArray,sourceArray.length);intmaxDigit=getMaxDigit(arr);returnradixSort(arr,maxDigit);}/***获取最高位数*/privateintgetMaxDigit(int[]arr){intmaxValue=getMaxValue(arr);returngetNumLenght(maxValue);}privateintgetMaxValue(int[]arr){intmaxValue=arr[0];for(intvalue:arr){if(maxValue<value){maxValue=value;}}returnmaxValue;}protectedintgetNumLenght(longnum){if(num==0){return1;}intlenght=0;for(longtemp=num;temp!=0;temp/=10){lenght++;}returnlenght;}privateint[]radixSort(int[]arr,intmaxDigit){intmod=10;intdev=1;for(inti=0;i<maxDigit;i++,dev*=10,mod*=10){//考虑负数的情况，这里扩展一倍队列数，其中[0-9]对应负数，[10-19]对应正数(bucket+10)int[][]counter=newint[mod*2][0];for(intj=0;j<arr.length;j++){intbucket=((arr[j]%mod)/dev)+mod;counter[bucket]=arrayAppend(counter[bucket],arr[j]);}intpos=0;for(int[]bucket:counter){for(intvalue:bucket){arr[pos++]=value;}}}returnarr;}/***自动扩容，并保存数据**@paramarr*@paramvalue*/privateint[]arrayAppend(int[]arr,intvalue){arr=Arrays.Of(arr,arr.length+1);arr[arr.length-1]=value;returnarr;}}PHP实例functionradixSort($arr,$maxDigit=null){if($maxDigit===null){$maxDigit=max($arr);}$counter=[];for($i=0;$i<$maxDigit;$i++){for($j=0;$j<count($arr);$j++){preg_match_all('/d/',(string)$arr[$j],$matches);$numArr=$matches[0];$lenTmp=count($numArr);$bucket=array_key_exists($lenTmp-$i-1,$numArr)?intval($numArr[$lenTmp-$i-1]):0;if(!array_key_exists($bucket,$counter)){$counter[$bucket]=[];}$counter[$bucket][]=$arr[$j];}$pos=0;for($j=0;$j<count($counter);$j++){$value=null;if($counter[$j]!==null){while(($value=array_shift($counter[$j]))!==null){$arr[$pos++]=$value;}}}}return$arr;}C++实例intmaxbit(intdata[],intn)//辅助函数，求数据的最大位数{intmaxData=data[0];///<最大数///先求出最大数，再求其位数，这样有原先依次每个数判断其位数，稍微优化点。for(inti=1;i<n;++i){if(maxData<data[i])maxData=data[i];}intd=1;intp=10;while(maxData>=p){//p*=10;//MaybeoverflowmaxData/=10;++d;}returnd;/*intd=1;//保存最大的位数intp=10;for(inti=0;i<n;++i){while(data[i]>=p){p*=10;++d;}}returnd;*/}voidradixsort(intdata[],intn)//基数排序{intd=maxbit(data,n);int*tmp=newint[n];int*count=newint[10];//计数器inti,j,k;intradix=1;for(i=1;i<=d;i++)//进行d次排序{for(j=0;j<10;j++)count[j]=0;//每次分配前清空计数器for(j=0;j<n;j++){k=(data[j]/radix)%10;//统计每个桶中的记录数count[k]++;}for(j=1;j<10;j++)count[j]=count[j-1]+count[j];//将tmp中的位置依次分配给每个桶for(j=n-1;j>=0;j--)//将所有桶中记录依次收集到tmp中{k=(data[j]/radix)%10;tmp[count[k]-1]=data[j];count[k]--;}for(j=0;j<n;j++)//将临时数组的内容复制到data中data[j]=tmp[j];radix=radix*10;}delete[]tmp;delete[]count;}C实例#include<stdio.h>#defineMAX20//#defineSHOWPASS#defineBASE10voidprint(int*a,intn){inti;for(i=0;i<n;i++){printf("%d ",a[i]);}}voidradixsort(int*a,intn){inti,b[MAX],m=a[0],exp=1;for(i=1;i<n;i++){if(a[i]>m){m=a[i];}}while(m/exp>0){intbucket[BASE]={0};for(i=0;i<n;i++){bucket[(a[i]/exp)%BASE]++;}for(i=1;i<BASE;i++){bucket[i]+=bucket[i-1];}for(i=n-1;i>=0;i--){b[--bucket[(a[i]/exp)%BASE]]=a[i];}for(i=0;i<n;i++){a[i]=b[i];}exp*=BASE;#ifdefSHOWPASSprintf("
PASS:");print(a,n);#endif}}intmain(){intarr[MAX];inti,n;printf("Entertotalelements(n<=%d):",MAX);scanf("%d",&n);n=n<MAX?n:MAX;printf("Enter%dElements:",n);for(i=0;i<n;i++){scanf("%d",&arr[i]);}printf("
ARRAY:");print(&arr[0],n);radixsort(&arr[0],n);printf("
SORTED:");print(&arr[0],n);printf("
");return0;}Lua实例--获取表中位数localmaxBit=function(tt)localweight=10;--十_制localbit=1;fork,vinpairs(tt)dowhilev>=weightdoweight=weight*10;bit=bit+1;endendreturnbit;end--基数排序localradixSort=function(tt)localmaxbit=maxBit(tt);localbucket={};localtemp={};localradix=1;fori=1,maxbitdoforj=1,10dobucket[j]=0;---清空桶endfork,vinpairs(tt)dolocalremainder=math.floor((v/radix))%10+1;bucket[remainder]=bucket[remainder]+1;--每_桶_量自_增加1endforj=2,10dobucket[j]=bucket[j-1]+bucket[j];--每个桶的数量=以前桶数量和+自个数量end--按照桶的位置，排序--这个是桶式排序，必须使用倒序，因为排序方法是从小到大，顺序下来，会出现大的在小的上面清空。fork=#tt,1,-1dolocalremainder=math.floor((tt[k]/radix))%10+1;temp[bucket[remainder]]=tt[k];bucket[remainder]=bucket[remainder]-1;endfork,vinpairs(temp)dott[k]=v;endradix=radix*10;endend;参考地址：
https://github.com/hustcc/JS-Sorting-Algorithm/blob/master/10.radixSort.md
https://zh.wikipedia.org/wiki/%E5%9F%BA%E6%95%B0%E6%8E%92%E5%BA%8F
以下是热心网友对基数排序算法的补充，仅供参考：热心网友提供的补充1：
java代码里，mod每次循环会乘10，但counter的行数是不需要变的，能包含[-9,9]就可以了。


for(inti=0;i<maxDigit;i++,dev*=10,mod*=10){
//考虑负数的情况，这里扩展一倍队列数，其中[0-9]对应负数，[10-19]对应正数(bucket+10)
int[][]counter=newint[20][0];

for(intj=0;j<arr.length;j++){
intbucket=((arr[j]%mod)/dev)+10;
counter[bucket]=arrayAppend(counter[bucket],arr[j]);
}

intpos=0;
for(int[]bucket:counter){
for(intvalue:bucket){
arr[pos++]=value;
}
}
}热心网友提供的补充2：
艾孜尔江补充使用C#基数排序算法如下:


///基数排序
staticvoidRadixSort(List<int>list)
{
intmaxValue=list.Max();//列表内部方法拿过来用用（在Linq中）
intit=0;//需要几趟
//maxvalue9-199-2999-3
//10^0<=910^1>9it=1
//10^0<9910^1<9910^2>99it=2
while(Math.Pow(10,it)<=maxValue)
{
List<List<int>>buckets=newList<List<int>>(10);//分10个桶对应0-9
for(inti=0;i<10;i++)
{
buckets.Add(newList<int>());
}//列表初始化大小
for(inti=0;i<list.Count;i++)//入桶
{
//989it=0989/10^it=989989%10=9;
intdigit=(int)((list[i])/(Math.Pow(10,it))%10);//得到对应桶
buckets[digit].Add(list[i]);
}//全部入桶
list.Clear();//依次取出来
for(inti=0;i<buckets.Count;i++)
{