快速排序算法非递归法c语言

⑴ 北航计算机类研究生专业考试科目

你需要到人家的网站看招生简章、招生专业目录、参考书目录三个文件，都在招生信息里，或者在招生就业里！网站在网络输入学校名就有了. 或者直接某大学2008研究生招生专业目录，参考08年的，09年的每年7月后出！对应相应编号找 ，总之你只要会电脑，就在他的网站找到招生专业目录及参考书！一定要去他的网站
http://yzb.buaa.e.cn/
院系名称:计算机学院
专业名称:计算机科学与技术
专业拟招收人数：220人
研究方向名称:计算机系统结构 计算机应用技术 计算机软件与理论
专业备注:基本学习年限为2.5年

考试科目单元 考试科目代码 考试科目名称
第一门考试科目 101 政治
第二门考试科目 201 英语
第三门考试科目 301 数学一
第四门考试科目 961 计算机专业综合
其中数学英语政治全国都一样，是统考！到考研书店问问就知道了！
专业课参考书：961 计算机专业综合
《数据结构教程》（第二版，第三次印刷〕
北航出版社
唐发根着

《计算机组成原理》
高等教育出版社
唐朔飞编着

《操作系统实用教程》
清华大学出版社
任爱华主编

《离散数学》（数理逻辑部分〕
高等教育出版社
尹宝林等编

大纲：961计算机专业综合考试大纲（2008版）

一、考试组成
961计算机专业综合共包括四门课程的内容：计算机组成原理、数据结构、操作系统、数理逻辑，分别占40分、40分、40分、30分。

二、计算机组成原理部分的考试大纲
(一) 参考书
《计算机组成原理》，高等教育出版社，唐朔飞编着
(二) 复习内容
1．存储系统
（1）主存储器：存储单元电路及其工作原理、存储芯片结构及其工作原理、DRAM的刷新原理和刷新方式、存储器的扩展方法。
（2）高速缓冲存储器：Cache的基本结构和工作原理、Cache的地址映射方式、Cache的替换策略。
（3）辅助存储器：磁盘存储器的结构、访问特征和性能参数计算。
2．指令系统
（1）指令格式：机器指令的一般格式以及指令字中各字段的作用和特点。
（2）寻址方式：常见寻址方式的有效地址计算方法、寻址范围、作用和特点。
（3）指令系统的设计：指令格式设计的相关因素及基本方法、扩展操作码技术。
3．CPU
（1）CPU的功能和结构: CPU的基本功能、内部结构、数据通路、控制信号。
（2）控制单元的功能：指令周期、多级时序系统、控制方式、指令执行过程的微操作流程分析。
（3）控制单元的设计：微程序控制器的结构和工作原理、微指令的格式和编码方式、微程序设计。
4．输入输出技术
（1）总线：总线的分类、总线的判优（仲裁）控制方式、总线的通信控制方式。
（2）I/O控制方式：中断响应与中断处理、DMA方式的工作原理。

三、操作系统部分的考试大纲
（一）指定参考书
《操作系统实用教程（第二版）》，任爱华，清华大学出版社。
（二）复习内容
1．进程
进程、进程同步和通信、进程调度和死锁等基本概念和相关算法。要求清楚理解进程，线程等基本概念，熟练掌握各种基本算法。
2．存储管理
存储器管理，包括重定位和虚拟存储器等基本概念，分区、分页、分段以及段页式存 储管理。要求清楚理解基本概念，熟练掌握各种分配算法。
3．设备管理
I/O设备管理、调度、分配机制, RAID 等。要求掌握I/O管理的基本概念。
4．文件系统
文件系统，包括文件的组织方式、目录结构、存取控制等。要求清楚理解文件系统的基本概念。

