Ⅰ c语言排序
//总共给你整理了7种排序算法：希尔排序，链式基数排序，归并排序
//起泡排序，简单选择排序，树形选择排序，堆排序,先自己看看吧，
//看不懂可以再问身边的人或者查资料,既然可以上网，我相信你所在的地方信息流通方式应该还行,所有的程序全部在VC++6.0下编译通过
//希尔排序
#include<stdio.h>
typedef int InfoType; // 定义其它数据项的类型
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))
#define LQ(a,b) ((a)<=(b))
#define MAXSIZE 20 // 一个用作示例的小顺序表的最大长度
typedef int KeyType; // 定义关键字类型为整型
struct RedType // 记录类型
{
KeyType key; // 关键字项
InfoType otherinfo; // 其它数据项，具体类型在主程中定义
};
struct SqList // 顺序表类型
{
RedType r[MAXSIZE+1]; // r[0]闲置或用作哨兵单元
int length; // 顺序表长度
};
void ShellInsert(SqList &L,int dk)
{ // 对顺序表L作一趟希尔插入排序。本算法是和一趟直接插入排序相比，
// 作了以下修改：
// 1.前后记录位置的增量是dk,而不是1;
// 2.r[0]只是暂存单元,不是哨兵。当j<=0时,插入位置已找到。算法10.4
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[0]
for(j=i-dk;j>0&<(L.r[0].key,L.r[j].key);j-=dk)
L.r[j+dk]=L.r[j]; // 记录后移，查找插入位置
L.r[j+dk]=L.r[0]; // 插入
}
}
void print(SqList L)
{
int i;
for(i=1;i<=L.length;i++)
printf("%d ",L.r[i].key);
printf("\n");
}
void print1(SqList L)
{
int i;
for(i=1;i<=L.length;i++)
printf("(%d,%d)",L.r[i].key,L.r[i].otherinfo);
printf("\n");
}
void ShellSort(SqList &L,int dlta[],int t)
{ // 按增量序列dlta[0..t-1]对顺序表L作希尔排序。算法10.5
int k;
for(k=0;k<t;++k)
{
ShellInsert(L,dlta[k]); // 一趟增量为dlta[k]的插入排序
printf("第%d趟排序结果: ",k+1);
print(L);
}
}
#define N 10
#define T 3
void main()
{
RedType d[N]={{49,1},{38,2},{65,3},{97,4},{76,5},{13,6},{27,7},{49,8},{55,9},{4,10}};
SqList l;
int dt[T]={5,3,1}; // 增量序列数组
for(int i=0;i<N;i++)
l.r[i+1]=d[i];
l.length=N;
printf("排序前: ");
print(l);
ShellSort(l,dt,T);
printf("排序后: ");
print1(l);
}
/*****************************************************************/
//链式基数排序
typedef int InfoType; // 定义其它数据项的类型
typedef int KeyType; // 定义RedType类型的关键字为整型
struct RedType // 记录类型(同c10-1.h)
{
KeyType key; // 关键字项
InfoType otherinfo; // 其它数据项
};
typedef char KeysType; // 定义关键字类型为字符型
#include<string.h>
#include<ctype.h>
#include<malloc.h> // malloc()等
#include<limits.h> // INT_MAX等
#include<stdio.h> // EOF(=^Z或F6),NULL
#include<stdlib.h> // atoi()
#include<io.h> // eof()
#include<math.h> // floor(),ceil(),abs()
#include<process.h> // exit()
#include<iostream.h> // cout,cin
// 函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
typedef int Status; // Status是函数的类型,其值是函数结果状态代码，如OK等
typedef int Boolean; // Boolean是布尔类型,其值是TRUE或FALSE
#define MAX_NUM_OF_KEY 8 // 关键字项数的最大值
#define RADIX 10 // 关键字基数，此时是十进制整数的基数
#define MAX_SPACE 1000
struct SLCell // 静态链表的结点类型
{
KeysType keys[MAX_NUM_OF_KEY]; // 关键字
InfoType otheritems; // 其它数据项
int next;
};
struct SLList // 静态链表类型
{
SLCell r[MAX_SPACE]; // 静态链表的可利用空间，r[0]为头结点
int keynum; // 记录的当前关键字个数
int recnum; // 静态链表的当前长度
};
typedef int ArrType[RADIX];
void InitList(SLList &L,RedType D[],int n)
{ // 初始化静态链表L（把数组D中的数据存于L中）
char c[MAX_NUM_OF_KEY],c1[MAX_NUM_OF_KEY];
int i,j,max=D[0].key; // max为关键字的最大值
for(i=1;i<n;i++)
if(max<D[i].key)
max=D[i].key;
L.keynum=int(ceil(log10(max)));
L.recnum=n;
for(i=1;i<=n;i++)
{
L.r[i].otheritems=D[i-1].otherinfo;
itoa(D[i-1].key,c,10); // 将10进制整型转化为字符型,存入c
for(j=strlen(c);j<L.keynum;j++) // 若c的长度<max的位数,在c前补'0'
{
strcpy(c1,"0");
strcat(c1,c);
strcpy(c,c1);
}
for(j=0;j<L.keynum;j++)
L.r[i].keys[j]=c[L.keynum-1-j];
}
}
int ord(char c)
{ // 返回k的映射(个位整数)
return c-'0';
}
void Distribute(SLCell r[],int i,ArrType f,ArrType e) // 算法10.15
{ // 静态键表L的r域中记录已按(keys[0],…,keys[i-1])有序。本算法按
// 第i个关键字keys[i]建立RADIX个子表,使同一子表中记录的keys[i]相同。
// f[0..RADIX-1]和e[0..RADIX-1]分别指向各子表中第一个和最后一个记录
int j,p;
for(j=0;j<RADIX;++j)
f[j]=0; // 各子表初始化为空表
for(p=r[0].next;p;p=r[p].next)
{
j=ord(r[p].keys[i]); // ord将记录中第i个关键字映射到[0..RADIX-1]
if(!f[j])
f[j]=p;
else
r[e[j]].next=p;
e[j]=p; // 将p所指的结点插入第j个子表中
}
}
int succ(int i)
{ // 求后继函数
return ++i;
}
void Collect(SLCell r[],ArrType f,ArrType e)
{ // 本算法按keys[i]自小至大地将f[0..RADIX-1]所指各子表依次链接成
// 一个链表，e[0..RADIX-1]为各子表的尾指针。算法10.16
int j,t;
for(j=0;!f[j];j=succ(j)); // 找第一个非空子表，succ为求后继函数
r[0].next=f[j];
t=e[j]; // r[0].next指向第一个非空子表中第一个结点
while(j<RADIX-1)
{
for(j=succ(j);j<RADIX-1&&!f[j];j=succ(j)); // 找下一个非空子表
if(f[j])
{ // 链接两个非空子表
r[t].next=f[j];
t=e[j];
}
}
r[t].next=0; // t指向最后一个非空子表中的最后一个结点
}
void printl(SLList L)
{ // 按链表输出静态链表
int i=L.r[0].next,j;
while(i)
{
for(j=L.keynum-1;j>=0;j--)
printf("%c",L.r[i].keys[j]);
printf(" ");
i=L.r[i].next;
}
}
void RadixSort(SLList &L)
{ // L是采用静态链表表示的顺序表。对L作基数排序，使得L成为按关键字
// 自小到大的有序静态链表，L.r[0]为头结点。算法10.17
int i;
ArrType f,e;
for(i=0;i<L.recnum;++i)
L.r[i].next=i+1;
L.r[L.recnum].next=0; // 将L改造为静态链表
for(i=0;i<L.keynum;++i)
{ // 按最低位优先依次对各关键字进行分配和收集
Distribute(L.r,i,f,e); // 第i趟分配
Collect(L.r,f,e); // 第i趟收集
printf("第%d趟收集后:\n",i+1);
printl(L);
printf("\n");
}
}
void print(SLList L)
{ // 按数组序号输出静态链表
int i,j;
printf("keynum=%d recnum=%d\n",L.keynum,L.recnum);
for(i=1;i<=L.recnum;i++)
{
printf("keys=");
for(j=L.keynum-1;j>=0;j--)
printf("%c",L.r[i].keys[j]);
printf(" otheritems=%d next=%d\n",L.r[i].otheritems,L.r[i].next);
}
}
void Sort(SLList L,int adr[]) // 改此句(类型)
{ // 求得adr[1..L.length]，adr[i]为静态链表L的第i个最小记录的序号
int i=1,p=L.r[0].next;
while(p)
{
adr[i++]=p;
p=L.r[p].next;
}
}
void Rearrange(SLList &L,int adr[]) // 改此句(类型)
{ // adr给出静态链表L的有序次序，即L.r[adr[i]]是第i小的记录。
// 本算法按adr重排L.r，使其有序。算法10.18(L的类型有变)
int i,j,k;
for(i=1;i<L.recnum;++i) // 改此句(类型)
if(adr[i]!=i)
{
j=i;
L.r[0]=L.r[i]; // 暂存记录L.r[i]
while(adr[j]!=i)
{ // 调整L.r[adr[j]]的记录到位直到adr[j]=i为止
k=adr[j];
L.r[j]=L.r[k];
adr[j]=j;
j=k; // 记录按序到位
}
L.r[j]=L.r[0];
adr[j]=j;
}
}
#define N 10
void main()
{
RedType d[N]={{278,1},{109,2},{63,3},{930,4},{589,5},{184,6},{505,7},{269,8},{8,9},{83,10}};
SLList l;
int *adr;
InitList(l,d,N);
printf("排序前(next域还没赋值):\n");
print(l);
RadixSort(l);
printf("排序后(静态链表):\n");
print(l);
adr=(int*)malloc((l.recnum)*sizeof(int));
Sort(l,adr);
Rearrange(l,adr);
printf("排序后(重排记录):\n");
print(l);
}
/*******************************************/
//归并排序
#include<stdio.h>
typedef int InfoType; // 定义其它数据项的类型
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))
#define LQ(a,b) ((a)<=(b))
#define MAXSIZE 20 // 一个用作示例的小顺序表的最大长度
typedef int KeyType; // 定义关键字类型为整型
struct RedType // 记录类型
{
KeyType key; // 关键字项
InfoType otherinfo; // 其它数据项，具体类型在主程中定义
};
struct SqList // 顺序表类型
{
RedType r[MAXSIZE+1]; // r[0]闲置或用作哨兵单元
int length; // 顺序表长度
};
void Merge(RedType SR[],RedType TR[],int i,int m,int n)
{ // 将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n] 算法10.12
int j,k,l;
for(j=m+1,k=i;i<=m&&j<=n;++k) // 将SR中记录由小到大地并入TR
if LQ(SR[i].key,SR[j].key)
TR[k]=SR[i++];
else
TR[k]=SR[j++];
if(i<=m)
for(l=0;l<=m-i;l++)
TR[k+l]=SR[i+l]; // 将剩余的SR[i..m]复制到TR
if(j<=n)
for(l=0;l<=n-j;l++)
TR[k+l]=SR[j+l]; // 将剩余的SR[j..n]复制到TR
}
void MSort(RedType SR[],RedType TR1[],int s, int t)
{ // 将SR[s..t]归并排序为TR1[s..t]。算法10.13
int m;
RedType TR2[MAXSIZE+1];
if(s==t)
TR1[s]=SR[s];
else
{
m=(s+t)/2; // 将SR[s..t]平分为SR[s..m]和SR[m+1..t]
MSort(SR,TR2,s,m); // 递归地将SR[s..m]归并为有序的TR2[s..m]
MSort(SR,TR2,m+1,t); // 递归地将SR[m+1..t]归并为有序的TR2[m+1..t]
Merge(TR2,TR1,s,m,t); // 将TR2[s..m]和TR2[m+1..t]归并到TR1[s..t]
}
}
void MergeSort(SqList &L)
{ // 对顺序表L作归并排序。算法10.14
MSort(L.r,L.r,1,L.length);
}
void print(SqList L)
{
int i;
for(i=1;i<=L.length;i++)
printf("(%d,%d)",L.r[i].key,L.r[i].otherinfo);
printf("\n");
}
#define N 7
void main()
{
RedType d[N]={{49,1},{38,2},{65,3},{97,4},{76,5},{13,6},{27,7}};
SqList l;
int i;
for(i=0;i<N;i++)
l.r[i+1]=d[i];
l.length=N;
printf("排序前:\n");
print(l);
MergeSort(l);
printf("排序后:\n");
print(l);
}
/**********************************************/
//起泡排序
#include<string.h>
#include<ctype.h>
#include<malloc.h> // malloc()等
#include<limits.h> // INT_MAX等
#include<stdio.h> // EOF(=^Z或F6),NULL
#include<stdlib.h> // atoi()
#include<io.h> // eof()
#include<math.h> // floor(),ceil(),abs()
#include<process.h> // exit()
#include<iostream.h> // cout,cin
// 函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
typedef int Status;
typedef int Boolean;
#define N 8
void bubble_sort(int a[],int n)
{ // 将a中整数序列重新排列成自小至大有序的整数序列(起泡排序)
int i,j,t;
Status change;
for(i=n-1,change=TRUE;i>1&&change;--i)
{
change=FALSE;
for(j=0;j<i;++j)
if(a[j]>a[j+1])
{
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
change=TRUE;
}
}
}
void print(int r[],int n)
{
int i;
for(i=0;i<n;i++)
printf("%d ",r[i]);
printf("\n");
}
void main()
{
int d[N]={49,38,65,97,76,13,27,49};
printf("排序前:\n");
print(d,N);
bubble_sort(d,N);
printf("排序后:\n");
print(d,N);
}
/****************************************************/
//简单选择排序
#include<stdio.h>
typedef int InfoType; // 定义其它数据项的类型
#define MAXSIZE 20 // 一个用作示例的小顺序表的最大长度
typedef int KeyType; // 定义关键字类型为整型
struct RedType // 记录类型
{
KeyType key; // 关键字项
InfoType otherinfo; // 其它数据项，具体类型在主程中定义
};
struct SqList // 顺序表类型
{
RedType r[MAXSIZE+1]; // r[0]闲置或用作哨兵单元
int length; // 顺序表长度
};
int SelectMinKey(SqList L,int i)
{ // 返回在L.r[i..L.length]中key最小的记录的序号
KeyType min;
int j,k;
k=i; // 设第i个为最小
min=L.r[i].key;
for(j=i+1;j<=L.length;j++)
if(L.r[j].key<min) // 找到更小的
{
k=j;
min=L.r[j].key;
}
return k;
}
void SelectSort(SqList &L)
{ // 对顺序表L作简单选择排序。算法10.9
int i,j;
RedType t;
for(i=1;i<L.length;++i)
{ // 选择第i小的记录，并交换到位
j=SelectMinKey(L,i); // 在L.r[i..L.length]中选择key最小的记录
if(i!=j)
{ // 与第i个记录交换
t=L.r[i];
L.r[i]=L.r[j];
L.r[j]=t;
}
}
}
void print(SqList L)
{
int i;
for(i=1;i<=L.length;i++)
printf("(%d,%d)",L.r[i].key,L.r[i].otherinfo);
printf("\n");
}
#define N 8
void main()
{
RedType d[N]={{49,1},{38,2},{65,3},{97,4},{76,5},{13,6},{27,7},{49,8}};
SqList l;
int i;
for(i=0;i<N;i++)
l.r[i+1]=d[i];
l.length=N;
printf("排序前:\n");
print(l);
SelectSort(l);
printf("排序后:\n");
print(l);
}
/************************************************/
//树形选择排序
#include<string.h>
#include<ctype.h>
#include<malloc.h> // malloc()等
#include<limits.h> // INT_MAX等
#include<stdio.h> // EOF(=^Z或F6),NULL
#include<stdlib.h> // atoi()
#include<io.h> // eof()
#include<math.h> // floor(),ceil(),abs()
#include<process.h> // exit()
#include<iostream.h> // cout,cin
// 函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
typedef int Status; // Status是函数的类型,其值是函数结果状态代码，如OK等
typedef int Boolean; // Boolean是布尔类型,其值是TRUE或FALSE
typedef int InfoType; // 定义其它数据项的类型
#define MAXSIZE 20 // 一个用作示例的小顺序表的最大长度
typedef int KeyType; // 定义关键字类型为整型
struct RedType // 记录类型
{
KeyType key; // 关键字项
InfoType otherinfo; // 其它数据项，具体类型在主程中定义
};
struct SqList // 顺序表类型
{
RedType r[MAXSIZE+1]; // r[0]闲置或用作哨兵单元
int length; // 顺序表长度
};
void TreeSort(SqList &L)
{ // 树形选择排序
int i,j,j1,k,k1,l,n=L.length;
RedType *t;
l=(int)ceil(log(n)/log(2))+1; // 完全二叉树的层数
k=(int)pow(2,l)-1; // l层完全二叉树的结点总数
k1=(int)pow(2,l-1)-1; // l-1层完全二叉树的结点总数
t=(RedType*)malloc(k*sizeof(RedType)); // 二叉树采用顺序存储结构
for(i=1;i<=n;i++) // 将L.r赋给叶子结点
t[k1+i-1]=L.r[i];
for(i=k1+n;i<k;i++) // 给多余的叶子的关键字赋无穷大
t[i].key=INT_MAX;
j1=k1;
j=k;
while(j1)
{ // 给非叶子结点赋值
for(i=j1;i<j;i+=2)
t[i].key<t[i+1].key?(t[(i+1)/2-1]=t[i]):(t[(i+1)/2-1]=t[i+1]);
j=j1;
j1=(j1-1)/2;
}
for(i=0;i<n;i++)
{
L.r[i+1]=t[0]; // 将当前最小值赋给L.r[i]
j1=0;
for(j=1;j<l;j++) // 沿树根找结点t[0]在叶子中的序号j1
t[2*j1+1].key==t[j1].key?(j1=2*j1+1):(j1=2*j1+2);
t[j1].key=INT_MAX;
while(j1)
{
j1=(j1+1)/2-1; // 序号为j1的结点的双亲结点序号
t[2*j1+1].key<=t[2*j1+2].key?(t[j1]=t[2*j1+1]):(t[j1]=t[2*j1+2]);
}
}
free(t);
}
void print(SqList L)
{
int i;
for(i=1;i<=L.length;i++)
printf("(%d,%d)",L.r[i].key,L.r[i].otherinfo);
printf("\n");
}
#define N 8
void main()
{
RedType d[N]={{49,1},{38,2},{65,3},{97,4},{76,5},{13,6},{27,7},{49,8}};
SqList l;
int i;
for(i=0;i<N;i++)
l.r[i+1]=d[i];
l.length=N;
printf("排序前:\n");
print(l);
TreeSort(l);
printf("排序后:\n");
print(l);
}
/****************************/
//堆排序
#include<stdio.h>
typedef int InfoType; // 定义其它数据项的类型
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))
#define LQ(a,b) ((a)<=(b))
#define MAXSIZE 20 // 一个用作示例的小顺序表的最大长度
typedef int KeyType; // 定义关键字类型为整型
struct RedType // 记录类型
{
KeyType key; // 关键字项
InfoType otherinfo; // 其它数据项，具体类型在主程中定义
};
struct SqList // 顺序表类型
{
RedType r[MAXSIZE+1]; // r[0]闲置或用作哨兵单元
int length; // 顺序表长度
};
typedef SqList HeapType; // 堆采用顺序表存储表示
void HeapAdjust(HeapType &H,int s,int m) // 算法10.10
{ // 已知H.r[s..m]中记录的关键字除H.r[s].key之外均满足堆的定义，本函数
// 调整H.r[s]的关键字,使H.r[s..m]成为一个大顶堆(对其中记录的关键字而言)
RedType rc;
int j;
rc=H.r[s];
for(j=2*s;j<=m;j*=2)
{ // 沿key较大的孩子结点向下筛选
if(j<m&<(H.r[j].key,H.r[j+1].key))
++j; // j为key较大的记录的下标
if(!LT(rc.key,H.r[j].key))
break; // rc应插入在位置s上
H.r[s]=H.r[j];
s=j;
}
H.r[s]=rc; // 插入
}
void HeapSort(HeapType &H)
{ // 对顺序表H进行堆排序。算法10.11
RedType t;
int i;
for(i=H.length/2;i>0;--i) // 把H.r[1..H.length]建成大顶堆
HeapAdjust(H,i,H.length);
for(i=H.length;i>1;--i)
{ // 将堆顶记录和当前未经排序子序列H.r[1..i]中最后一个记录相互交换
t=H.r[1];
H.r[1]=H.r[i];
H.r[i]=t;
HeapAdjust(H,1,i-1); // 将H.r[1..i-1]重新调整为大顶堆
}
}
void print(HeapType H)
{
int i;
for(i=1;i<=H.length;i++)
printf("(%d,%d)",H.r[i].key,H.r[i].otherinfo);
printf("\n");
}
#define N 8
void main()
{
RedType d[N]={{49,1},{38,2},{65,3},{97,4},{76,5},{13,6},{27,7},{49,8}};
HeapType h;
int i;
for(i=0;i<N;i++)
h.r[i+1]=d[i];
h.length=N;
printf("排序前:\n");
print(h);
HeapSort(h);
printf("排序后:\n");
print(h);
}
Ⅱ 关于数据结构的问题，用C语言描述
数据结构复习重点归纳笔记[清华严蔚敏版]
数据结构复习重点归纳[适于清华严版教材]
一、数据结构的章节结构及重点构成
数据结构学科的章节划分基本上为：概论，线性表，栈和队列，串，多维数组和广义表，树和二叉树，图，查找，内排，外排，文件，动态存储分配。
对于绝大多数的学校而言，“外排，文件，动态存储分配”三章基本上是不考的，在大多数高校的计算机本科教学过程中，这三章也是基本上不作讲授的。所以，大家在这三章上可以不必花费过多的精力，只要知道基本的概念即可。但是，对于报考名校特别是该校又有在试卷中对这三章进行过考核的历史，那么这部分朋友就要留意这三章了。
按照以上我们给出的章节以及对后三章的介绍，数据结构的章节比重大致为：
概论：内容很少，概念简单，分数大多只有几分，有的学校甚至不考。
线性表：基础章节，必考内容之一。考题多数为基本概念题，名校考题中，鲜有大型算法设计题。如果有，也是与其它章节内容相结合。
栈和队列：基础章节，容易出基本概念题，必考内容之一。而栈常与其它章节配合考查，也常与递归等概念相联系进行考查。
串 ：基础章节，概念较为简单。专门针对于此章的大型算法设计题很少，较常见的是根据KMP进行算法分析。
多维数组及广义表
：基础章节，基于数组的算法题也是常见的，分数比例波动较大，是出题的“可选单元”或“侯补单元”。一般如果要出题，多数不会作为大题出。数组常与“查找，排序”等章节结合来作为大题考查。
树和二叉树
：重点难点章节，各校必考章节。各校在此章出题的不同之处在于，是否在本章中出一到两道大的算法设计题。通过对多所学校的试卷分析，绝大多数学校在本章都曾有过出大型算法设计题的历史。
图 ：重点难点章节，名校尤爱考。如果作为重点来考，则多出现于分析与设计题型当中，可与树一章共同构成算法设计大题的题型设计。
查找
：重点难点章节，概念较多，联系较为紧密，容易混淆。出题时可以作为分析型题目给出，在基本概念型题目中也较为常见。算法设计型题中可以数组结合来考查，也可以与树一章结合来考查。
排序
：与查找一章类似，本章同属于重点难点章节，且概念更多，联系更为紧密，概念之间更容易混淆。在基本概念的考查中，尤爱考各种排序算法的优劣比较此类的题。算法设计大题中，如果作为出题，那么常与数组结合来考查。
二、数据结构各章节重点勾划：
第0章 概述
本章主要起到总领作用，为读者进行数据结构的学习进行了一些先期铺垫。大家主要注意以下几点：数据结构的基本概念，时间和空间复杂度的概念及度量方法，算法设计时的注意事项。本章考点不多，只要稍加注意理解即可。
第一章 线性表
作为线性结构的开篇章节，线性表一章在线性结构的学习乃至整个数据结构学科的学习中，其作用都是不可低估的。在这一章，第一次系统性地引入链式存储的概念，链式存储概念将是整个数据结构学科的重中之重，无论哪一章都涉及到了这个概念。
总体来说，线性表一章可供考查的重要考点有以下几个方面：
1.线性表的相关基本概念，如：前驱、后继、表长、空表、首元结点，头结点，头指针等概念。
2.线性表的结构特点，主要是指：除第一及最后一个元素外，每个结点都只有一个前趋和只有一个后继。
3.线性表的顺序存储方式及其在具体语言环境下的两种不同实现：表空间的静态分配和动态分配。静态链表与顺序表的相似及不同之处。
4.线性表的链式存储方式及以下几种常用链表的特点和运算：单链表、循环链表，双向链表，双向循环链表。其中，单链表的归并算法、循环链表的归并算法、双向链表及双向循环链表的插入和删除算法等都是较为常见的考查方式。此外，近年来在不少学校中还多次出现要求用递归算法实现单链表输出（可能是顺序也可能是倒序）的问题。
在链表的小题型中，经常考到一些诸如：判表空的题。在不同的链表中，其判表空的方式是不一样的，请大家注意。
5.线性表的顺序存储及链式存储情况下，其不同的优缺点比较，即其各自适用的场合。单链表中设置头指针、循环链表中设置尾指针而不设置头指针以及索引存储结构的各自好处。
第二章 栈与队列
栈与队列，是很多学习DS的同学遇到第一只拦路虎，很多人从这一章开始坐晕车，一直晕到现在。所以，理解栈与队列，是走向DS高手的一条必由之路，。
学习此章前，你可以问一下自己是不是已经知道了以下几点：
1.栈、队列的定义及其相关数据结构的概念，包括：顺序栈，链栈，共享栈，循环队列，链队等。栈与队列存取数据（请注意包括：存和取两部分）的特点。
2.递归算法。栈与递归的关系，以及借助栈将递归转向于非递归的经典算法：n!阶乘问题，fib数列问题，hanoi问题，背包问题，二叉树的递归和非递归遍历问题，图的深度遍历与栈的关系等。其中，涉及到树与图的问题，多半会在树与图的相关章节中进行考查。
3.栈的应用：数值表达式的求解，括号的配对等的原理，只作原理性了解，具体要求考查此为题目的算法设计题不多。
4.循环队列中判队空、队满条件，循环队列中入队与出队算法。
如果你已经对上面的几点了如指掌，栈与队列一章可以不看书了。注意，我说的是可以不看书，并不是可以不作题哦。
第三章 串
经历了栈一章的痛苦煎熬后，终于迎来了串一章的柳暗花明。
串，在概念上是比较少的一个章节，也是最容易自学的章节之一，但正如每个过来人所了解的，KMP算法是这一章的重要关隘，突破此关隘后，走过去又是一马平川的大好DS山河了，呵呵。
串一章需要攻破的主要堡垒有：
1.串的基本概念，串与线性表的关系（串是其元素均为字符型数据的特殊线性表），空串与空格串的区别，串相等的条件
2.串的基本操作，以及这些基本函数的使用，包括：取子串，串连接，串替换，求串长等等。运用串的基本操作去完成特定的算法是很多学校在基本操作上的考查重点。
3.顺序串与链串及块链串的区别和联系，实现方式。
4.KMP算法思想。KMP中next数组以及nextval数组的求法。明确传统模式匹配算法的不足，明确next数组需要改进之外。其中，理解算法是核心，会求数组是得分点。不用我多说，这一节内容是本章的重中之重。可能进行的考查方式是：求next和nextval数组值，根据求得的next或nextval数组值给出运用KMP算法进行匹配的匹配过程。
第四章 数组与广义表
学过程序语言的朋友，数组的概念我们已经不是第一次见到了，应该已经“一回生，二回熟”了，所以，在概念上，不会存在太大障碍。但作为考研课程来说，本章的考查重点可能与大学里的程序语言所关注的不太一样，下面会作介绍。
广义表的概念，是数据结构里第一次出现的。它是线性表或表元素的有限序列，构成该结构的每个子表或元素也是线性结构的，所以，这一章也归入线性结构中。
本章的考查重点有：
1.多维数组中某数组元素的position求解。一般是给出数组元素的首元素地址和每个元素占用的地址空间并组给出多维数组的维数，然后要求你求出该数组中的某个元素所在的位置。
2.明确按行存储和按列存储的区别和联系，并能够按照这两种不同的存储方式求解1中类型的题。
3.将特殊矩阵中的元素按相应的换算方式存入数组中。这些矩阵包括：对称矩阵，三角矩阵，具有某种特点的稀疏矩阵等。熟悉稀疏矩阵的三种不同存储方式：三元组，带辅助行向量的二元组，十字链表存储。掌握将稀疏矩阵的三元组或二元组向十字链表进行转换的算法。
4.广义表的概念，特别应该明确表头与表尾的定义。这一点，是理解整个广义表一节算法的基础。近来，在一些学校中，出现了这样一种题目类型：给出对某个广义表L若干个求了若干次的取头和取尾操作后的串值，要求求出原广义表L。大家要留意。
5.与广义表有关的递归算法。由于广义表的定义就是递归的，所以，与广义表有关的算法也常是递归形式的。比如：求表深度，复制广义表等。这种题目，可以根据不同角度广义表的表现形式运用两种不同的方式解答：一是把一个广义表看作是表头和表尾两部分，分别对表头和表尾进行操作；二是把一个广义表看作是若干个子表，分别对每个子表进行操作。
第五章 树与二叉树
从对线性结构的研究过度到对树形结构的研究，是数据结构课程学习的一次跃变，此次跃变完成的好坏，将直接关系到你到实际的考试中是否可以拿到高分，而这所有的一切，将最终影响你的专业课总分。所以，树这一章的重要性，已经不说自明了。
总体来说，树一章的知识点包括：
二叉树的概念、性质和存储结构，二叉树遍历的三种算法（递归与非递归），在三种基本遍历算法的基础上实现二叉树的其它算法，线索二叉树的概念和线索化算法以及线索化后的查找算法，最优二叉树的概念、构成和应用，树的概念和存储形式，树与森林的遍历算法及其与二叉树遍历算法的联系，树与森林和二叉树的转换。
下面我们来看考试中对以上知识的主要考查方法：
1.二叉树的概念、性质和存储结构
考查方法可有：直接考查二叉树的定义，让你说明二叉树与普通双分支树的区别；考查满二叉树和完全二叉树的性质，普通二叉树的五个性质：第i层的最多结点数，深度为k的二叉树的最多结点数，n0=n2+1的性质，n个结点的完全二叉树的深度，顺序存储二叉树时孩子结点与父结点之间的换算关系（左为：2*i，右为：2*i+1）。
二叉树的顺序存储和二叉链表存储的各自优缺点及适用场合，二叉树的三叉链表表示方法。
2.二叉树的三种遍历算法
这一知识点掌握的好坏，将直接关系到树一章的算法能否理解，进而关系到树一章的算法设计题能否顺利完成。二叉树的遍历算法有三种：先序，中序和后序。其划分的依据是视其每个算法中对根结点数据的访问顺序而定。不仅要熟练掌握三种遍历的递归算法，理解其执行的实际步骤，并且应该熟练掌握三种遍历的非递归算法。由于二叉树一章的很多算法，可以直接根据三种递归算法改造而来（比如：求叶子个数），所以，掌握了三种遍历的非递归算法后，对付诸如：“利用非递归算法求二叉树叶子个数”这样的题目就下笔如有神了。我会在另一篇系列文章（）里给出三种遍历的递归和非递归算法的背记版，到时请大家一定熟记。
3.可在三种遍历算法的基础上改造完成的其它二叉树算法：
求叶子个数，求二叉树结点总数，求度为1或度为2的结点总数，复制二叉树，建立二叉树，交换左右子树，查找值为n的某个指定结点，删除值为n的某个指定结点，诸如此类等等等等。如果你可以熟练掌握二叉树的递归和非递归遍历算法，那么解决以上问题就是小菜一碟了。
4.线索二叉树：
线索二叉树的引出，是为避免如二叉树遍历时的递归求解。众所周知，递归虽然形式上比较好理解，但是消耗了大量的内存资源，如果递归层次一多，势必带来资源耗尽的危险，为了避免此类情况，线索二叉树便堂而皇之地出现了。对于线索二叉树，应该掌握：线索化的实质，三种线索化的算法，线索化后二叉树的遍历算法，基本线索二叉树的其它算法问题（如：查找某一类线索二叉树中指定结点的前驱或后继结点就是一类常考题）。
5.最优二叉树（哈夫曼树）：
最优二叉树是为了解决特定问题引出的特殊二叉树结构，它的前提是给二叉树的每条边赋予了权值，这样形成的二叉树按权相加之和是最小的。最优二叉树一节，直接考查算法源码的很少，一般是给你一组数据，要求你建立基于这组数据的最优二叉树，并求出其最小权值之和，此类题目不难，属送分题。
6.树与森林：
二叉树是一种特殊的树，这种特殊不仅仅在于其分支最多为2以及其它特征，一个最重要的特殊之处是在于：二叉树是有序的！即：二叉树的左右孩子是不可交换的，如果交换了就成了另外一棵二叉树，这样交换之后的二叉树与原二叉树我们认为是不相同的两棵二叉树。但是，对于普通的双分支树而言，不具有这种性质。
树与森林的遍历，不像二叉树那样丰富，他们只有两种遍历算法：先根与后根（对于森林而言称作：先序与后序遍历）。在难度比较大的考试中，也有基于此二种算法的基础上再进行扩展要求你利用这两种算法设计其它算法的，但一般院校很少有这种考法，最多只是要求你根据先根或后根写出他们的遍历序列。此二者的先根与后根遍历与二叉树中的遍历算法是有对应关系的：先根遍历对应二叉树的先序遍历，而后根遍历对应二叉树的中序遍历。这一点成为很多学校的考点，考查的方式不一而足，有的直接考此句话，有的是先让你求解遍历序列然后回答这个问题。二叉树、树与森林之所以能有以上的对应关系，全拜二叉链表所赐。二叉树使用二叉链表分别存放他的左右孩子，树利用二叉链表存储孩子及兄弟（称孩子兄弟链表），而森林也是利用二叉链表存储孩子及兄弟。
树一章，处处是重点，道道是考题，大家务必个个过关。
第六章 图
如果说，从线性结构向树形结构研究的转变，是数据结构学科对数据组织形式研究的一次升华，那么从树形结构的研究转到图形结构的研究，则进一步让我们看到了数据结构对于解决实际问题的重大推动作用。
图这一章的特点是：概念繁多，与离散数学中图的概念联系紧密，算法复杂，极易被考到，且容易出大题，尤其是名校，作为考研课程，如果不考查树与图两章的知识，几乎是不可想象的。
下面我们看一下图这一章的主要考点以及这些考点的考查方式：
1.考查有关图的基本概念问题：
这些概念是进行图一章学习的基础，这一章的概念包括：图的定义和特点，无向图，有向图，入度，出度，完全图，生成子图，路径长度，回路，（强）连通图，（强）连通分量等概念。与这些概念相联系的相关计算题也应该掌握。
2.考查图的几种存储形式：
图的存储形式包括：邻接矩阵，（逆）邻接表，十字链表及邻接多重表。在考查时，有的学校是给出一种存储形式，要求考生用算法或手写出与给定的结构相对应的该图的另一种存储形式。
3.考查图的两种遍历算法：深度遍历和广度遍历
深度遍历和广度遍历是图的两种基本的遍历算法，这两个算法对图一章的重要性等同于“先序、中序、后序遍历”对于二叉树一章的重要性。在考查时，图一章的算法设计题常常是基于这两种基本的遍历算法而设计的，比如：“求最长的最短路径问题”和“判断两顶点间是否存在长为K的简单路径问题”，就分别用到了广度遍历和深度遍历算法。
4.生成树、最小生成树的概念以及最小生成树的构造：PRIM算法和KRUSKAL算法。
考查时，一般不要求写出算法源码，而是要求根据这两种最小生成树的算法思想写出其构造过程及最终生成的最小生成树。
5.拓扑排序问题：
拓扑排序有两种方法，一是无前趋的顶点优先算法，二是无后继的顶点优先算法。换句话说，一种是“从前向后”的排序，一种是“从后向前”排。当然，后一种排序出来的结果是“逆拓扑有序”的。
6.关键路径问题：
这个问题是图一章的难点问题。理解关键路径的关键有三个方面：一是何谓关键路径，二是最早时间是什么意思、如何求，三是最晚时间是什么意思、如何求。简单地说，最早时间是通过“从前向后”的方法求的，而最晚时间是通过“从后向前”的方法求解的，并且，要想求最晚时间必须是在所有的最早时间都已经求出来之后才能进行。这个问题拿来直接考算法源码的不多，一般是要求按照书上的算法描述求解的过程和步骤。
在实际设计关键路径的算法时，还应该注意以下这一点：采用邻接表的存储结构，求最早时间和最晚时间要采用不同的处理方法，即：在算法初始时，应该首先将所有顶点的最早时间全部置为0。关键路径问题是工程进度控制的重要方法，具有很强的实用性。
7.最短路径问题：
与关键路径问题并称为图一章的两只拦路虎。概念理解是比较容易的，关键是算法的理解。最短路径问题分为两种：一是求从某一点出发到其余各点的最短路径；二是求图中每一对顶点之间的最短路径。这个问题也具有非常实用的背景特色，一个典型的应该就是旅游景点及旅游路线的选择问题。解决第一个问题用DIJSKTRA算法，解决第二个问题用FLOYD算法。注意区分。
第七章 查找
在不少数据结构的教材中，是把查找与排序放入高级数据结构中的。应该说，查找和排序两章是前面我们所学的知识的综合运用，用到了树、也用到了链表等知识，对这些数据结构某一方面的运用就构成了查找和排序。
现实生活中，search几乎无处不在，特别是现在的网络时代，万事离不开search，小到文档内文字的搜索，大到INTERNET上的搜索，search占据了我们上网的大部分时间。
在复习这一章的知识时，你需要先弄清楚以下几个概念：
关键字、主关键字、次关键字的含义；静态查找与动态查找的含义及区别；平均查找长度ASL的概念及在各种查找算法中的计算方法和计算结果，特别是一些典型结构的ASL值，应该记住。
在DS的教材中，一般将search分为三类：1st，在顺序表上的查找；2nd，在树表上的查找；3rd，在哈希表上的查找。下面详细介绍其考查知识点及考查方式：
1.线性表上的查找：
主要分为三种线性结构：顺序表，有序顺序表，索引顺序表。对于第一种，我们采用传统查找方法，逐个比较。对于及有序顺序表我们采用二分查找法。对于第三种索引结构，我们采用索引查找算法。考生需要注意这三种表下的ASL值以及三种算法的实现。其中，二分查找还要特别注意适用条件以及其递归实现方法。
2.树表上的查找：
这是本章的重点和难点。由于这一节介绍的内容是使用树表进行的查找，所以很容易与树一间的某些概念相混淆。本节内容与树一章的内容有联系，但也有很多不同，应注意规纳。树表主要分为以下几种：二叉排序树，平衡二叉树，B树，键树。其中，尤以前两种结构为重，也有部分名校偏爱考B树的。由于二叉排序树与平衡二叉树是一种特殊的二叉树，所以与二叉树的联系就更为紧密，二叉树一章学好了，这里也就不难了。
二叉排序树，简言之，就是“左小右大”，它的中序遍历结果是一个递增的有序序列。平衡二叉树是二叉排序树的优化，其本质也是一种二叉排序树，只不过，平衡二叉树对左右子树的深度有了限定：深度之差的绝对值不得大于1。对于二叉排序树，“判断某棵二叉树是否二叉排序树”这一算法经常被考到，可用递归，也可以用非递归。平衡二叉树的建立也是一个常考点，但该知识点归根结底还是关注的平衡二叉树的四种调整算法，所以应该掌握平衡二叉树的四种调整算法，调整的一个参照是：调整前后的中序遍历结果相同。
B树是二叉排序树的进一步改进，也可以把B树理解为三叉、四叉....排序树。除B树的查找算法外，应该特别注意一下B树的插入和删除算法。因为这两种算法涉及到B树结点的分裂和合并，是一个难点。B树是报考名校的同学应该关注的焦点之一。
键树也称字符树，特别适用于查找英文单词的场合。一般不要求能完整描述算法源码，多是根据算法思想建立键树及描述其大致查找过程。
3.基本哈希表的查找算法：
哈希一词，是外来词，译自“hash”一词，意为：散列或杂凑的意思。哈希表查找的基本思想是：根据当前待查找数据的特征，以记录关键字为自变量，设计一个function，该函数对关键字进行转换后，其解释结果为待查的地址。基于哈希表的考查点有：哈希函数的设计，冲突解决方法的选择及冲突处理过程的描述。
第八章 内部排序
内排是DS课程中最后一个重要的章节，建立在此章之上的考题可以有多种类型：填空，选择，判断乃至大型算法题。但是，归结到一点，就是考查你对书本上的各种排序算法及其思想以及其优缺点和性能指标（时间复杂度）能否了如指掌。
这一章，我们对重点的规纳将跟以上各章不同。我们将从以下几个侧面来对排序一章进行不同的规纳，以期能更全面的理解排序一章的总体结构及各种算法。
从排序算法的种类来分，本章主要阐述了以下几种排序方法：插入、选择、交换、归并、计数等五种排序方法。
其中，在插入排序中又可分为：直接插入、折半插入、2路插入、希尔排序。这几种插入排序算法的最根本的不同点，说到底就是根据什么规则寻找新元素的插入点。直接插入是依次寻找，折半插入是折半寻找。希尔排序，是通过控制每次参与排序的数的总范围“由小到大”的增量来实现排序效率提高的目的。
交换排序，又称冒泡排序，在交换排序的基础上改进又可以得到快速排序。快速排序的思想，一语以敝之：用中间数将待排数据组一分为二。快速排序，在处理的“问题规模”这个概念上，与希尔有点相反，快速排序，是先处理一个较大规模，然后逐渐把处理的规模降低，最终达到排序的目的。
选择排序，相对于前面几种排序算法来说，难度大一点。具体来说，它可以分为：简单选择、树选择、堆排。这三种方法的不同点是，根据什么规则选取最小的数。简单选择，是通过简单的数组遍历方案确定最小数；树选择，是通过“锦标赛”类似的思想，让两数相比，不断淘汰较大（小）者，最终选出最小（大）数；而堆排序，是利用堆这种数据结构的性质，通过堆元素的删除、调整等一系列操作将最小数选出放在堆顶。堆排序中的堆建立、堆调整是重要考点。树选择排序，也曾经在一些学校中的大型算法题中出现，请大家注意。
归并排序，故名思义，是通过“归并”这种操作完成排序的目的，既然是归并就必须是两者以上的数据集合才可能实现归并。所以，在归并排序中，关注最多的就是2路归并。算法思想比较简单，有一点，要铭记在心：归并排序是稳定排序。
基数排序，是一种很特别的排序方法，也正是由于它的特殊，所以，基数排序就比较适合于一些特别的场合，比如扑克牌排序问题等。基数排序，又分为两种：多关键字的排序（扑克牌排序），链式排序（整数排序）。基数排序的核心思想也是利用“基数空间”这个概念将问题规模规范、变小，并且，在排序的过程中，只要按照基排的思想，是不用进行关键字比较的，这样得出的最终序列就是一个有序序列。
本章各种排序算法的思想以及伪代码实现，及其时间复杂度都是必须掌握的，学习时要多注意规纳、总结、对比。此外，对于教材中的10.7节，要求必须熟记，在理解的基础上记忆，这一节几乎成为很多学校每年的必考点。
至此，数据结构所有章节的章节重点问题，我们已经规纳完毕，使用清华严版教材的同学，在复习的同时，可以参照本贴给出的重点进行复习。但是，由于作者本人水平有限，可能有很多考点没有规纳出来，也可能有些考点规纳有误，在此，作者本人诚恳希望诸位朋友直面提出，我会不断完善和发布新的关于数据结构复习的总结以及笔记
严蔚敏数据结构为主的笔记二
第二章：线性表(包括习题与答案及要点)
--------------------------------------------------------------------------------
本章的重点是掌握顺序表和单链表上实现的各种基本算法及相关的时间性能分析，难点是使用本章所学的基本知识设计有效算法解决与线性表相关的应用问题。
要求达到<识记>层次的内容有:线性表的逻辑结构特征；线性表上定义的基本运算，并利用基本运算构造出较复杂的运算。
要求达到<综合应用>层次的内容有：顺序表的含义及特点，顺序表上的插入、删除操作及其平均时间性能分析，解决简单应用问题。
链表如何表示线性表中元素之间的逻辑关系；单链表、双链表、循环链表链接方式上的区别；单链表上实现的建表、查找、插入和删除等基本算法及其时间复杂度。循环链表上尾指针取代头指针的作用，以及单循环链表上的算法与单链表上相应算法的异同点。双链表的定义和相关算法。利用链表设计算法解决简单应用问题。
要求达到<领会>层次的内容就是顺序表和链表的比较，以及如何选择其一作为其存储结构才能取得较优的时空性能。
--------------------------------------------------------------------------------
线性表的逻辑结构特征是很容易理解的，如其名，它的逻辑结构特征就好象是一条线，上面打了一个个结，很形象的，如果这条线上面有结，那么它就是非空表，只能有一个开始结点，有且只能有一个终端结点，其它的结前后所相邻的也只能是一个结点(直接前趋和直接后继)。
关于线性表上定义的基本运算，主要有构造空表、求表长、取结点、查找、插入、删除等。
--------------------------------------------------------------------------------
线性表的逻辑结构和存储结构之间的关系。在计算机中，如何把线性表的结点存放到存储单元中，就有许多方法，最简单的方法就是按顺序存储。就是按线性表的逻辑结构次序依次存放在一组地址连续的存储单元中。在存储单元中的各元素的物理位置和逻辑结构中各结点相邻关系是一致的。
在顺序表中实现的基本运算主要讨论了插入和删除两种运算。相关的算法我们通过练习掌握。对于顺序表的插入和删除运算，其平均时间复杂度均为O(n)。
--------------------------------------------------------------------------------
线性表的链式存储结构。它与顺序表不同，链表是用一组任意的存储单元来存放线性表的结点，这组存储单元可以分布在内存中任何位置上。因此，链表中结点的逻辑次序和物理次序不一定相同。所以为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还存储了其后继结点的地址信息(即
Ⅲ C语言排序有哪些方法 详细点
排序方法吗应该和语言没有太紧密的关系，关键看数据类型和结构，一般常用的排序方法有：
1 插入排序——细分的话还可有（1）直接插入排序（2）折半插入排序（3）希尔排序（4）2-路插入排序（5）表插入排序 等
2 比较排序——如冒泡排序，快速排序 等
3 选择排序——如简单选择排序，树形选择排序，堆排序 等
4 归并排序——简单的如 2-路归并排序 等
5 基数排序
等等
一般情况下，如果数据不大，只是简单的自己练习或简单的几个十几个或几十个数据的话，效率分不出多少来，常用冒泡，直接插入，简单选择这几种简单的时间复杂度为O（n2）的排序方法就可以。这里举一个简单的小例子——比较排序中的——冒泡排序 如下：
//其中a[]是用于排序的数组变量的首地址，也即数组名,a[0]不放数据，
//用于交换时的辅助存储空间，数据从a[1]开始存放，n表示存放的数据个数
void bubble_sort(int a[], int n){
int i = 0, j = 0, change = 0;//change用于记录当前次比较是否进行了交换
for(i = n - 1, change = 1; i >= 1 && change; i--){//如果change是0，即已经排好序不用再进行比较了
change = 0;//将当前次的change赋值为0，记录不交换即下次不用比较了
for(j = 1; j <= i; j++){//内循环依次将相邻的两个记录进行比较
if(a[j] > a[j+1]){//小的前移，最大的移动到本次的最后一项去
a[0] = a[j+1];
a[j+1] = a[j];
a[j] = a[0];
change = 1;//进行了交换的标记
}
}
}
}
Ⅳ C语言数组排序方法
选择排序的原理是，每次从待排序数字中挑选出最大（最小）数字，放在有序序列的末尾。实际操作中，只需要在这个数组中将挑出来的数字与前面的数字交换即可。例如：4
1 5
2 3找到最小的1，1和4交换1
4 5
2
3找到最小的2，2和4交换1
2
5
4
3找到最小的3，3和5交换1
2
3
4
5找到最小的4，4和4交换（不交换也可）可见，选择排序需要一个双重循环来完成，因此它的复杂度是O(n^2)在数据量比较大时，不建议使用这种排序方法。 其他排序方法有很多，你甚至可以自己根据不同数据规模设计不同的排序方法。比较常见的有冒泡排序，插入排序（这两种和选择排序一样，都是O(n^2)），二分法插入排序（降低了一些复杂度，但是涉及到大规模数据移动，效率依然不高），快速排序（平均复杂度O(nlogn)，但是不稳定，最坏情况O(n^2)），随机化快速排序（很大程度上避免了最坏情况的出现），堆排序（O(nlogn)，编程复杂度高），基数排序（理论复杂度O(n)，实际要比这个慢。甚至能应付字符串排序，但是编程复杂度高，牵扯到其他数据结构），桶排序（O(n)，编程简单，效率高，但是应付的数据范围不能太大，受到内存大小的限制）。 平时比较常用的就是快速排序，程序简单，效率也可以接受。 这是我了解的一些东西，希望对你有帮助。
Ⅳ 求基数排序的算法代码C语言
void Sort(int *arr, int n)
{
int max = arr[0];
for (int i = 1; i < n; i++)
{
if (arr[i] > max)
max = arr[i];
}
vector<int> *bucket = new vector<int>[max / 10 + 1];
for (int i = 0; i < n; i++)
{
int change = arr[i] / 10; //元素arr[i]所在的桶编号
bucket[change].push_back(arr[i]);
}
for (int i = 0; i < n; i++)
{
if (bucket[i].size() > 0)
{
sort(bucket[i].begin(), bucket[i].end()); //桶内排序
}
}
int index = 0;
for (int i = 0; i < n; i++) //桶遍历
{
for (int j = 0; j < bucket[i].size(); j++) //遍历桶内元素
{
arr[index++] = bucket[i][j];
}
}
}
Ⅵ 求c语言基数排序与桶排序的源代码
基数排序：
#include<math.h>
testBS()
{
inta[]={2,343,342,1,123,43,4343,433,687,654,3};
int*a_p=a;
//计算数组长度
intsize=sizeof(a)/sizeof(int);
//基数排序
bucketSort3(a_p,size);
//打印排序后结果
inti;
for(i=0;i<size;i++)
{
printf("%d ",a[i]);
}
intt;
scanf("%d",t);
}
//基数排序
voidbucketSort3(int*p,intn)
{
//获取数组中的最大数
intmaxNum=findMaxNum(p,n);
//获取最大数的位数，次数也是再分配的次数。
intloopTimes=getLoopTimes(maxNum);
inti;
//对每一位进行桶分配
for(i=1;i<=loopTimes;i++)
{
sort2(p,n,i);
}
}
//获取数字的位数
intgetLoopTimes(intnum)
{
intcount=1;
inttemp=num/10;
while(temp!=0)
{
count++;
temp=temp/10;
}
returncount;
}
//查询数组中的最大数
intfindMaxNum(int*p,intn)
{
inti;
intmax=0;
for(i=0;i<n;i++)
{
if(*(p+i)>max)
{
max=*(p+i);
}
}
returnmax;
}
//将数字分配到各自的桶中，然后按照桶的顺序输出排序结果
voidsort2(int*p,intn,intloop)
{
//建立一组桶此处的20是预设的根据实际数情况修改
intbuckets[10][20]={};
//求桶的index的除数
//如798个位桶index=(798/1)%10=8
//十位桶index=(798/10)%10=9
//百位桶index=(798/100)%10=7
//tempNum为上式中的1、10、100
inttempNum=(int)pow(10,loop-1);
inti,j;
for(i=0;i<n;i++)
{
introw_index=(*(p+i)/tempNum)%10;
for(j=0;j<20;j++)
{
if(buckets[row_index][j]==NULL)
{
buckets[row_index][j]=*(p+i);
break;
}
}
}
//将桶中的数，倒回到原有数组中
intk=0;
for(i=0;i<10;i++)
{
for(j=0;j<20;j++)
{
if(buckets[i][j]!=NULL)
{
*(p+k)=buckets[i][j];
buckets[i][j]=NULL;
k++;
}
}
}
}
桶排序
#include<stdio.h>
#defineMAXNUM100
voidbucksort(intarr[],intN,intM)
{
intcount[MAXNUM];
for(inti=0;i<=M;i++)
{
count[i]=0;
}
for(inti=0;i<N;i++)
{
++count[arr[i]];
}
for(inti=0;i<=M;i++)
{
for(intj=1;j<=count[i];j++)
{
printf("%d",i);
}
}
}
intmain()
{
inta[]={2,5,6,12,4,8,8,6,7,8,8,10,7,6};
bucksort(a,sizeof(a)/sizeof(a[0]),12);
return0;
}
Ⅶ c语言，基数排序
如图
//#pragmaGCCdiagnosticerror"-std=c11"
#include<stdlib.h>//有随机数库
#include<malloc.h>
#include<time.h>//用于产生随机数种子
#include<string.h>
#include<stdio.h>
#defineLEN30//要多长这里改就行
intA[LEN];
intascend(constvoid*a,constvoid*b){
return*((int*)a)-*((int*)b);
}
voidprintArr(intA[],intlen){
inti;
for(i=0;i<len;++i){
printf("%d",A[i]);
if((i+1)%10==0)putchar('
');//10个数换一行
}
}
intmain(){
inti;
srand(time(0));//置随机数种子
printf("生成随机数：↓
");
for(i=0;i<LEN;++i){
A[i]=rand();
}
printArr(A,LEN);
printf("
排序后：↓
");
qsort(A,LEN,sizeof(int),ascend);
printArr(A,LEN);
return0;
}
Ⅷ 什么是基数排序啊
基数排序，是”数据结构“课程中，排序算法的一种。基数排序是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法。
如果你感兴趣。想进一步了解的话。可以参阅《数据结构（C语言版）》---严蔚敏着。清华大学出版社出版。
Ⅸ c语言中排序方法
1、冒泡排序（最常用）
冒泡排序是最简单的排序方法：原理是：从左到右，相邻元素进行比较。每次比较一轮，就会找到序列中最大的一个或最小的一个。这个数就会从序列的最右边冒出来。（注意每一轮都是从a[0]开始比较的）
以从小到大排序为例，第一轮比较后，所有数中最大的那个数就会浮到最右边；第二轮比较后，所有数中第二大的那个数就会浮到倒数第二个位置……就这样一轮一轮地比较，最后实现从小到大排序。
2、鸡尾酒排序
鸡尾酒排序又称双向冒泡排序、鸡尾酒搅拌排序、搅拌排序、涟漪排序、来回排序或快乐小时排序, 是冒泡排序的一种变形。该算法与冒泡排序的不同处在于排序时是以双向在序列中进行排序。
原理：数组中的数字本是无规律的排放，先找到最小的数字，把他放到第一位，然后找到最大的数字放到最后一位。然后再找到第二小的数字放到第二位，再找到第二大的数字放到倒数第二位。以此类推，直到完成排序。
3、选择排序
思路是设有10个元素a[1]-a[10]，将a[1]与a[2]-a[10]比较，若a[1]比a[2]-a[10]都小，则不进行交换。若a[2]-a[10]中有一个以上比a[1]小，则将其中最大的一个与a[1]交换，此时a[1]就存放了10个数中最小的一个。同理，第二轮拿a[2]与a[3]-a[10]比较，a[2]存放a[2]-a[10]中最小的数，以此类推。
4、插入排序
插入排序是在一个已经有序的小序列的基础上，一次插入一个元素*
一般来说，插入排序都采用in-place在数组上实现。
具体算法描述如下：
⒈ 从第一个元素开始，该元素可以认为已经被排序
⒉ 取出下一个元素，在已经排序的元素序列中从后向前扫描
⒊ 如果该元素（已排序）大于新元素，将该元素移到下一位置
⒋ 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
⒌ 将新元素插入到下一位置中
⒍ 重复步骤2~5
Ⅹ C语言（简单的）编写程序输入一维整形数组a[10],将其按由小到大排序后输出
这个应该用起泡法排序算法。
#include<stdio.h>
intmain(){
inta[10];inti,j,k;
printf("input10numbers: ");
for(i=0;i<10;i++）{//输入十个数，一次循环输入10次
scanf("%d",&a[i]);
printf(" ");//换行
for(j=0;j<9;j++)//从小到大换行经典方法四行
for(i=0;i<9;i++)
if(a[i]>a[i+1])
{t=a[i];a[i]=a[i+1];a[i+1]=t;}
printf(”thesortednumbers: ”）；
for（i=0;i<10;i++）
printf("%d",a[i]);
printf(" ");
}
}
结果演示：