排序算法

1 #include 2 using namespace std; 3

4 /*///////////////////////////////////////////////////////////////////////// 5 以下为快速排序

6 /////////////////////////////////////////////////////////////////////////*/ 7 /*

8 冒泡排序 9 算法：

10 核心思想是扫描数据清单，寻找出现乱序的两个相邻的项目。当找到这两个项目后 11 交换项目的位置然后继续扫描。重复上面的操作直到所有的项目都按顺序排好 12 时间复杂度n*n (n-1)*n/2 13 */

14 void BubbleSortData(int SortData[], int Length) 15 {

16 int tmpData =0;

17 bool swapFlag =true; 18

19 for (int i=Length-1; i>0 && swapFlag; i--) 20 {

2

注：已经整理第一节到第六节(程序代码均已测试)，第七节到第十一节暂未整理

一、 排序问题

1.1 排序问题的定义

排序问题的输入是一个线性表，该线性表的元素属于一个偏序集；要求对该线性表的元素做某种重排，使得线性表中除表尾外的每个元素都小于等于（或大于等于）它的后继。

设R为非空集合A上的二元关系，如果R满足自反性(对于每一个x?A，

(x,x)?R)，反对称性((x,y)?R&(y,x)?R?x?y)和传递性

((x,y)?R&(y,z)?R?(x,z)?R)，则称R为A上的偏序关系，记作?。如果

(x,y)?R，则记作x?y，读作“x小于等于y”。存在偏序关系的集合A称为

偏序集。（注意，这里的?不是指数的大小，而是指在偏序关系中的顺序性。x?y的含

义是：按照这个序，x排在y前面。根据不同的偏序定义，?有不同的解释。例如整除关系是偏序关系?，3?6的含义是3整除6。大于或等于关系也是偏序关系，针对这个关系5?4是指在大于或等于关系中5排在4的前面，也就是说5比4大。）

在实际应用中，经常遇到的偏序关系是定义在一个记录类型的数据集合上的。在该记录类型中有一个主键域key，key域的类型是某一个偏序集，记录的其他域称为数据。比较线性表中的两个元素Li

课程设计说明书

设计名称： 数据结构课程设计

题 目： 排序算法比较

学生姓名：

专 业： 计算机科学与技术 班 级： 11级一班 学 号：

指导教师： 李娅 日 期： 2013 年 3 月 20 日

1

课程设计任务书

计算机科学与技术 专业 11 年级 班 一、 设计题目 各种算法排序比较 二、 主要内容

利用随机函数产生N个随机整数（N<10000），对这些数进行多种方法排序。

三、 要求

1)至少采用4种方法实现上述问题求解（可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序），并把排序后的结果保存在不同的文件里。

2）给出该排序算法对数据的比较次数和移动次数并统计每一种排序方法的性能（以运行程序所花费的时间为准进行对比），找出其中两种较快的方法。

四、 进度安排

1）资料阅读查找、系统分析，概要设计；时间安排0.5天 2）系统详细设计、功能设计；时间安排0.5天

课程设计(论文)任务书

学 院 计算机科学与技术 专 业 2005-1 班

一、课程设计(论文)题目 各种排序算法演示

二、课程设计(论文)工作自 2007 年 6 月 25 日起至 2007 年 7 月 8 日止。

三、课程设计(论文) 地点: 多媒体实验室(5-302,303) 四、课程设计(论文)内容要求： 1．本课程设计的目的

（1）熟练掌握C语言的基本知识和技能；

（2）掌握各种排序（直接插入，希尔，冒泡，快速排序，简单选择，堆排序）方法及适用场合，并能在解决实际问题时灵活应用；

（3）从空间和时间的角度分析各种排序；

（5）培养分析、解决问题的能力；提高学生的科技论文写作能力。

2．课程设计的任务及要求 1）基本要求：

（1）设计一个的菜单将在实现的功能显示出来，并有选择提示；

（2）分别实现直接插入，希尔，冒泡，快速排序，简单选择，堆排序算法； （3）通过多种测试数据，对各种排序算法的时间复杂度和空间复杂度进行比较并说明在实际

第8 章排序(算法设计)习题练习答案

13. 将哨兵放在R[n]中，被排序的记录放在R[0..n-1]中，重写直接插入排序算法。

解： 重写的算法如下： void InsertSort(SeqList R)

{//对顺序表中记录R[0..n-1]按递增序进行插入排序 int i,j;

for(i=n-2;i>=0;i--) //在有序区中依次插入R[n-2]..R[0] 课后答案网 www.khdaw.com

if(R[i].key>R[i+1].key) //若不是这样则R[i]原位不动 {

R[n]=R[i];j=i+1; //R[n]是哨兵

do{ //从左向右在有序区中查找插入位置 R[j-1]=R[j]; //将关键字小于R[i].key 的记录向右移 j++;

}while(R[j].key

R[j-1]=R[n]; //将R[i]插入到正确位置上 }//endif }//InsertSort.

14.以单链表作为存储结构实现直接插入排序算法。 解： #define int KeyType //定义KeyType 为int 型 typedef struct node{

KeyType key; //关键字域

OtherInfoTyp

常见经典排序算法

1.希尔排序 2.二分插入法 3.直接插入法

4.带哨兵的直接排序法 5.冒泡排序 6.选择排序 7.快速排序 8.堆排序

一.希尔（Shell）排序法（又称宿小增量排序，是1959年由D.L.Shell提出来的） /* Shell 排序法 */ #include

void sort(int v[],int n) {

int gap,i,j,temp;

for(gap=n/2;gap>0;gap /= 2) /* 设置排序的步长，步长gap每次减半，直到减到1 */ {

for(i=gap;i

for(j=i-gap;(j >= 0) && (v[j] > v[j+gap]);j -= gap ) /* 比较相距gap远的两个元素的大小，根据排序方向决定如何调换 */ {

temp=v[j]; v[j]=v[j+gap]; v[j+gap]=temp; } } }

数据结构程序设计

内部排序算法比较

目录

摘 要 ........................................................................................................................... 1 1绪论 ............................................................................................................................ 1 2系统分析 .................................................................................................................... 1 2.1 功能需求 ............................................................................................................. 1

三种冒泡排序,附有自己编写的源文件。

冒泡排序（沉底排序）

1. 基础冒泡排序

基础冒泡排序通过两个循环控制，第一重循环控制整个大的循环次数，第二重循环着重数组或者结构体内大小的比较，在算法的优化问题上，主要对这两重循环进行优化。 程序代码：

BubbleSort.cpp

核心代码：

for(int i=1;i<=n-1;i++) //数组的零号单元不使用。 for(int j=1;j<=n-i;j++) { count++; if(a[j]>a[j+1]) { temp=a[j];a[j]=a[j+1];a[j+1]=temp; //交换两个变量的值，比较简单。

} } 程序运行结果：

初始数据2,1,3,4,5,6,7,8,9,10

n 1 n

最基础的冒泡排序，对于n个数，无论n个数字怎样排列，比较次数为

2. 冒泡排序第一步改进。 程序代码：

2

BubbleSort2.cpp

核心代码：

三种冒泡排序,附有自己编写的源文件。

程序运行结果：

初始数据2,1,3,4,5,6,7,8,9,10

改进思想：

n 1 n

改进后的冒泡排序，对于n个数，无论n个数字怎样排列，比较次数一般会

常见经典排序算法

1.希尔排序 2.二分插入法 3.直接插入法

4.带哨兵的直接排序法 5.冒泡排序 6.选择排序 7.快速排序 8.堆排序

一.希尔（Shell）排序法（又称宿小增量排序，是1959年由D.L.Shell提出来的） /* Shell 排序法 */ #include

void sort(int v[],int n) {

int gap,i,j,temp;

for(gap=n/2;gap>0;gap /= 2) /* 设置排序的步长，步长gap每次减半，直到减到1 */ {

for(i=gap;i

for(j=i-gap;(j >= 0) && (v[j] > v[j+gap]);j -= gap ) /* 比较相距gap远的两个元素的大小，根据排序方向决定如何调换 */ {

temp=v[j]; v[j]=v[j+gap]; v[j+gap]=temp; } } }

package cn.ily;

import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.File;

import java.io.FileNotFoundException; import java.io.FileReader; import java.io.FileWriter; import java.io.IOException; import java.util.Random; import java.util.Scanner;

public class ReadTxt01 {

private static int NUM = 20000;

public static void main(String[] args) { int flag = 0; int exit = 0; int[] a = null;

long startTime = 0L; long resultTime = 0L; start();

Scanner reader = new Scanner(System.in); fla