四、数据结构部分的考试大纲
（一）、指定参考书
《数据结构教程（第二版）》 唐发根编着 北京航空航天大学出版社，（建议选用第3次印刷的书）
（二）、复习内容
1．线性表
（1）线性关系，线性表的定义，线性表的基本操作；
（2）线性表的顺序存储结构与链式存储结构(单链表、循环链表和双向链表)的构造原理；
（3）在以上两种存储结构的基础上对线性表实施的基本操作对应的算法设计。
2．堆栈与队列
（1）堆栈与队列的基本概念，基本操作；
（2）堆栈与队列的顺序存储结构与链式存储结构的构造原理；
（3）在以上两种储结构的基础上对堆栈与队列实施插入与删除等基本操作的算法设计。
3．二叉树
（1）二叉树的基本概念与基本名词术语；
（2）完全二叉树与满二叉树，二叉树的基本性质；
（3）二叉树的顺序存储结构与二叉链表存储结构的基本构造原理，二叉树的前序遍历、中序遍历、后序遍历以及对应算法的设计(非递归算法)；
（4）二叉排序树的基本概念，二叉排序树的建立(插入)和查找。
4．图
（1）图的定义，基本名词术语；
（2）图的邻接矩阵存储方法、邻接表存储方法的基本构造原理；
（3）图的深度优先遍历与广度优先遍历；
（4）最小生成树与最短路径的基本概念和构造过程。
5．文件及查找
（1）顺序查找法与折半查找法，折半查找法对应的“判定树”的构造；
（2）B-树的基本概念，B-树的插入与查找；
（3）散列(Hash)表的构造、散列函数、散列冲突以及处理散列冲突的方法。
6．内排序
（1）插入排序法(含折半插入排序法)、选择排序法、泡排序法、快速排序法、(大顶)堆积排序法；
（2）各种内排序方法排序的基本原理和特点。

五、数理逻辑部分的考试大纲
（一）参考书
《离散数学》（第一篇 数理逻辑），高等教育出版社，尹宝林等编着
（二）复习内容
1. 命题逻辑
命题逻辑的基本概念及方法：联结词、赋值、等值演算、对偶定理、联结词的完全集、范式、逻辑推论。
2. 谓词逻辑
谓词逻辑的基本概念及方法：谓词和量词、项和公式、解释和赋值、永真式、等值演算、逻辑推论。
3. 公理系统
公理系统：命题逻辑及谓词逻辑的公理系统、可靠性和完全性。
4. 归结法原理
归结法原理：前束范式、斯科伦范式、命题逻辑及谓词逻辑的归结法。

还一个：
院系名称:软件学院
专业名称:软件工程
专业拟招收人数：80人
研究方向名称:集成电路设计 日文应用软件开发 嵌入式软件
专业备注:基本学习年限2.5年,培养费共4万元人民币,本专业只招收"自筹经费"和"委托培养"两种类别

第一门考试科目 101 政治
第二门考试科目 201 英语
或 203 日语
第三门考试科目 301 数学一
第四门考试科目 991 数据结构与C语言程序设计
专业课参考书：991 数据结构与C语言程序设计
《数据结构教程第二版》
北京航空航天大学出版社
唐发根着

《C程序设计》
清华大学出版社
谭浩强着

大纲：991数据结构与C语言程序设计考试大纲(2008版)

一、考试组成
数据结构与C语言程序设计包括“数据结构”与“C语言程序设计”两门课程的内容，各占75分，总分150分。

