常用的数据排序算法有哪些,各有什么特点?举例结合一种排序算法并应用数组进行数据排序。

求解！！求具体程序，应用选择法排序算法对数组排序，并输出排序后的结果，已知数据a的数据为15，45~

void select_sort(int array[], int length){int i, j;for(i = 0; i < length-1; i++) {int min = i;for(j = i+1; j < length; j++)if( array[j] < array[min] ) // find minmin = j; if(min != i) // swap array[i] and array[min]{ int tmp = array[i];array[i] = array[min];array[min] = tmp;}}}完整测试程序：
#include void select_sort(int array[], int length){int i, j;for(i = 0; i < length-1; i++) {int min = i;for(j = i+1; j < length; j++)if( array[j] < array[min] ) min = j;if(min != i){int tmp = array[i];array[i] = array[min];array[min] = tmp;}}}int ia[] = { 15, 45, 25, 60, 20, 84, 75, 90, 100, 68 };const int len = sizeof(ia)/sizeof(ia[0]);int main(int argc, char *argv[]){int i;puts("before sort:");for(i = 0; i < len; i++)printf("%d ", ia[i]);select_sort(ia, len);puts("
after sort:");for(i = 0; i < len; i++)printf("%d ", ia[i]);return 0;}

第一章 数据结构基本概念
1、基本概念：理解什么是数据、数据对象、数据元素、数据结构、数据的逻辑结构与物理结构、逻辑结构与物理结构间的关系。
2、面向对象概念：理解什么是数据类型、抽象数据类型、数据抽象和信息隐蔽原则。了解什么是面向对象。由于目前关于这个问题有许多说法，我们采用了一种最流行的说法，即Coad与Yourdon 给出的定义：面向对象 = 对象 + 类 + 继承 + 通信。
要点：
·抽象数据类型的封装性
·面向对象系统结构的稳定性
·面向对象方法着眼点在于应用问题所涉及的对象
3、数据结构的抽象层次：理解用对象类表示的各种数据结构
4、算法与算法分析：理解算法的定义、算法的特性、算法的时间代价、算法的空间代价。
要点：·算法与程序的不同之处需要从算法的特性来解释
·算法的正确性是最主要的要求
·算法的可读性是必须考虑的
·程序的程序步数的计算与算法的事前估计
·程序的时间代价是指算法的渐进时间复杂性度量

第二章 数组
1、作为抽象数据类型的数组：数组的定义、数组的按行顺序存储与按列顺序存储
要点：
·数组元素的存放地址计算
2、顺序表：顺序表的定义、搜索、插入与删除
要点：
·顺序表搜索算法、平均比较次数的计算
·插入与删除算法、平均移动次数的计算
3、多项式：多项式的定义
4、字符串：字符串的定义及其操作的实现
要点：
·串重载操作的定义与实现

第三章 链接表
1、单链表：单链表定义、相应操作的实现、单链表的游标类。
要点：
·单链表的两种定义方式（复合方式与嵌套方式）
·单链表的搜索算法与插入、删除算法
·单链表的递归与迭代算法
2、循环链表：单链表与循环链表的异同
3、双向链表：双向链表的搜索、插入与删除算法、链表带表头结点的优点
4、多项式的链接表示

第四章 栈与队列
1、栈：栈的特性、栈的基本运算
要点：
·栈的数组实现、栈的链表实现
·栈满及栈空条件、抽象数据类型中的先决条件与后置条件
2、栈的应用：用后缀表示计算表达式，中缀表示改后缀表示
3、队列：队列的特性、队列的基本运算
要点：
·队列的数组实现：循环队列中队头与队尾指针的表示，队满及队空条件
·队列的链表实现：链式队列中的队头与队尾指针的表示、
4、双向队列：双向队列的插入与删除算法
5、优先级队列：优先级队列的插入与删除算法

第五章 递归与广义表
1、递归：递归的定义、递归的数据结构、递归问题用递归过程求解
要点：·链表是递归的数据结构，可用递归过程求解有关链表的问题
2、递归实现时栈的应用
要点：·递归的分层（树形）表示：递归树
·递归深度（递归树的深度）与递归工作栈的关系
·单向递归与尾递归的迭代实现
3、广义表：广义表定义、广义表长度、广义表深度、广义表表头、广义表表尾
要点：
·用图形表示广义表的存储结构
·广义表的递归算法

第六章 树与森林
1、树：树的定义、树的基本运算
要点：
·树的分层定义是递归的
·树中结点个数与高度的关系
2、二叉树：二叉树定义、二叉树的基本运算
要点：
·二叉树性质、二叉树中结点个数与高度的关系、不同种类的二叉树棵数
·完全二叉树的顺序存储、完全二叉树的双亲、子女和兄弟的位置
·二叉树的前序·中序·后序·层次遍历
·前序
·中序
·后序的线索化二叉树、前驱与后继的查找方法
3、霍夫曼树：霍夫曼树的构造方法、霍夫曼编码、带权路径长度的计算
4、树的存储：树的广义表表示、树的双亲表示、树与二叉树的对应关系、树的先根·中根·后根·层次遍历。
5、堆：堆的定义、堆的插入与删除算法
要点：
·形成堆时用到的向下调整算法及形成堆时比较次数的上界估计
·堆插入时用到的向上调整算法

第七章 集合与搜索
1、集合的概念：集合的基本运算、集合的存储表示
要点：
·用位数组表示集合时集合基本运算的实现
·用有序链表表示集合时集合基本运算的实现
2、并查集：并查集定义、并查集的三种基本运算的实现
3、基本搜索方法
要点：
·对一般表的顺序搜索算法（包括有监视哨和没有监视哨）
·对有序顺序表的顺序搜索算法、用判定树（即扩充二叉搜索树）描述搜索，以及平均搜索长度（成功与不成功）的计算。
·对有序顺序表的折半搜索算法、用判定树（即扩充二叉搜索树）描述搜索，以及平均搜索长度（成功与不成功）的计算。
4、二叉搜索树：
要点：
·动态搜索树与静态搜索树的特性
·二叉搜索树的定义、二叉搜索树上的搜索算法、二叉搜索树搜索时的平均搜索长度（成功与不成功）的计算。
·AVL树结点上的平衡因子、AVL树的平衡旋转方法
·高度为h的AVL树上的最少结点个数与最多结点个数
· AVL树的搜索方法、插入与删除方法

第八章 图
1、图：图的定义与图的存储表示
要点：
·邻接矩阵表示（通常是稀疏矩阵）
·邻接表与逆邻接表表示
·邻接多重表(十字链表)表示
2、深度优先遍历与广度优先遍历
要点：
·生成树与生成树林的定义
·深度优先搜索是个递归的过程，而广度优先搜索是个非递归的过程
·为防止重复访问已经访问过的顶点，需要设置一个访问标志数组visited
3、图的连通性
要点：
·深度优先搜索可以遍历一个连通分量上的所有顶点
·对非连通图进行遍历，可以建立一个生成森林
·对强连通图进行遍历，可能建立一个生成森林
·关节点的计算和以最少的边构成重连通图
4、最小生成树
要点：
·对于连通网络、可用不会构成环路的权值最小的n-1条边构成最小生成树
·会画出用Kruskal算法及Prim算法构造最小生成树的过程
5、单源最短路径
要点：
·采用逐步求解的方式求某一顶点到其他顶点的最短路径
·要求每条边的权值必须大于零
6、活动网络
要点：
·拓扑排序、关键路径、关键活动、AOE网
·拓扑排序将一个偏序图转化为一个全序图。
·为实现拓扑排序，要建立一个栈，将所有入度为零的顶点进栈
·关键路径的计算

第九章 排序
1、基本概念：关键码、初始关键码排列、关键码比较次数、数据移动次数、稳定性、附加存储、内部排序、外部排序
2、插入排序：
要点：
·当待排序的关键码序列已经基本有序时，用直接插入排序最快
3、选择排序：
要点：
·用直接选择排序在一个待排序区间中选出最小的数据时，与区间第一个数据对调，而不是顺次后移。这导致方法不稳定。
·当在n个数据（n很大）中选出最小的5 ~ 8个数据时，锦标赛排序最快
·锦标赛排序的算法中将待排序的数据个数n补足到2的k次幂2k-1<n≤2k
·在堆排序中将待排序的数据组织成完全二叉树的顺序存储。
4、交换排序：
要点：
·快速排序是一个递归的排序方法
·当待排序关键码序列已经基本有序时，快速排序显著变慢。
5、二路归并排序：
要点：
·归并排序可以递归执行
·归并排序需要较多的附加存储。可以采用一种"推拉法"（参见教科书上习题）实现归并排序，算法的时间复杂度为O (n)、空间复杂度为O(1)
·归并排序对待排序关键码的初始排列不敏感，排序速度较稳定
6、外排序
要点：
·多路平衡归并排序的过程、I/O缓冲区个数的配置
·外排序的时间分析、利用败者树进行多路平衡归并
·利用置换选择方法生成不等长的初始归并段
·最佳归并树的构造及WPL的计算

第十章 索引与散列
1、线性索引：
要点：
·密集索引、稀疏索引、索引表计算
·基于属性查找建立倒排索引、单元式倒排表
2、动态搜索树
要点：
·平衡的m路搜索树的定义、搜索算法
·B树的定义、B树与平衡的m路搜索树的关系
·B树的插入（包括结点分裂）、删除（包括结点调整与合并）方法
·B树中结点个数与高度的关系
·B+树的定义、搜索、插入与删除的方法
3、散列表
要点：
·散列函数的比较
·装填因子 a 与平均搜索长度的关系，平均搜索长度与表长m及表中已有数据对象个数n的关系
·解决地址冲突的（闭散列）线性探查法的运用，平均探查次数的计算
·线性探查法的删除问题、散列表类的设计中必须为各地址设置三个状态
·线性探查法中的聚集问题
·解决地址冲突的（闭散列）双散列法的运用，平均探查次数的计算
·双散列法中再散列函数的设计要求与表长m互质，为此m设计为质数较宜
·解决地址冲突的（闭散列）二次散列法的运用，平均探查次数的计算
·注意：二次散列法中装填因子 a 与表长m的设置
·解决地址冲突的（开散列）链地址法的运用，平均探查次数的计算

排序简介
排序是数据处理中经常使用的一种重要运算,在计算机及其应用系统中,花费在排序上的时间在系统运行时间中占有很大比重;并且排序本身对推动算法分析的发展也起很大作用。目前已有上百种排序方法，但尚未有一个最理想的尽如人意的方法，本章介绍常用的如下排序方法，并对它们进行分析和比较。

1、插入排序（直接插入排序、折半插入排序、希尔排序）；
2、交换排序（起泡排序、快速排序）；
3、选择排序（直接选择排序、堆排序）；
4、归并排序；
5、基数排序；

学习重点
1、掌握排序的基本概念和各种排序方法的特点，并能加以灵活应用；
2、掌握插入排序(直接插入排序、折半插入排序、希尔排序)、交换排序（起泡排序、快速排序）、选择排序（直接选择排序、堆排序）、二路归并排序的方法及其性能分析方法；
3、了解基数排序方法及其性能分析方法。

排序（sort）或分类

　所谓排序，就是要整理文件中的记录，使之按关键字递增(或递减)次序排列起来。其确切定义如下：
　　输入：n个记录R1，R2，…，Rn，其相应的关键字分别为K1，K2，…，Kn。
　　输出：Ril，Ri2，…，Rin，使得Ki1≤Ki2≤…≤Kin。(或Ki1≥Ki2≥…≥Kin)。

1．被排序对象--文件
　　被排序的对象--文件由一组记录组成。
　　记录则由若干个数据项(或域)组成。其中有一项可用来标识一个记录，称为关键字项。该数据项的值称为关键字(Key)。
注意：
　 在不易产生混淆时，将关键字项简称为关键字。

2．排序运算的依据--关键字
　用来作排序运算依据的关键字，可以是数字类型，也可以是字符类型。
　 关键字的选取应根据问题的要求而定。
【例】在高考成绩统计中将每个考生作为一个记录。每条记录包含准考证号、姓名、各科的分数和总分数等项内容。若要惟一地标识一个考生的记录，则必须用"准考证号"作为关键字。若要按照考生的总分数排名次，则需用"总分数"作为关键字。

排序的稳定性

　 当待排序记录的关键字均不相同时，排序结果是惟一的，否则排序结果不唯一。
　在待排序的文件中，若存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，该排序方法是稳定的；若具有相同关键字的记录之间的相对次序发生变化，则称这种排序方法是不稳定的。
注意：
　 排序算法的稳定性是针对所有输入实例而言的。即在所有可能的输入实例中，只要有一个实例使得算法不满足稳定性要求，则该排序算法就是不稳定的。

排序方法的分类

1．按是否涉及数据的内、外存交换分
　在排序过程中，若整个文件都是放在内存中处理，排序时不涉及数据的内、外存交换，则称之为内部排序(简称内排序)；反之，若排序过程中要进行数据的内、外存交换，则称之为外部排序。
注意：
　 ① 内排序适用于记录个数不很多的小文件
　② 外排序则适用于记录个数太多，不能一次将其全部记录放人内存的大文件。

2．按策略划分内部排序方法
　可以分为五类：插入排序、选择排序、交换排序、归并排序和分配排序。

排序算法分析

1．排序算法的基本操作
　大多数排序算法都有两个基本的操作：
　　(1) 比较两个关键字的大小；
　　(2) 改变指向记录的指针或移动记录本身。
注意：
　 第(2)种基本操作的实现依赖于待排序记录的存储方式。

2．待排文件的常用存储方式
（1） 以顺序表(或直接用向量)作为存储结构
排序过程：对记录本身进行物理重排（即通过关键字之间的比较判定，将记录移到合适的位置）

（2） 以链表作为存储结构
　　排序过程：无须移动记录，仅需修改指针。通常将这类排序称为链表(或链式)排序；

（3） 用顺序的方式存储待排序的记录，但同时建立一个辅助表(如包括关键字和指向记录位置的指针组成的索引表)
　　排序过程：只需对辅助表的表目进行物理重排（即只移动辅助表的表目，而不移动记录本身）。适用于难于在链表上实现，仍需避免排序过程中移动记录的排序方法。

3．排序算法性能评价
（1） 评价排序算法好坏的标准
　　评价排序算法好坏的标准主要有两条：
　① 执行时间和所需的辅助空间
　② 算法本身的复杂程度

（2） 排序算法的空间复杂度
　　若排序算法所需的辅助空间并不依赖于问题的规模n，即辅助空间是O(1)，则称之为就地排序(In-PlaceSou)。
　　非就地排序一般要求的辅助空间为O(n)。

（3） 排序算法的时间开销
　　大多数排序算法的时间开销主要是关键字之间的比较和记录的移动。有的排序算法其执行时间不仅依赖于问题的规模，还取决于输入实例中数据的状态。

文件的顺序存储结构表示

#define n l00 //假设的文件长度，即待排序的记录数目
typedef int KeyType； //假设的关键字类型
typedef struct{ //记录类型
KeyType key； //关键字项
InfoType otherinfo；//其它数据项，类型InfoType依赖于具体应用而定义
}RecType；
typedef RecType SeqList[n+1]；//SeqList为顺序表类型，表中第0个单元一般用作哨兵
注意：
　若关键字类型没有比较算符，则可事先定义宏或函数来表示比较运算。
【例】关键字为字符串时，可定义宏"#define LT(a，b)(Stromp((a)，(b))<0)"。那么算法中"a<b"可用"LT(a，b)"取代。若使用C++，则定义重载的算符"<"更为方便。

按平均时间将排序分为四类：

（1）平方阶(O(n2))排序
　一般称为简单排序，例如直接插入、直接选择和冒泡排序；

（2）线性对数阶(O(nlgn))排序
　如快速、堆和归并排序；

（3）O(n1+￡)阶排序
　￡是介于0和1之间的常数，即0<￡<1，如希尔排序；

（4）线性阶(O(n))排序
　如桶、箱和基数排序。

各种排序方法比较

简单排序中直接插入最好，快速排序最快，当文件为正序时，直接插入和冒泡均最佳。

影响排序效果的因素

　因为不同的排序方法适应不同的应用环境和要求，所以选择合适的排序方法应综合考虑下列因素：
　　①待排序的记录数目n；
　　②记录的大小(规模)；
　　③关键字的结构及其初始状态；
　　④对稳定性的要求；
　　⑤语言工具的条件；
　　⑥存储结构；
　　⑦时间和辅助空间复杂度等。

不同条件下，排序方法的选择

(1)若n较小(如n≤50)，可采用直接插入或直接选择排序。
　当记录规模较小时，直接插入排序较好；否则因为直接选择移动的记录数少于直接插人，应选直接选择排序为宜。
(2)若文件初始状态基本有序(指正序)，则应选用直接插人、冒泡或随机的快速排序为宜；
(3)若n较大，则应采用时间复杂度为O(nlgn)的排序方法：快速排序、堆排序或归并排序。
　快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；
　堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。
　若要求排序稳定，则可选用归并排序。但本章介绍的从单个记录起进行两两归并的 排序算法并不值得提倡，通常可以将它和直接插入排序结合在一起使用。先利用直接插入排序求得较长的有序子文件，然后再两两归并之。因为直接插入排序是稳定的，所以改进后的归并排序仍是稳定的。

4)在基于比较的排序方法中，每次比较两个关键字的大小之后，仅仅出现两种可能的转移，因此可以用一棵二叉树来描述比较判定过程。
　当文件的n个关键字随机分布时，任何借助于"比较"的排序算法，至少需要O(nlgn)的时间。
　箱排序和基数排序只需一步就会引起m种可能的转移，即把一个记录装入m个箱子之一，因此在一般情况下，箱排序和基数排序可能在O(n)时间内完成对n个记录的排序。但是，箱排序和基数排序只适用于像字符串和整数这类有明显结构特征的关键字，而当关键字的取值范围属于某个无穷集合(例如实数型关键字)时，无法使用箱排序和基数排序，这时只有借助于"比较"的方法来排序。
　若n很大，记录的关键字位数较少且可以分解时，采用基数排序较好。虽然桶排序对关键字的结构无要求，但它也只有在关键字是随机分布时才能使平均时间达到线性阶，否则为平方阶。同时要注意，箱、桶、基数这三种分配排序均假定了关键字若为数字时，则其值均是非负的，否则将其映射到箱(桶)号时，又要增加相应的时间。
(5)有的语言(如Fortran，Cobol或Basic等)没有提供指针及递归，导致实现归并、快速(它们用递归实现较简单)和基数(使用了指针)等排序算法变得复杂。此时可考虑用其它排序。
(6)本章给出的排序算法，输人数据均是存储在一个向量中。当记录的规模较大时，为避免耗费大量的时间去移动记录，可以用链表作为存储结构。譬如插入排序、归并排序、基数排序都易于在链表上实现，使之减少记录的移动次数。但有的排序方法，如快速排序和堆排序，在链表上却难于实现，在这种情况下，可以提取关键字建立索引表，然后对索引表进行排序。然而更为简单的方法是：引人一个整型向量t作为辅助表，排序前令t[i]=i(0≤i<n)，若排序算法中要求交换R[i]和R[j]，则只需交换t[i]和t[j]即可；排序结束后，向量t就指示了记录之间的顺序关系：
R[t[0]].key≤R[t[1]].key≤…≤R[t[n-1]].key
若要求最终结果是：
R[0].key≤R[1].key≤…≤R[n-1].key
则可以在排序结束后，再按辅助表所规定的次序重排各记录，完成这种重排的时间是O(n)。

找本算法设计的书看看就行了

---

宁远县19798392491： 几种常见的排序算法 - ？
罗骅泰白： for(i = 0; i < n; i++) for(j = 0; j < n - 1 - i; j++){if(arr[j] arr[j + 1]){arr[j] = arr[j] ^ arr[j+1]; arr[j+1] = arr[j] ^ arr[j+1]; arr[j] = arr[j] ^ arr[j+1];}}} 交换两个数据,可以用用临时变量,也可用以下的两个方法a = a^b;b = a^b;a = a^b;或者 a = a + b;b = a - b;a = a - ...

