设计一程序将文件中的学生信息读出，按先后顺序建立链表，并对链表中的学生记录按总分降序排序，要排名。_百度知道用java编写程序实现单链表，要提供插入，删除，排序，统计等功能，链表节点中的数据要求是整数。_百度知道c习题（157）
给定程序中，函数fun的功能是将带头节点的单向链表节点数据中的数据从小到大排序，即若原链表节点数据从头至尾的数据为：10、4、8、6，排序后链表节点数据从头至尾的数据为：2,、4、6、8、10.
#define _CRT_SECURE_NO_WARNINGS
#include&stdio.h&
#include&stdlib.h&
#define N 6
typedef struct node
struct node *
void fun(NODE *h)
NODE *p, *q;
if (p-&data & q-&data)
p-&data = q-&
NODE *creatlist(int a[])
NODE *h, *p, *q;
h = (NODE *)malloc(sizeof(NODE));
h-&next = NULL;
for (i = 0;i & N;i++)
q = (NODE*)malloc(sizeof(NODE));
q-&data = a[i];
q-&next = NULL;
if (h-&next == NULL)
h-&next = p =
void outlist(NODE *h)
if (p == NULL)
printf(&The list is NULL!\n&);
printf(&\nHead &);
printf(&-&%d&, p-&data);
} while (p != NULL);
printf(&-&End\n&);
int main()
int a[N] = { 0,10,2,4,8,6 };
head = creatlist(a);
printf(&\nThe original list:\n&);
outlist(head);
fun(head);
printf(&\nThe list after sorting:\n&);
outlist(head);
getchar();
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：22127次
积分：1903
积分：1903
排名：第15106名
原创：176篇
(1)(54)(111)(6)(1)(3)输入一组数据，存放在一个链表中，然后对其进行排序，并显示输出排序_百度知道排序的分类：
1 内部排序
&内部排序：在整个排序过程中不需不访问外存便能完成，称这样的排序问题为内部排序；
1.1 插入排序
&&&&& 插入排序： 将无序序列中的一个或几个记录&插入&到有序的序列中，从而增加记录的有序序列的长度。
&&&& 主要思想是将第一个元素看做是有序的，从第二个元素起将待排序的元素插入到有序序列中，使序列逐渐扩大，直到所有的元素都插入到有序序类中。
直接插入排序
&&& 基本思想是将记录R[i]插入到有序序列R[1..i-1],使记录的有序序列从R[1..i-1]变为R[1..i]。
&&& 直接插入排序算法最好情况下的时间复杂度为O(n),最坏情况的时间复杂度和平均时间复杂度为O(n^2)。
#include "stdafx.h"
#include "stdafx.h"
#include &iostream&
void StrInsSort (int number
for(int i=1;i&=i++)
temp=r[i];int j=i-1;
while(temp&r[j])
r[j+1]=r[j];
int _tmain(int argc, int argv[])
std::cout&&"输入数组大小"&&
std::cin&&
std::cout&&"输入数组内数据"&&
for(int j=0;j&j++)
std::cin&&argv[j];
StrInsSort (argc ,argv);
for(int j=0;j&j++)
std::cout && argv[j] && std::
system("pause");
次待排序数组是从0开始的，先假定第0个元素是有序的，从第一个元素起与前边的有序序列进行比较，T先和下标为i-1的数组比较，（生成的整个序列是从小到达排列的）如果
r[i]&r[i-1],则直接放在r[i]的位置，否则如果T&r[i-1],则将将i--，直到找到一个比T小的，把T放在该数的后边；
折半插入排序
&&& 折半插入与直接插入比较，当第i 个记录要插入到前i-1个记录序列时，可以利用折半查找方式确定插入位置，以减少比较次数。
&&&&折半查找明显减少了关键字的&比较&次数，单记录的移动次数不变，故时间复杂度仍为O(n^2)。
void BinSort (int count, int R[])
for (int i=1;i&=i++)
int left=0;
int right=i-1;
while (right&=left)
temp=R[i] ;
int mid =(left+right)/2;
if (temp&R[mid])
left=mid+1;
right=mid-1;
for (int j=i-1;j&=right+1;j--)
R[j+1]=R[j];
R[right+1]=
函数写过程中，首先确定有多少个元素要参加排序，由于次数组是从下表0开始的，所以和直接插入排序一样，先假设第0个元素是有序的，则从下标为1的元素开始执行循环，即从1到count个元素都要执行对比循环过程；其循环内部基本思路是，把取到的第i个元素插入到前0到i-1个元素中，因为前i个元素是有序的，所以二分查找是拿第i元素和和前面有序数列中的第mid =(left+right)/2个元素比较，即有序数列中中间的那个元素，因为排序后要生成一个从小到大排序的数列，即升序数列，所以如果temp&R[mid]如下图所示，
&则要是插入&temp后整个数列依然有序，则temp必须在6的后面，所以要最左侧的数为left=mid+1;才能保证在后半部分寻找数据；
然后就要判断循环什么时候终止，因为在整个循环过程中不断缩小循环的范围，即left和right的距离越来越近，当left==right时，这时mid==left==righ,&这时，
如果&&&&&&
&&if (temp&R[mid]) &&&{ &&&&left=mid+1; &&&}&&&&&
如上图所示，mid在6的位置，此时的temp是&6而&7&的，应该把&=left的或&=mid+1的或&=right+1的元素向后移一位；
else &&&{ &&&&right=mid-1; &&&}
如上图所示，mid应该&6且&4，即放在4和6之间，这样更应该把&=left的后&=mid的或&=right+1的元素向后移一位；
&&for (int j=i-1;j&=right+1;j--) &&{ &&&R[j+1]=R[j]; &&}&&&&&&&&&& 即对应这段程序；
&经过上边分析，同样也可以写成下面程序，即把&=right+1,改成&=
&for (int j=i-1;j&=j--) &&{ &&&R[j+1]=R[j]; &&} &&R[left]=
二路插入排序
&&& 基本思想是另设一数组d，将R[1]复制给d[1]，并将d[1]看做排好序的&中间&记录，从第二个起依次将关键字小于d[1]的记录插入到d[1]之前的有序序列中，将关键字大于d[1]的记录插入到d[1]之后的有序序列中。这里借助两个变量first和final来指示排序过程中有序序列第一个记录和最后一个记录在d中的位置。
int BiInsertSort()
//二路插入排序算法
int iRawBuff[6] ={0,9,6,7,3,2};
int final = 0;
int first = 0;
const int iLenght = 5;
int iTempBuff[iLenght] = {0};
iTempBuff[0] = iRawBuff[0];
for (int i = 1; i &= iLi++)
if(iRawBuff[i] & iTempBuff[final])
//大于当前最大值，后插
iTempBuff[final] = iRawBuff[i];
if(iRawBuff[i]& iTempBuff[first])
//小于当前最小值,前插
first = (first-1+iLenght)%iL
iTempBuff[first] = iRawBuff[i];
if(iRawBuff[i] & iTempBuff[final]&&iRawBuff[i] & iTempBuff[first])
//大于当前最小值，小于当前最大值，中间插
int j = final++;
while (iRawBuff[i] & iTempBuff[j])
iTempBuff[(j+1)%iLenght] = iTempBuff[j];
j = (j-1+iLenght)%iL
iTempBuff[j+1] = iRawBuff[i];
printf("第%d趟：\n",i-1);
for(int k = 0; k & iL k++)
std::cout&&iTempBuff[k]&&"\t";
std::cout&&std::
//导入输入到原始数组中
for (int k = 0; k & iL k++)
iRawBuff[k+1] = iTempBuff[(first++)%iLenght];
&&&&运行结果：
&&&&&&&&&&&
&由于first在增加增加的过程中，没有最大值的限制，为了防止生成的数组发生越界，所以对这些数取iLenght的余数，即用%iLenght。
表插入排序
&&&&为了减少在排序过程中&移动&记录的操作，必须改变排序过程中采用的存储结构。利用静态链表进行排序，并在排序之后，一次性地调整各个记录之间的位置，即将每个记录都调整到他们应该在的位置上，这样的排序方法称为表插入排序。
基本思想：
使头结点的next域始终指示最小的那个元素，然后依次向下：每一个元素的next域都指示比它稍大的那个元素。最大的元素的next域指示头结点。
下面分三步给出具体的代码：
1、用数组初始化表结构。
2、修改next域形成有序的循环链表。
3、根据next域信息调整表结构中的数组，是数据从小到大排列。
#include "stdafx.h"
#define INT_MAX 100
#define number 100
#include&iostream&
#include&time.h&
#include&stdlib.h&
#include&iomanip&
#include&math.h&
//排序后按从小到大输出
typedef struct
//记录其他数据域
STListType SL[number+1];
void ListInsSort(STListType SL[],int n)
//对记录序列SL[1..n]进行表插入排序
SL[0].key = 10000;
SL[0].next=1;
SL[1].next=0;
//初始化，假定第一个记录有序
for (int i=2; i& i++)
//查找插入位置
for (k=SL[0].SL[k].key&SL[i].)
//保证[k].key&=[i].key
j=k, k=SL[k].
//保证是SL[k]里的总是最大的
SL[j].next=i;
//结点i插入在结点j和结点k之间
SL[j]&=SL[i]&=SL[k]
SL[i].next =k;
cout&&"ListInsSort-key:\n";
for(int count=0;count&n;count++)
cout&&setw(4)&&SL[count].
cout&&"ListInsSort-next:\n";
for(int count=0;count&n;count++)
cout&&setw(4)&&SL[count].
void Arrange(STListType SL[],int n)
//根据静态表SL中各节点的指针值调整记录位置，使得SL中的记录关键字非递减有序顺序排列
//p指示第i个记录的当前位置；i指示第i个记录应在的位置；q指示第i+1个记录的当前位置；
int p=SL[0].
//p指示第一个记录的当前位置
for (int i=1;i&n;i++)
//SL[1..i-1]中的记录关键字有序排列，第i个记录在SL中的当前位置应不小于i
//为了保证&i 的元素都是有序的
while(p&i)
//找到第i个记录，并用p指示其在SL中的当前位置
//q指示尚未调整的表尾
temp = SL[p];
SL[p] = SL[i];
//交换记录，使第i个记录到位
SL[i].next=p;
//指向被移走的记录，使得以后可以由while循环找到
//p指示尚未调整的表尾，为找第i+1个记录作准比
cout&&"Arrange-key:\n";
for(int count=0;count&n;count++)
cout&&setw(4)&&SL[count].
cout&&"Arrange-next:\n";
for(int count=0;count&n;count++)
cout&&setw(4)&&SL[count].
int _tmain()
STListType SL[100];
cout&&"ListInsSort.cpp运行结果:\n";
int b[100],i;
srand(time(0));
cout&&"输入待排序元素个数n:";cin&&n;
for(i=1;i&n;i++)
b[i]=rand()%100;
SL[i].key=b[i];
cout&&"排序前数组:\n";
for(i=1;i&n;i++)
cout&&setw(4)&&b[i];
ListInsSort(SL,n);
Arrange(SL,n);
cout&&"排序后数组:\n";
for(i=1;i&n;i++)
cout&&setw(4)&&SL[i].
system("pause");
希尔插入排序
&&& 希尔排序又称缩小增量排序，（适用于待排序数列很无序的情况下）；基本思想是将待排序的记录划分成几组，从而减少参与直接插入排序的数据量，经过几次分组排序后，记录的排序已经基本有序，在对所有的记录实施最后的直接插入排序。
&&&&&对于希尔排序，具体步骤可以描述如下：假设待排序的记录为n个，先取整数d&n,例如d=n/2,将所有距离为d的记录构成一组，从而将整个待排序记录分割成为d个子序列（d组），对每个分组进行直接插入排序，然后再缩小间隔d，例如，取d=d/2，重复上述分组，再对每个分组分别进行直接插入排序，直到最后取d=1,即将所有的记录放在一组进行一次直接插入排序，最终将所有记录重新排列成按关键字有序的序列。
Shell提出的选法：d1=n/2 , di+1=di/2
#include&iostream&
#include&iomanip&
#include&stdlib.h&
#include&time.h&
#define MAXI 11
typedef int KeyT
typedef int ElemT
struct rec
typedef rec sqlist[MAXI];
void shellsort(sqlist b,int n)
int i,j,gap,k;
while(gap&0)
for(i=gap+1;i&n;i++)
while(j&0)
if(b[j].key&b[j+gap].key)
b[j]=b[j+gap];
b[j+gap]=x;
for(k=1;k&n;k++)
cout&&setw(4)&&b[k].
gap=gap/2;
void main()
{cout&&"运行结果:\n";
int i,n=MAXI;
srand(time(0));
for(i=1;i&n;i++)
{a[i].key=rand()%80;
a[i].data=rand()%100;}
cout&&"排序前数组:\n";
for(i=1;i&n;i++)
cout&&setw(4)&&a[i].
cout&&"数组排序过程演示:\n";
shellsort(a,n);
cout&&"排序后数组:\n";
for(i=1;i&n;i++)
cout&&setw(4)&&a[i].
cout&&cin.get();}
1.2 交换排序
&&&&& 交换排序：通过&交换&无序序列中的相邻记录从而得到其中关键字最小或最大的记录，并将他们加入到有序序列中，以增加记录的有序序列长度。
&&&&& 主要思想是在排序过程中，通过比较待排序记录序列中元素的关键字，如果发现次序相反，则将存储位置交换来达到排序目的。
&&&& 它的基本思想是对所有相邻记录的关键字值进行比较，如果是逆序(a[j]&a[j+1]),则将其交换，最终达到有序。
#include "stdafx.h"
#include "stdafx.h"
#include &iostream&
int bubbleSort (int number
for (int i =0;i&=number-1;i++)
for (int j=0;j&=number-i-1;j++)
if (r[j]&r[j+1])
temp=r[j];
r[j]=r[j+1];
int _tmain(int argc, int argv[])
std::cout&&"输入数组大小"&&
std::cin&&
std::cout&&"输入数组内数据"&&
for(int j=0;j&j++)
std::cin&&argv[j];
bubbleSort (argc ,argv);
for(int j=0;j&j++)
std::cout && argv[j] && std::
system("pause");
在排序过程中，比较相邻的元素，如果第前个比后一个大，就交换他们两个。对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。针对所有的元素重复以上的步骤，除了最后一个。
for (int i =0;i&=number-1;i++)循环是指（一个元素向上冒泡，直到它找到合适的位置）这个过程的次数，即有多少个元素要进行冒泡操作；冒到上边的是最大的；
for (int j=0;j&=number-i-1;j++)循环是指进行冒泡操作的每一个元素，要经过做少次对比，才能找到合适的位置；
&&&& 快速排序的基本思想：首先将待排序记录序列中的所有记录作为当前待排序区域，从中任选一个记录（通常可选取第一个记录），以它的关键字作为枢纽，凡其关键字小于枢纽的记录均移到该记录之前，反之，凡关键字大于枢纽的记录均移至该纪录之后，这样一趟排序之后，记录的无序序列R[s..t]将分割成两部分：R[s..i-1]和R[i+1..t]，且R[j].key&=R[i].key&=R[k].key
#include "stdafx.h"
#include "stdafx.h"
#define number 100
#include&iostream&
#include&time.h&
#include&stdlib.h&
#include&iomanip&
#include&math.h&
//排序后按从小到大输出
typedef struct
//记录其他数据域
RecType S[number+1];
int Partirion(RecType R[],int l,int h)
//交换记录子序列R[1..h]中的记录，使枢纽记录交换到正确的位置，并返回其所在的位置
//用变量i,j记录待排序记录的首尾位置
R[0]=R[i];
//以子表的第一个记录作为枢轴，将其暂存到记录R[0]中
int x=R[i].
//用变量x存放枢纽记录的关键字
while (i&j)
//从表的两端交替地向中间扫描
while (i&j&&R[j].key&=x)
R[i]=R[j];
//将比枢纽小的记录移到低端
while (i&j&&R[i].key&=x)
R[j]=R[i];
//将比枢纽大的记录移到高端
R[i]=R[0];
//枢纽记录到位
//返回枢纽位置
void QuickSort(RecType R[],int s,int t)
//对记录序列R[s..t]进行快速排序
k=Partirion(R,s,t);
QuickSort(R,s,k-1);
QuickSort(R,k+1,t);
cout&&"QuickSort:\n";
for(i=2;i&=t;i++)
cout&&setw(4)&&R[i].
int _tmain()
RecType SL[100];
cout&&"QuickSort.cpp运行结果:\n";
int b[100],i;
srand(time(0));
cout&&"输入待排序元素个数n:";cin&&n;
for(i=1;i&n;i++)
b[i]=rand()%100;
SL[i].key=b[i];
cout&&"排序前数组:\n";
for(i=1;i&n;i++)
cout&&setw(4)&&b[i];
QuickSort(SL,1,n);
cout&&"排序后数组:\n";
for(i=2;i&=n;i++)
cout&&setw(4)&&SL[i].
system("pause");
运行结果：
1.3 选择排序
&&&& &选择排序：从记录的无序序列中&选择&关键字最小或最大的记录，并将他加入到有序子序列中，以增加记录的有序序列的长度。
&&&&& 基本思想是依次从待排序记录中选择出关键字值最小（或最大）的记录、关键字值次之的记录、...并分别将它们定位到序列左侧（或右侧）的第1位置、第2位置、...，从而使待排序的记录序列成为按关键字值由小到大（或有大到小）排列的有序序列。
直接选择排序
&&&& 有序序列中所有记录的关键字均小于无序序列中记录的关键字，则第i趟直接选择排序是从无序序列R[i..n]的n-i+1个记录中选择关键字最小的记录加入有序序列的末尾。
#include "stdafx.h"
#define number 100
#include&iostream&
#include&time.h&
#include&stdlib.h&
#include&iomanip&
#include&math.h&
//排序后按从小到大输出
typedef struct
//记录其他数据域
RecType S[number+1];
void SelectSort(RecType R[],int n)
//对记录序列R[1..n]进行直接选择排序
for (int i=1;i&n;i++)
for (int j=i+1;j&=n;j++)
if (R[k].key&R[j].key)
temp=R[i];
R[i]=R[k];
int _tmain()
RecType SL[100];
cout&&"SelectSort.cpp运行结果:\n";
int b[100],i;
srand(time(0));
cout&&"输入待排序元素个数n:";
for(i=1;i&n;i++)
b[i]=rand()%100;
SL[i].key=b[i];
cout&&"排序前数组:\n";
for(i=1;i&n;i++)cout&&setw(4)&&b[i];
cout&&SelectSort(SL,n);
cout&&"排序后数组:\n";
for(i=2;i&=n;i++)
cout&&setw(4)&&SL[i].
system("pause");
树形选择排序
&&&& 基本思想：首先是对n个待排序记录的关键字进行两两比较，从中选出[n/2]个较小者再两两比较，直到选出关键字最小的记录为止，此为一趟排序。
#include "stdafx.h"
//锦标赛排序法
#include&iostream&
#include&iomanip&
#include&math.h&
#include&stdlib.h&
#include&time.h&
class DataNode //胜者树结点的类定义
//树中的结点号
//参选标志
//锦标赛排序中的调整算法;i是表中当前
//最小元素的下标,即胜者.从它开始向上调整
void UpdataTree(DataNode *tree,int i)
if(i%2==0) //i为偶数,对手为左结点
tree[(i-1)/2]=tree[i-1];//i为奇数,对手为右结点
tree[(i-1)/2]=tree[i+1];
i=(i-1)/2; //i上升到双亲结点位置
{if(i%2==0) j=i-1;//确定i的对手为左结点还是右结点
else j=i+1;
if(!tree[i].active||!tree[j].active)//比赛对手中间有一个空
if(tree[i].active) tree[(i-1)/2]=tree[i];
else tree[(i-1)/2]=tree[j]; //非空者上升到双亲结点
//比赛对手都不为空
if(tree[i].data&tree[j].data) tree[(i-1)/2]=tree[i];
else tree[(i-1)/2]=tree[j];//胜者上升到双亲结点
i=(i-1)/2; //i上升到双亲结点
//建立树的顺序存储数组tree,将数组a[]中的元素复制到胜者树中,
//对它们进行排序,并把结果返回数组中,n是待排序元素个数
void TournmentSort(int a[],int n)
{DataNode * //胜者树结点数组
int m,i,j=0;
for(int k=0;k&n;k++)//计算满足&=n的2的最小次幂的数
m=(int)pow((double) 2,(double)k);
int bottomRowSize=m;
int TreeSize=2*bottomRowSize-1;//计算胜者树的大小:内结点+外结点数
int loadindex=bottomRowSize-1;//外结点开始位置
tree=new DataNode[TreeSize];
//动态分配胜者树结点数组空间
for(i=i&TreeSi++)//复制数组数据到树的外结点中
{tree[i].index=i;//下标
if(j&n) {tree[i].active=1;tree[i].data=a[j++];}//复制数据
else tree[i].active=0; //后面的结点为空的外结点
//进行初始比较寻找最小的项
while(j&2*i)
//处理各对比赛者
{if(!tree[j+1].active||tree[j].data&tree[j+1].data)
tree[(j-1)/2]=tree[j];
else tree[(j-1)/2]=tree[j+1];//胜者送入双亲
j+=2; //下一对参加比较的项
i=(i-1)/2;//i退到双亲,直到i=0为止
for(i=0;i&n-1;i++)//处理其他n-1个元素
{a[i]=tree[0].//当前最小元素送数组a
tree[tree[0].index].active=0;//该元素相应外结点不再比赛
UpdataTree(tree,tree[0].index);//从该处向上修改
a[n-1]=tree[0].
//锦标赛排序法的测试
void main()
{cout&&"JinBiaoSai.cpp运行结果:\n";
int n,b[100],i;
srand(time(0));
cout&&"输入待排序元素个数n:";cin&&n;
for(i=0;i&n;i++) b[i]=rand()%100;
cout&&"排序前数组:\n";
for(i=0;i&n;i++)
cout&&setw(4)&&b[i];
TournmentSort(b,n);
cout&&"排序后数组:\n";
for(i=0;i&n;i++)
cout&&setw(4)&&b[i];
cin.get();cin.get();
树形选择排序：
#include "stdafx.h"
#include&iostream&
#include&string.h&
#include&ctype.h&
#include&malloc.h&
#include&limits.h&
#include&stdio.h&
#include&stdlib.h&
#include&io.h&
#include&math.h&
#define MAX_SIZE 20
typedef int KeyT
typedef int InfoT //定义其他数据类型
struct RedType{ KeyT InfoT };
struct SqList
RedType r[MAX_SIZE];
void print(SqList L)
for(i=1;i&=L.i++)
cout&&"("&&L.r[i].key&&","&&L.r[i].otherinfo&&")";
void TreeSort(SqList &L)
int i,j,j1,k,k1,l;
float n=L.
RedType *t;
l=(int)ceil(log(n)/log(2.0))+1; //完全二叉树的层数;ceil取上整，返回比x大的最小整数
k=(int)pow(2.0,l)-1; //k为l层完全二叉树的结点总数
k1=(int)pow(2.0,l-1)-1; //k1为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;
//给非叶子结点赋值
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;
cout&&"给非叶子结点赋值:"&&
//循环一次，找到最小的
for(i=0;i&n;i++)
L.r[i+1]=t[0]; //键当前最小值赋给L.r[i]
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;
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]);
cout&&"循环排序:"&&
#define N 8
void main()
RedType d[N]={{49,1},{38,2},{65,3},{97,4},{76,5},{13,6},{27,7},{49,8}};
for(i=0;i&N;i++)
l.r[i+1]=d[i];
l.length=N;
cout&&"排序前："&&
TreeSort(l);
cout&&"排序后："&&
system("pause");
排序过程中t[k1+i-1]=L.r[i];把L里的数据存储t[k1+i-1]中，为排序需要
k=(int)pow(2.0,l)-1; //k为l层完全二叉树的结点总数
t=(RedType*)malloc(k*sizeof(RedType)); //二叉树采用顺序存储
的存储空间；
运行结果：
&&&& 其左右子树分别是堆，任何一个结点的值不大(或不小于)左右孩子节点，则最顶端元素必是序列中的最大值或最小值，分别称为小顶堆或大顶堆（小堆或大堆）。堆排序是利用堆的特性对记录序列进行排序的一种排序算法。其基本思想是：先建一个堆，即先选一个关键字最大或最小的记录，然后与序列中的最后一个记录交换，之后将序列中前n-1个记录重新调整为一个堆(调堆的过程称为&筛选&)，再将堆顶记录和第n-1个记录交换，如此反复至排序结束。注意：第i 次筛选的前提是从2到n-i 是一个堆，即筛选是对一棵左/右子树均为堆的完全二叉树&调整&根节点使整棵二叉树为堆的过程。
#include "stdafx.h"
#include &iostream&
void sift(int R[],int i,int m) //R[]要排序的数组;i是指是从堆的第几行的首元素 即i=1 2 4 8 16...;m是指数组中一共多少个元素
//设R[i+1..m]中各元素满足堆的定义,本算法调整R[i]使序列R[i..m]中的元素满足堆的性质
int temp = R [i];
for (int j=2*i;j&=m;j*=2)
//在堆的同一层进行比较，如果右边的大于左边的，则继续向右查找 ，为了保证下面和temp比较的R[j],是这一层上最大的一个
if ((j&m)&&(R[j]&R[j+1]))
if (temp&R[j]) //temp和每一层最大的数比较，如果小于最大的，则把最大的的值赋给R[i]
R[i]=R[j];
//修改i的值，此时R[i]=R[j]的值相同
//最初要调整的节点放在正确的位置
HeapSort( int R[],int n)
int nCreateTime=1;
for (i=n/2;i&0;i--)
sift(R,i,n);
//建堆时i从n/2起递减，是指i从从最底层起依次循环向顶层排序
std::cout&&"建堆"&&nCreateTime&&
for(int j=1;j&9;j++)
std::cout && R[j];
nCreateTime++;
std::cout&&
int nAdjustTime=1;
for (i=n;i&1;i--)
temp=R[i];
R[i]=R[1];
sift(R,1,i-1);
std::cout&&"重新调整"&&nAdjustTime&&
for(int j=1;j&9;j++)
std::cout && R[j];
nAdjustTime++;
std::cout&&
int _tmain(int argc, _TCHAR* argv[])
int data[9]={0,6,9,3,1,5,8,9};
std::cout&&"初始序列"&&
for(int j=1;j&9;j++)
std::cout && data[j];
std::cout&&
HeapSort( data,8);
std::cout&&"生成的有序序列"&&
for(int j=1;j&9;j++)
std::cout && data[j];
std::cout&&
system("pause");
运行结果：
1.4 归并排序
&&&& &归并排序：通过&归并&两个或两个以上的有序序类，逐步增加有序序列的长度。
归并排序 2-路归并排序
&&&& 其基本思想是：将一个具有n个待排序记录的序列看成是n个长度为1的有序序列，然后进行两两归并，得到n/2个长度为2的有序序列，在进行两两归并，得到n/4个长度为4的有序序列，如此重复，直至得到一个长度为n的有序序列为止。
#include "stdafx.h"
#define number 100
#include&iostream&
#include&time.h&
#include&stdlib.h&
#include&iomanip&
#include&math.h&
//排序后按从小到大输出
typedef struct
//记录其他数据域
RecType S[number+1];
void Merge(RecType R[],RecType R1[],int i,int l,int h)
//将有序的R[i..l]和R[l+1..h]归并为有序的R1[i..h]
for (j=l+1,k=i;i&=l && j&=h;k++)
//将R[]中记录由小到大地并入R1
if (R[i].key&=R[j].key)
R1[k]=R[i++];
R1[k]=R[j++];
R1[k++]=R[i++];
R1[k++]=R[j++];
//将剩余的R[j..h]复制到R1
void Msort(RecType R[],RecType R1[],int s,int t)
//将R[s..t]2-路归并排序为R1[s..t]
RecType R2[100];
R1[s]=R[s];
int m=(s+t)/2;
//将R[s..t]平分为R[s..m]和R[m+1..t]
Msort(R,R2,s,m);
//递归的将R[s..m]归并为有序的R2[s..m]
Msort(R,R2,m+1,t);
//递归的将R[m+1..t]归并为有序的R2[m+1..t]
Merge(R2,R1,s,m,t);
//将R2[s..m]和R2[m+1..t]归并到R1[s..t]
int _tmain()
cout&&"MergingSort.cpp运行结果:\n";
int b[100],i;
RecType R1[100];
srand(time(0));
cout&&"输入待排序元素个数n:";cin&&n;
RecType SL[100];
for(i=1;i&=n;i++)
b[i]=rand()%100;
SL[i].key=b[i];
cout&&"排序前数组:\n";
for(i=1;i&=n;i++)
cout&&setw(4)&&b[i];
Msort(SL,R1,1,n);
cout&&"排序后数组:\n";
for(i=1;i&=n;i++)
cout&&setw(4)&&R1[i].
system("pause");
1.5 分配排序
&&&&& 前面讨论的排序算法都是基于关键字之间的比较，通过比较判断出大小，然后进行调整。而分配排序则不然，它是利用关键字的结构，通过&分配&和&收集&的办法来实现排序。
&&&&& 分配排序：通过对无序序列中的记录进行反复的&分配&和&收集&操作，逐步是无序序列变为有序序列。
分配排序分为：桶排序和基数排序两类。
计数排序的过程类似小学选班干部的过程,如某某人10票,作者9票,那某某人是班长,作者是副班长
大体分两部分,第一部分是拉选票和投票,第二部分是根据你的票数入桶
看下具体的过程,一共需要三个数组,分别是待排数组,票箱数组,和桶数组
var unsorted = new int[] { 6, 2, 4, 1, 5, 9 };& //待排数组
var ballot = new int[unsorted.Length];&&&&&&&&& //票箱数组
var bucket = new int[unsorted.Length];&&&&&&&&& //桶数组
最后再看桶数组,先看待排数组和票箱数组
初始状态,迭代变量i = 0时,待排数组[i] = 6,票箱数组[i] = 0,这样通过迭代变量建立了数字与其桶号(即票数)的联系
待排数组[ 6 2 4 1 5 9 ] i = 0时,可以从待排数组中取出6
票箱数组[ 0 0 0 0 0 0 ] 同时可以从票箱数组里取出6的票数0,即桶号
拉选票的过程
首先6出列开始拉选票,6的票箱是0号,6对其它所有数字说,谁比我小或与我相等,就给我投票,不然揍你
于是,2 4 1 5 分别给6投票,放入0号票箱,6得四票
待排数组[ 6 2 4 1 5 9 ]
票箱数组[ 4 0 0 0 0 0 ]
接下来2开始拉选票,对其它人说,谁比我小,谁投我票,不然弄你!于是1投了一票,其他人比2大不搭理,心想你可真二
于是2从1那得到一票
待排数组[ 6 2 4 1 5 9 ]
票箱数组[ 4 1 0 0 0 0 ]
4得到2和1的投票,共计两票
1得到0票,没人投他
5得到2,4,1投的三张票
9是最大,得到所有人(自己除外)的投票,共计5票(数组长度-1票)
投票完毕时的状态是这样
待排数组[ 6 2 4 1 5 9 ]
票箱数组[ 4 1 2 0 3 5 ]
入桶的过程
投票过程结束,每人都拥有自己的票数,桶数组说,看好你自己的票数,进入与你票数相等的桶,GO
6共计5票,进入5号桶
2得1票,进入1号桶,有几票就进几号桶
4两票,进2号桶,5三票进3号桶,9有5票,进5号桶
待排数组[ 6 2 4 1 5 9 ]
票箱数组[ 4 1 2 0 3 5 ]
-----------------------
入桶前 [ 0 1 2 3 4 5 ] //里边的数字表示桶编号
入桶后 [ 1 2 4 5 6 9 ] //1有0票,进的0号桶
排序完毕,顺序输出即可[ 1 2 4 5 6 9]
可以看到,数字越大票数越多,9得到除自己外的所有人的票,5票,票数最多所以9最大,
每个人最多拥有[数组长度减去自己]张票
1票数最少,所以1是最小的
#include "stdafx.h"
#include &iostream&
#include &cstdio&
#include &cstdlib&
#include &cmath&
#include &cstring&
#include &stdlib.h&
#include&time.h&
#include&iomanip&
#include&math.h&
void CountingSort(int *A,int *B,int *Order,int N,int K)
int *C=new int[K+1];
memset(C,0,sizeof(int)*(K+1));
for (i=1;i&=N;i++) //把A中的每个元素分配
C[A[i]]++;
for (i=2;i&=K;i++) //统计不大于i的元素的个数
C[i]+=C[i-1];
for (i=N;i&=1;i--)
B[C[A[i]]]=A[i]; //按照统计的位置，将值输出到B中，将顺序输出到Order中
Order[C[A[i]]]=i;
C[A[i]]--;
int main()
int *A,*B,*Order,N=15,K=10,i;
A=new int[N+1];
B=new int[N+1];
Order=new int[N+1];
for (i=1;i&=N;i++) A[i]=rand()%K+1; //生成1..K的随机数
cout&&"Before CS:\n";
for (i=1;i&=N;i++)
cout&&setw(4)&&A[i];
CountingSort(A,B,Order,N,K);
printf("\nAfter CS:\n");
for (i=1;i&=N;i++)
cout&&setw(4)&&B[i];
cout&&"\nOrder:\n";
for (i=1;i&=N;i++)
cout&&setw(4)&&Order[i];
system("pause");
运行结果：
&&&& 桶排序（Bucket Sort）也称箱排序（Bin Sort）,其基本思想是：设置若干个桶，依次扫描待排序记录R[1..n],把关键字等于k的记录全部都装到第k个桶里（分配），按序号依次将各非空的桶首尾连接起来（收集）。桶的个数取决于关键字的取值范围。
桶排序 (Bucket sort)或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶子里。 基本思路： 1.设置一个定量的数组当作空桶子。 2.寻访串行，并且把项目一个一个放到对应的桶子去。 3.对每个不是空的桶子进行排序。 4.从不是空的桶子里把项目再放回原来的串行中。
无序数组有个要求,就是成员隶属于固定(有限的)的区间,如范围为[0-9](考试分数为1-100等)
例如待排数字[6 2 4 1 5 9]
准备10个空桶,最大数个空桶
[6 2 4 1 5 9]&&&&&&&&&& 待排数组
[0 0 0 0 0 0 0 0 0 0]&& 空桶
[0 1 2 3 4 5 6 7 8 9]&& 桶编号(实际不存在)
1,顺序从待排数组中取出数字,首先6被取出,然后把6入6号桶,这个过程类似这样:空桶[ 待排数组[ 0 ] ] = 待排数组[ 0 ]
[6 2 4 1 5 9]&&&&&&&&&& 待排数组
[0 0 0 0 0 0 6 0 0 0]&& 空桶
[0 1 2 3 4 5 6 7 8 9]&& 桶编号(实际不存在)
2,顺序从待排数组中取出下一个数字,此时2被取出,将其放入2号桶,是几就放几号桶
[6 2 4 1 5 9]&&&&&&&&&& 待排数组
[0 0 2 0 0 0 6 0 0 0]&& 空桶
[0 1 2 3 4 5 6 7 8 9]&& 桶编号(实际不存在)
3,4,5,6省略,过程一样,全部入桶后变成下边这样
[6 2 4 1 5 9]&&&&&&&&&& 待排数组
[0 1 2 0 4 5 6 0 0 9]&& 空桶
[0 1 2 3 4 5 6 7 8 9]&& 桶编号(实际不存在)
0表示空桶,跳过,顺序取出即可:1 2 4 5 6 9
/* 桶排序实现 */
#include "stdafx.h"
#include &iostream&
#include &cstdio&
#include &cstdlib&
#include &cmath&
#include &cstring&
#include &stdlib.h&
#include&time.h&
#include&iomanip&
#include&math.h&
void BucketSort(int *A,int *B,int N,int K)
int *C=new int[K+1];
int i,j,k;
memset(C,0,sizeof(int)*(K+1));
for (i=1;i&=N;i++) //把A中的每个元素按照值放入桶中
C[A[i]]++;
for (i=j=1;i&=K;i++,j=k) //统计每个桶元素的个数，并输出到B
for (k=j;k&j+C[i];k++)
int main()
int *A,*B,N=100,K=100,i;
A=new int[N+1];
B=new int[N+1];
cout&&"排序前："&&
for (i=1;i&=N;i++)
A[i]=rand()%K+1; //生成1..K的随机数
cout&&setw(4)&&A[i];
BucketSort(A,B,N,K);
cout&&"排序后："&&
for (i=1;i&=N;i++)
cout&&setw(4)&&B[i];
system("pause");
运行结果：
这种特殊实现的方式时间复杂度为O(N+K)，空间复杂度也为O(N+K)，同样要求每个元素都要在K的范围内。更一般的，如果我们的K很大，无法直接开出O(K)的空间该如何呢？ & 首先定义桶，桶为一个数据容器，每个桶存储一个区间内的数。依然有一个待排序的整数序列A，元素的最小值不小于0，最大值不超过K。假设我们有M个桶，第i个桶Bucket[i]存储iK/M至(i+1)K/M之间的数，有如下桶排序的一般方法： &1.扫描序列A，根据每个元素的值所属的区间，放入指定的桶中(顺序放置)。 &2.对每个桶中的元素进行排序，什么排序算法都可以，例如快速排序。 &3.依次收集每个桶中的元素，顺序放置到输出序列中。 & 对该算法简单分析，如果数据是期望平均分布的，则每个桶中的元素平均个数为N/M。如果对每个桶中的元素排序使用的算法是快速排序，每次排序的时间复杂度为O(N/Mlog(N/M))。则总的时间复杂度为O(N)+O(M)O(N/Mlog(N/M)) = O(N+ Nlog(N/M)) = O(N + NlogN - NlogM)。当M接近于N是，桶排序的时间复杂度就可以近似认为是O(N)的。就是桶越多，时间效率就越高，而桶越多，空间却就越大，由此可见时间和空间是一个矛盾的两个方面。
/*桶排序实现 */
#include "stdafx.h"
#include &iostream&
#include &cstdio&
#include &cstdlib&
#include &cmath&
#include &cstring&
#include &stdlib.h&
#include&time.h&
#include&iomanip&
#include&math.h&
struct linklist
linklist *
linklist(int v,linklist *n):value(v),next(n){}
~linklist() {if (next)}
inline int cmp(const void *a,const void *b)
return *(int *)a-*(int *)b;
/* 为了方便，我把A中元素加入桶中时是倒序放入的，而收集取出时也是倒序放入序列的，所以不违背稳定排序。 */
void BucketSort(int *A,int *B,int N,int K)
linklist *Bucket[101],*p;
int i,j,k,M; M=K/100;
memset(Bucket,0,sizeof(Bucket));
for (i=1;i&=N;i++)
//把A中的每个元素按照的范围值放入对应桶中
Bucket[k]=new linklist(A[i],Bucket[k]);
for (k=j=0;k&=100;k++)
for (p=Bucket[k];p;p=p-&next)
B[++j]=p-&
//把桶中每个元素取出，排序并加入B
delete Bucket[k];
qsort(B+i+1,j-i,sizeof(B[0]),cmp);
int main()
int *A,*B,N=100,K=100,i;
A=new int[N+1];
B=new int[N+1];
for (i=1;i&=N;i++)
A[i]=rand()%K+1; //生成1..K的随机数
cout&&setw(4)&&A[i];
BucketSort(A,B,N,K);
cout&&"排序后："&&
for (i=1;i&=N;i++)
cout&&setw(4)&&B[i];
system("pause");
运行结果：
&&&& 基数排序（Radix Sort）是对桶排序的改进和推广。
&&&& 基本思想：将一个关键字分解成多个&关键字&，再利用多关键字排序的思想对记录序列进行排序。基数排序就是借助&多关键字排序&的思想来实现&单关键字排序&的算法。
&&&& 假设有n个记录的待排序序列{R1,R2,...,Rn},每个记录Ri中含有d个关键字，则称上述记录序列对关键字有序，是指对于序列中的任意两个记录Ri和Rj（1&=i&j&=n）都满足下列（词典）有序关系；
具体做法为：
&&&& （1）待排序的记录以指针相链，构成一个链表。
&&&&&（2）&分配&时，按当前&关键字位&的取值，将记录分配到不同的&链队列&中，每个队列中记录的&关键字位&相同。
&&&&&（3）&收集&时，按当前关键字取值从小到大将各队首尾相链接成一个链表；对每个关键字位均重复2）和3）两步。如下所示：
p-&369-&367-&167-&239-&237-&138-&230-&139
第一次分配得到：
B[0].f-&230&-B[0].e
B[7].f-&367-&167-&237&-B[7].e
B[8].f-&138&-B[8].e
B[9].f-&369-&239-&139&-B[9].e
第一次收集得到：
p-&230-&367-&167-&237-&138-&369-&239-&139
第二次分配得到：
B[3].f-&230-&237-&138-&239-&139&-B[3].e
B[6].f-&367-&167-&369&-B[6].e
第二次收集得到：
p-&230-&237-&138-&239-&139-&367-&167-&369
第三次分配得到：
B[1].f-&138-&139-&167&-B[1].e
B[2].f-&230-&237-&239&=B[2].e
B[3].f-&367-&369&-B[3].e
第三次收集之后便得到记录的有序序列：
p-&138-&139-&167-&230-&237-&239-&367-&369
#include "stdafx.h"
#include &iostream&
#include&stdlib.h&
#include&iomanip&
#include&math.h&
int maxbit(int data[],int n) //辅助函数，求数据的最大位数
int d = 1; //保存最大的位数
int p =10;
for(int i = 0;i & ++i)
while(data[i] &= p)
void radixsort(int data[],int n) //基数排序
int d = maxbit(data,n);
int * tmp = new int[n];
int * count = new int[10]; //计数器
int i,j,k;
int radix = 1;
for(i = 1; i&=i++) //进行d次排序
for(j = 0;j & 10;j++)
count[j] = 0; //每次分配前清空计数器
for(j = 0;j & 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 &j++) //将临时数组的内容复制到data中
data[j] = tmp[j];
radix = radix*10;
int _tmain(int argc, _TCHAR* argv[])
int data[10]={267,6,9,679,0,999,99,9,22,11};
std::cout&&"初始序列"&&
for(int j=0;j&10;j++)
std::cout &&setw(4)&& data[j];
std::cout&&
radixsort( data,10);
std::cout&&"生成的有序序列"&&
for(int j=0;j&10;j++)
std::cout && setw(4)&&data[j];
std::cout&&
system("pause");
system("pause");
&运行结果：
各种排序算法比较
大部分已排序时较好
B是真数(0-9)，
R是基数(个十百)
O(ns) 1&s&2
s是所选分组
2 外部排序
外部排序：若参加排序的记录数量很大，整个排序过程不能一次在内存中完成，则称此类排序问题为外部排序；
&&&&& 以上博客，如有参考使用，请标明出处；
&《算法与数据结构》 第二版&& 陈守孔 著
参考的网上内容：
阅读(...) 评论()