二、数据结构部分的考试大纲
（一）指定参考书
《数据结构教程（第二版）》 唐发根编着， 北京航空航天大学出版社
（建议选择2006年6月第3次印刷的书）
（二）复习内容及基本要求
1、概述
（1）数据的逻辑结构与存储结构的基本概念；
（2）算法的定义、基本性质以及算法分析的基本概念，包括采用大形式表示时间或空间复杂度。
2、线性表
（1）线性关系、线性表的定义，线性表的基本操作；
（2）线性表的顺序存储结构与链式存储结构(包括单链表、循环链表和双向链表)的构造原理；
(3)在以上两种存储结构的基础上对线性表实施的基本操作，包括顺序表的插入和删除、链表的建立、插入和删除、检索等操作对应的算法设计(含递归算法的设计)。
3、堆栈与队列
(1)堆栈与队列(含循环队列)的基本概念、基本操作；
(2)堆栈与队列的顺序存储结构与链式存储结构的构造原理；
(3)在不同存储结构的基础上对堆栈与队列实施插入与删除等基本操作。
4、树与二叉树
(1)树与二叉树的基本概念，基本特征、名词术语；
(2)完全二叉树、满二叉树的概念、二叉树的基本性质；
(3)二叉树的顺序存储结构与二叉链表存储结构的构造原理、二叉树的前序遍历、中序遍历、后序遍历和按层次遍历算法(重点为非递归算法)以及利用遍历解决有关二叉树的其它操作；
(4)线索二叉树的基本概念以及构造原理；
(5)二叉排序树的基本概念、建立(插入)和查找，在二叉排序树中查找结点的平均查找长度ASL。
5、图
(1)图的基本概念、名词术语；
(2)邻接矩阵存储方法和邻接表存储方法的基本构造原理与特点；
(3)图的深度优先搜索和广度优先搜索的过程，图的遍历的基本作用；
(4)最小生成树及最短路径的特点、求解过程，拓扑排序及其目的。
6、文件及查找
(1)顺序查找法、折半查找法以及查找过程对应的“判定树”的构造；
(2)索引文件的基本概念；
(3)B-树与B+树的构造以及构造上异同，B-树的插入和查找；
(4)散列文件的特点，散列函数和散列冲突的概念，处理散列冲突的方法以及散列文件的查找。
7、内排序
插入排序、选择排序、泡排序、快速排序、堆积排序(大顶堆积)和二路归并排序法等排序方法的排序原理、规律和特点。

三、C语言程序设计部分的考试大纲
（一）指定参考书
《C程序设计》 谭浩强编着，清华大学出版社
（二）复习内容及基本要求
1、C语言基本知识
（1）C语言的特点以及C语言程序的组成；
（2）数据类型，包括整型、实型、字符型等常量与变量和变量的赋值；用typedef定义类型；
（3）各种类型数据之间的混合运算；
（4）各类运算符的运算规则和优先级；条件运算符；
（5）算术表达式、关系表达式和逻辑表达式，逗号运算符和逗号表达式，表达式sizeof的含义。
2、语句
（1）赋值语句(含条件赋值语句)、条件语句(含if、if-else、switch)、循环语句(含while、do-while、for语句，包括循环嵌套和break语句)；
（2）输入/输出语句，包括整型、实型、字符型(含字符串)等类型数据的格式输入函数scanf和格式输出函数printf。
3、数组
（1）一维数组与二维数组的定义，数组元素的引用，数组的初始化；
（2）字符数组的定义，字符数组的初始化，字符数组的引用，字符数组的输入与输出，字符串和字符串处理函数。
4、函数
（1）函数的定义，函数参数(形参和实参)与函数的返回值；
（2）函数的调用，包括函数的嵌套调用和递归函数的递归调用；
（3）命令行参数的概念（带参数的主函数）。
5、宏定义
（1）带参数的宏定义；
（2）包含文件的处理。
6、指针
（1）指针的概念，变量的指针与指向变量的指针变量，包括定义、引用以及指针变量作为函数参数；
（2）数组的指针，包括指向数组的指针变量的定义与赋值、通过指针引用数组元素、数组名作为函数参数；
（3）字符串的指针与指向字符串的指针变量。
7、结构体
（1）结构体的基本概念和特点，结构体的初始化与引用；
（2）结构体数组。
8、文件
（1）文本文件的基本概念，文本文件的类型指针FILE以及文本文件的使用方式；
（2）文本文件的打开(fopen函数)、文本文件的关闭(fclose函数)；
（3）文本文件的状态，包括feof函数和ferror函数；
（4）文本文件的读写，包括fputc函数和fgetc函数、fgets函数和fputs函数等；
（5）文本文件的输入函数fscanf和输出函数fprintf。

复式：北京航空航天大学计算机学院
2008年硕士研究生复试规定与安排