宁远县19798392491： 常见排序算法有哪些 - ？
罗骅泰白： 常用的排序算法有:冒泡排序、选择排序、堆排序、SHELL排序、快速排序、归并排序、磁盘排序等等.但是每种排序算法都是各有优缺点.如果需要进一步研究各种算法的性能的话,那么就必须学习计算机算法和复杂性这门课程.

宁远县19798392491： 数据结构中排序方法有多少种 - ？
罗骅泰白： 1、插入排序(直接插入排序和希尔排序) 2、选择排序(直接选择排序和堆排序) 3、交换排序(冒泡排序和快速排序) 4、归并排序 5、基数排序 直接插入排序:逐个将后一个数加到前面的排好的序中.在直接插入排序过程中,对其中一个记...

宁远县19798392491： 数据结构排序算法有哪些常用的 - ？
罗骅泰白： 最常用的是快速排序,基数排序,计数排序,归并排序,堆排序,(偶尔还有插入排序) 都有各自的应用,快排就是单纯的快,但是特殊数据下复杂度会退化 基数排序可以配合一些特定的算法,譬如后缀数组的构建 计数排序简单且常用,通常排序值域小但是数据量大的情况 归并直接用来排序并不多,但是可以用来求解一些其他问题,本身的思想也非常重要,有很多拓展的算法(不是排序算法) 堆排序胜在稳定,不论数据如何最坏都是O(nlogn),一般情况比快速排序慢些,但是极端情况下表现十分优秀,常用来配合快速排序,优化其稳定性 插入排序适合极少量数据的排序(几个到十几个),速度要比这些高级算法快一些

宁远县19798392491： 常见的排序方法有哪些 - ？
罗骅泰白： 常见的有冒泡排序,选择排序(这两个复杂度是一样的,都是O(n^2)),希尔排序是目前效率最高的(复杂度为O(nlgn)),另外还有插入排序(希尔排序就是在此基础上改进的),快速排序,归并排序,基数排序等

宁远县19798392491： 常见排序算法有哪些呢? ？
罗骅泰白： 排序常见排序算法快速排序、希尔排序、堆排序、直接选择排序不是稳定的排序算法,而基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的排序算法排序分类◆稳定排序:假设在待排序的文件中,存在两个或两个以上的记录具有相同的关键字,在用某种排序法排序后,若这些相同关键字的元素的相对次序仍然不变,则这种排序方法是稳定的

宁远县19798392491： 数据结构中几种常见的排序算法之比较 - ？
罗骅泰白： 实话实说,关于数据结构中几种常见的排序算法(例如:冒泡排序、SHELL排序、归并排序、快速排序等)的性能好坏,还不只是学好了数据结构这门课程就能够解决的问题,还必须要学习好、且精通掌握计算机软件专业的另外一门非常重要的课程,才能够解决这个问题.即:计算机算法复杂性理论.只有同时把这门课程学好了,那么才能够真正掌握数据结构中的各种排序算法、以及各种查找算法中所有涉及到的:比较次数、以及交换次数,最终才能够根据具体的开发软件规模的不同,选择出一个适合开发该软件的最佳算法.

宁远县19798392491： 常见的排序算法有什么呢? ？
罗骅泰白： 这是我的回答,希望对你有帮助. 常用的排序算法有:冒泡法、选择法、插入法、快速排序法、堆排序法、归并排序法等

宁远县19798392491： 数据结构的排序方法有哪些? - ？
罗骅泰白： 冒泡排序,快速排序,堆排序.冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法.它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来.走访数列的工作是重复地进行直到没有再需要...

宁远县19798392491： 数据结构中常见的排序方式都有哪些?比如冒泡排序,快速排序等.每种排序具体是怎么排的? - ？
罗骅泰白： 1.直接插入:就是有一个已经排好的子序列,它是有序的.然后来一个插入一个仍是这个序列有序.比如a1本身就是有序的.a2来了,要和a1比较,a2大就插在a1之后,小就在a1之前,那么a1、a2就是新的有序子序列,然后a3来了,又要插入...