北航计算机学院硕士研究生招生复试工作基本安排如下：
一、 统考生源复试安排（仅适合统考生源）
1. 复试分数线：计算机科学与技术（081200）和地图制图学与地理信息工程（081603）两个专业的复试分数线均为：总分350分，政治和外语单科50分，数学和专业单科80分。另外，计算机学院2008年继续在统考生源中招收部分软件工程硕士（双证），有关软件工程硕士的分数线和复试办法参见《北京航空航天大学计算机学院2008年软件工程硕士复试规定与安排》。
2. 复试办法：复试采取差额复试的办法，复试分为C语言上机考试和综合面试两部分，每部分各150分，复试总成绩300分，没有笔试。每部分成绩及格（90分以上（含）），方具有录取资格。
 C语言上机考试只测试考生的C语言编程能力，直接在计算机上进行，系统环境为Microsoft Visual Studio 6.0，建议使用标准C编程。
 综合面试内容包括英语口语、听力、数理基础和专业综合素质等方面的内容。专业综合素质方面将涉及计算机基础与专业知识，考生在相关领域内曾经进行的开发、研究工作，考生本科的专业背景、曾获得的各种荣誉，参加的各种科技、社会活动等。复试注重实际能力和可培养潜力。
3. 资格审查：所有参加复试的考生须按本规定附件1的要求准备好复试资格审查材料，复试报到时提交以便学院进行资格审查。
4. 复试报到：3月23日上午8:30，参加复试的考生到新主楼G849报到，递交复试资格审查材料，进行考生复试资格审核（复试资格审核办法见附件1），同时领取导师情况简介和导师志愿表。
5. C上机考试：3月23日下午2:00，参加复试的考生到计算机学院教学实验中心参加C语言上机测试，测试时间2小时。
6. 地图制图学与地理信息工程专业综合面试：3月24日上午8:30报考地图制图学与地理信息工程专业的学生统一参加导师组面试。面试结束后公布复试结果。
7. 计算机科学与技术专业综合面试流程
 参加计算机科学与技术专业复试的考生根据导师介绍、导师招生人数等情况填报两个导师志愿，3月24日中午12:00前将志愿表返回G849（过时无故不交，视为自动放弃复试）。3月24日下午6:00公布第一批面试分组名单。
 第一批面试（3月25日上午8:30）的考生是第一志愿填报教授导师的考生，第一志愿填报副教授导师的考生不参加第一批面试。每个导师的面试人数一般不超过招生人数的150％，排名在150％以后的考生，如第一志愿服从调剂，学院将根据具体情况将考生调剂到报名人数不足150％的教授所在的面试小组参加面试。3月25日下午5:30左右公布第一批拟录取名单和3月26日上午（第二批）面试分组名单。
 第二批面试3月26日上午8:30进行，第一志愿填报副教授的考生按其第一志愿和第一志愿填报教授导师但没被录取的考生的第二志愿一起排队参加面试。每个导师的面试人数一般不超过招生人数的150％。排名在150％以后的考生，学院将根据具体情况进行调剂，以确保每人至少有一次面试机会。
 两轮面试仍然没有录取满的导师，学院将从剩余考生中根据考生统考成绩和考生是否服从分配等因素调剂录取。
 3月26日下午5:30左右公布全部拟录取名单。最终录取与否，以收到研究生院发出的正式录取通知书为准。
 3月26日下午5:30左右，所有被拟录取的考生到学院办公室领取政审表，录取类别为自筹的考生领取并签署自筹协议，录取类别为委托培养的考生领取定向委托培养协议。
8. 同等学历加试：按同等学力身份参加复试的考生（国家承认学历的成人应届本科毕业生或获得国家承认的大专毕业证书后连续工作两年或两年以上的）需要单独加试《C语言程序设计》和《编译原理》课程（《C语言程序设计》用上机考试成绩代替），《编译原理》成绩不低于60分，方有资格录取。
二、 推免、单考和强军计划类别生源复试安排
 推免生不再进行复试。
 单考和强军计划考生的复试采取等额复试的办法，且不参加C语言上机考试。
 3月23日下午2:30，单考和强军计划类别参加复试的考生到院会议室（如心楼407）报到，同时领取综合面试记录表、政审表。
 3月24日单考和强军计划类别考生与志愿导师联系，取得导师认可后，参加导师所在组的综合面试。

北京航空航天大学计算机学院
2008年3月18日

计算机学院硕士研究生招生咨询电话：
010－82317630

附件1：
北京航空航天大学计算机学院
2008硕士研究生招生复试资格审核及材料提交办法
参加复试的考生在报到时应提交如下材料以进行资格审核后，方可参加复试：
1. 考生参加研究生入学考试的准考证原件和一份复印件；
2. 本人有效身份证件（身份证、现役军官证、文职干部证）原件和一份复印件，应届本科毕业生还需同时提交本人学生证原件和一份复印件，原件审核后当场退回考生；
3. 非应届本科毕业生需提交：（1）学历证书原件和一份复印件；（2）由档案所在单位人事部门提供的在校历年学习成绩表复印件一份（原件上应有毕业学校公章），并由档案所在单位人事部门加盖公章。
4. 应届本科毕业生需提交所在学校教务部门提供的加盖公章的在校历年学习成绩表一份。
5. 英语六级或四级证书复印件。
国家承认学历的成人应届本科生可按同等学力资格参与复试，但必须同时符合如下条件方有资格录取：
 加试专业成绩合格（加试科目：《C语言程序设计》和《编译原理》）；
 2008年8月底以前获得本科毕业证书；
 在计算机相关领域核心期刊以第一作者发表一篇以上（含）论文；
 2008年8月底以前通过国家英语四级。
获得国家承认的大专毕业证书后到2008年9月1日连续工作两年以上（含）可按同等学力参加复试，但必须同时符合如下条件方有资格录取：
 加试专业成绩合格（加试科目：《C语言程序设计》和《编译原理》）；
 在全日制普通高校辅修完所报专业本科的全部主干课程且成绩合格（提交加盖学校教务处公章的成绩表）；
 在计算机相关领域核心期刊以第一作者发表一篇以上（含）论文；
 2008年8月底以前通过国家英语四级。
以下材料不属于复试资格审核必须的，但希望考生提供：
 考生自述；
 考生获得的校级以上的奖励证书复印件（如果有）
凡提交信息与本人实际情况不符，一经发现，立即取消复试或拟录取资格。无论录取与否，考生复试报到时所提交资料恕不退回。
所有提交的材料均以A4纸大小按如下顺序统一左侧装订（成绩单超过A4的，装订后折叠成A4大小）：
1） 封面（见附件2）
2） 准考证复印件；
3） 有效身份证复印件，应届毕业生将身份证与学生证复印在同一A4纸上；
4） 考生自述；
5） 往届生的学历证复印件和成绩证明，应届生成绩证明；
6） 英语六级或四级证书复印件（有六级证书的不要再提供四级证书）
7） 同等学力考生应提交的其他证明材料；
8） 各类校级以上获奖证书复印件。

北京航空航天大学计算机学院
2008年3月18日

附件2：

北京航空航天大学计算机学院
2008硕士研究生招生复试审核材料

准考证号：
考生姓名：
毕业学校：
所学专业：
初试成绩（总分）：

本人郑重声明：
在此提交的所有材料均与实际情况一致，如有不实之处，本人愿承担由此引起的相关责任。
签名：
时间： 年 月 日

⑵ C语言实现文件排序

常见排序算法（冒泡，选择，快速）的C语言实现
要实现这几种算法的关键是要熟悉算法的思想。简单的说，冒泡排序，就如名字说的，每经过一轮排序，将最大的数沉到最底部。选择排序的思想是将整个数列，分为有序区和无序区。每轮排序，将无序区里的最小数移入到有序区。快速排序的思想是以一个数为中心，通常这个数是该数列第一个数，将整个数列分为两个部分，一个部分是大于这个数的区域，一个部分是小于这个数的区域。然后再对这两个部分的数列分别排序。如果将数列分为两个部分是通过，一方面从后向前的搜索，另一方面从前向后的搜索来实现的。具体的参考后面的来自网络的文档。
从这几个简单的排序算法上看，有几个特点：
冒泡排序是最简单的，也是最稳定的算法。
选择排序不太稳定，但是效率上较冒泡还是有较大的提升。其实在分析的过程中就能发现，选择排序和冒泡排序相比，中间少了很多的交换过程，和比较的次数，这个应该是时间较少的原因。选择排序能够满足一般的使用。当比较的数超过以万为单位时，选择排序也还是要一点时间的。
快速排序据说是最快的。这个可以从思想上看的出来。，当记录较多的时候，快速排序的比较循环次数比上面2个都要少。但是在具体的实现过程中，并不见得如此。这是因为递归效率的低下导致的。当然，估计在实际使用过的过程，快速排序估计都会使用非递归操作栈的方式来实现。那样应该会效率高伤不少。估计我会在后期出一个快速排序的非递归实现来真正比较它们3个性能。在下面的程序中，可以通过调高N的数字就能看的出来冒泡排序和选择排序性能的差异。在N较小，大概几百的时候，是看不出来的。N较大的的时候，比如N=1000或者N=10000的时候，快速排序的递归实现就会卡死在那里了，出不了结果。
以下是具体的代码：
/*
** 常见排序算法比较
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <windows.h>
#define N 10
#define Demo 1

void BubbleSort(int arr[], int n);
void SelectSort(int arr[], int n);
void QuickSort(int arr[], int n);
void PrintArray(int arr[], int n);
void GenerateArray(int arr[], int n);

int main(int argc, char *argv[])
{
int arr[N];

GenerateArray(arr, N);
#if Demo
printf("Before the bubble sort------------------------\n");
PrintArray(arr, N);
#endif
printf("Start Bubble sort----------------------\n");
clock_t start_time1=clock(); //开始计时
BubbleSort(arr, N);
clock_t end_time1=clock(); // 结束计时
printf("Running time is: %lf ms\n", (double)(end_time1-start_time1)/CLOCKS_PER_SEC*1000); //输出运行时间
#if Demo
printf("After the bubble sort------------------------\n");
PrintArray(arr, N);
#endif
printf("-----------------------------------------------------------\n");

sleep(1000); // 单位是毫秒即千分之一秒
GenerateArray(arr, N);
#if Demo
printf("Before the selection sort------------------------\n");
PrintArray(arr, N);
#endif
printf("Start selection sort----------------------\n");
clock_t start_time2=clock(); //开始计时
SelectSort(arr, N);
clock_t end_time2=clock(); // 结束计时
printf("Running time is: %lf ms\n", (double)(end_time2-start_time2)/CLOCKS_PER_SEC*1000); //输出运行时间
#if Demo
printf("After the selection sort------------------------\n");
PrintArray(arr, N);
#endif

printf("-----------------------------------------------------------\n");
sleep(1000); // 单位是毫秒即千分之一秒
GenerateArray(arr, N);
#if Demo
printf("Before the quick sort------------------------\n");
PrintArray(arr, N);
#endif
printf("Start quick sort----------------------\n");
clock_t start_time3=clock(); //开始计时
QuickSort(arr, N);
clock_t end_time3=clock(); // 结束计时
printf("Running time is: %lf ms\n", (double)(end_time3-start_time3)/CLOCKS_PER_SEC*1000); //输出运行时间
#if Demo
printf("After the quick sort------------------------\n");
PrintArray(arr, N);
#endif

system("PAUSE");
return 0;
}

// 产生随机列表
void GenerateArray(int arr[], int n)
{
int i;
srand((unsigned)time(0));

for(i = 0; i <N; i++)
{
arr[i] = rand(); // 生成随机数 范围在0-32767之间
}
}

// 打印列表
void PrintArray(int arr[], int n)
{
int i = 0;
for(i = 0; i < n; i++)
printf("%6d", arr[i]);
printf("\n");
}

// 经典冒泡排序
void BubbleSort(int arr[], int n)
{
int i = 0, j =0;
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];
}
}
}

// 快速排序的递归实现
void QuickSort(int arr[], int n)
{
if(n <= 1)
return;

int i =0 , j = n - 1;
int key = arr[0];
int index = 0;

while(i < j)
{
// 从后向前搜索
while(j > i && arr[j] > key)
j--;
if(j == i)
break;
else
{
//交换 a[j] a[i]
arr[j] = arr[j] ^arr[i];
arr[i] = arr[j] ^arr[i];
arr[j] = arr[j] ^arr[i];
index = j;
}

// 从前向后搜索
while(i < j && arr[i] <key)
i++;
if(i == j)
break;
else
{
// 交换 a[i] a[j]
arr[j] = arr[j] ^arr[i];
arr[i] = arr[j] ^arr[i];
arr[j] = arr[j] ^arr[i];
index = i;
}
}
QuickSort(arr, index);
QuickSort(arr + index + 1, n - 1 - index);
}

// 选择排序
void SelectSort(int arr[], int n)
{
int i, j;
int min;

for(i = 0; i < n - 1; i++)
{
int index = 0;
min = arr[i];
for(j = i + 1; j < n; j++) //找出 i+1 - n 无序区的最小者与arr[i]交换
{
if(arr[j] < min)
{
min = arr[j];
index = j;
}
}
if(index != 0) //表明无序区有比arr[i]小的元素
{
arr[i] = arr[i]^arr[index];
arr[index] = arr[i]^arr[index];
arr[i] = arr[i]^arr[index];
}
}
}

程序里有几点注意的地方：
一，在程序里，交换2个数，我使用了异或来处理。这个可以根据个人喜好。为了避免产生临时变量，可以使用如下几种方式来交换2个数：
a=a^b;
b=a^b;
a=a^b;

或者
a=a+b;
b=a-b;
a=a-b;
使用第二种也挺好的。第一种异或的方式，只适用于，2个数都为int型的，a,b可以正可以负，这个没有关系，但是必须是int类型。
二， sleep()函数是包含在windows.h里面的，要加入 #include <window.h>
三， 关于随机数生成的2个函数 srand()种子发生器函数，还有rand()随机数生成器函数，自己可以参考相关文档。
四， Demo宏来控制是演示还是比较性能用的。当把N调整的很小，比如10的时候，可以设置Demo为1，那样就能打印数组了，可以看到比较前后的情况。当把N调整到很大比如10000的时候，就把Demo设置为0，那样就不打印数组，直接比较性能。

具体的算法文档参考下面的：
冒泡排序
基本概念
冒泡排序（BubbleSort）的基本概念是：依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的数放到了最后。在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。如此下去，重复以上过程，直至最终完成排序。
由于在排序过程中总是小数往前放，大数往后放，相当于气泡往上升，所以称作冒泡排序。
用二重循环实现，外循环变量设为i，内循环变量设为j。外循环重复9次，内循环依次重复9，8，...，1次。每次进行比较的两个元素都是与内循环j有关的，它们可以分别用a[j]和a[j+1]标识，i的值依次为1,2,...,9，对于每一个i, j的值依次为1,2,...10-i。
产生
在许多程序设计中，我们需要将一个数列进行排序，以方便统计，而冒泡排序一直由于其简洁的思想方法而倍受青睐。
排序过程
设想被排序的数组R［1..N］垂直竖立，将每个数据元素看作有重量的气泡，根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R，凡扫描到违反本原则的轻气泡，就使其向上"漂浮"，如此反复进行，直至最后任何两个气泡都是轻者在上，重者在下为止。
算法示例
A[0] 、 A[1]、 A[2]、 A[3]、 A[4]、 A[5]、 A[6]：
49 38 65 97 76 13 27
第一趟冒泡排序过程
38 49 65 97 76 13 27
38 49 65 97 76 13 27
38 49 65 97 76 13 27
38 49 65 76 97 13 27
38 49 65 76 13 97 27
38 49 65 76 13 27 97 – 这是第一趟冒泡排序完的结果
第二趟也是重复上面的过程，只不过不需要比较最后那个数97，因为它已经是最大的
38 49 65 13 27 76 97 – 这是结果
第三趟继续重复，但是不需要比较倒数2个数了
38 49 13 27 65 76 97
….
选择排序
基本思想
n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果：
①初始状态：无序区为R[1..n]，有序区为空。
②第1趟排序
在无序区R[1..n]中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[1]交换，使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
……
③第i趟排序
第i趟排序开始时，当前有序区和无序区分别为R[1..i-1]和R(1≤i≤n-1)。该趟排序从当前无序区中选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
这样，n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。
常见的选择排序细分为简单选择排序、树形选择排序（锦标赛排序）、堆排序。上述算法仅是简单选择排序的步骤。
排序过程
A[0] 、 A[1]、 A[2]、 A[3]、 A[4]、 A[5]、 A[6]：
49 38 65 97 76 13 27
第一趟排序后 13 ［38 65 97 76 49 27]
第二趟排序后 13 27 ［65 97 76 49 38]
第三趟排序后 13 27 38 [97 76 49 65]
第四趟排序后 13 27 38 49 [76 97 65]
第五趟排序后 13 27 38 49 65 [97 76]
第六趟排序后 13 27 38 49 65 76 [97]
最后排序结果 13 27 38 49 49 65 76 97
快速排序算法
算法过程
设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。一趟快速排序的算法是：
1）设置两个变量I、J，排序开始的时候：I=0，J=N-1；
2）以第一个数组元素作为关键数据，赋值给key，即 key=A[0]；
3）从J开始向前搜索，即由后开始向前搜索（J=J-1），找到第一个小于key的值A[J]，并与A[I]交换；
4）从I开始向后搜索，即由前开始向后搜索（I=I+1），找到第一个大于key的A[I]，与A[J]交换；
5）重复第3、4、5步，直到 I=J； (3,4步是在程序中没找到时候j=j-1，i=i+1，直至找到为止。找到并交换的时候i， j指针位置不变。另外当i=j这过程一定正好是i+或j+完成的最后另循环结束)
例如：待排序的数组A的值分别是：（初始关键数据：X=49） 注意关键X永远不变，永远是和X进行比较，无论在什么位子，最后的目的就是把X放在中间，小的放前面大的放后面。
A[0] 、 A[1]、 A[2]、 A[3]、 A[4]、 A[5]、 A[6]：
49 38 65 97 76 13 27
进行第一次交换后： 27 38 65 97 76 13 49
( 按照算法的第三步从后面开始找)
进行第二次交换后： 27 38 49 97 76 13 65
( 按照算法的第四步从前面开始找>X的值，65>49,两者交换，此时：I=3 )
进行第三次交换后： 27 38 13 97 76 49 65
( 按照算法的第五步将又一次执行算法的第三步从后开始找
进行第四次交换后： 27 38 13 49 76 97 65
( 按照算法的第四步从前面开始找大于X的值，97>49,两者交换，此时：I=4,J=6 )
此时再执行第三步的时候就发现I=J，从而结束一趟快速排序，那么经过一趟快速排序之后的结果是：27 38 13 49 76 97 65，即所以大于49的数全部在49的后面，所以小于49的数全部在49的前面。
快速排序就是递归调用此过程——在以49为中点分割这个数据序列，分别对前面一部分和后面一部分进行类似的快速排序，从而完成全部数据序列的快速排序，最后把此数据序列变成一个有序的序列，根据这种思想对于上述数组A的快速排序的全过程如图6所示：
初始状态 {49 38 65 97 76 13 27}
进行一次快速排序之后划分为 {27 38 13} 49 {76 97 65}
分别对前后两部分进行快速排序 {27 38 13} 经第三步和第四步交换后变成 {13 27 38} 完成排序。
{76 97 65} 经第三步和第四步交换后变成 {65 76 97} 完成排序。

⑶ 数据结构中快速排序算法的不足以及改进

一般快速排序算法都是以最左元素作为划分的基准值，这样当数据元素本身已经完全有序（不管正序或者逆序）时，每一趟划分只能将一个元素分割出来，其效率很低：时间复杂度O(n^2)，空间复杂度为O(n)
所以改进方法就是找寻合适的基准值，保证不至于在关键字有序或者接近有序时发生这个情况，一般可以使用三者取中（就是待划分序列的头元素、尾元素、中间元素三者的中间值）、或者随机选择等方法，这样即使关键字完全有序，也可以保证时间复杂度O(nlogn)，空间复杂度O(logn)