当前位置：文档之家 › 各种排序算法时间性能的比较讲解

各种排序算法时间性能的比较讲解

  • 格式：doc
  • 大小：261.55 KB
  • 文档页数：12

实训报告 实训题目：各种排序算法时间性能的比较

学 院： 计算机科学与技术学院 专 业： 软件工程 班 级： 142 学 号： 1400170269 学生姓名： 莫磊 指导教师： 蔡丽

2016年 3 月15 日 一、实训目的及要求 数据结构是计算机课程的一门重要的基础课，它的教学要求大致有三个重要方面：其一就是让学生学会分析研究计算机加工的数据对象的特性，以便为数据选择适当的物理结构和逻辑结构；其二，根据结构，选择适当的算法，并初步掌握算法的时间分析和空间分析；其三，学习复杂的程序设计。本综合实训利用Visual Studio 2008 集成编程环境为实践工具，通过上机实践培养学生分析具体问题、解决实际问题的能力，训练和培养学生的数据抽象能力和程序设计的能力。 数据结构是一门实践性较强的课程，以培养学生的数据抽象能力和程序设计的能力为目的。在实训时应注重培养学生的实际操作能力。本综合实训安排了18学时的实验课时，具体要求如下： 1. 学习和理解每个实训题目的基本理论和方法； 2. 掌握每个实验的实现步骤和关键技术； 3. 准备好实验所需要的资源和文档； 4. 上机实现程序，得到通过调试的正确程序。 5. 根据每个实验的不同要求，完成实验报告的word文档。

二、实训环境 Windows XP Visual Studio 2013

三、实训内容 (1) 设计并实现上述各种排序算法； (2) 产生正序和逆序的初始排列分别调用上述排序算法，并比较时间性能； (3) 产生随机的初始排列分别调用上述排序算法，并比较时间性能。 （4）对各种排序方法（直接插入排序、希尔排序、起泡排序、直接选择排序）的时间性能进行比较。

四、算法描述及实训步骤 上述各种排序方法都是基于比较的内排序，其时间主要消耗在排序过程中进行的记录的比较次数和移动次数，因此，统计在相同数据状态下不同排序算法的比较次数和移动次数，即可实现比较各种排序算法的目的。 五、总结及心得体会 直接选择排序算法是对冒泡排序的改进，这种方法是在参加排序数组中找出最小（或最大）的数据元素，使它与第一个元素中的数据相互交换位置然后再在余下的元素中找出最小（或最大）的数据元素与第二个元素中的元素交换位置，以此类推直到所有元素成为有序序列。 六、实训结果 七、源代码： #include #include #include

//正序希尔排序 void xiEr(int num[], int n, int &no, int &r){ int item; int i, j, d; for (d = n / 2; d >= 1; d = d / 2){ for (i = d; iitem = num[i]; j = i - d; while ((j >= 0) && (itemnum[j + d] = num[j]; j = j - d; r = r + 1; } num[j + d] = item; no = no + 1; } } // printf("\n"); // for(int x=0;x// printf("%d\t",num[x]); // } }

//逆序希尔排序 void xiErUp(int num[], int n, int &no, int &r){ int item; int i, j, d; for (d = n / 2; d >= 1; d = d / 2){ for (i = d; iitem = num[i]; j = i - d; while ((j >= 0) && (item>num[j])){ num[j + d] = num[j]; j = j - d; r = r + 1; } num[j + d] = item; no = no + 1; } } }

//正序冒泡排序 void MaoPao(int num[], int n, int &no, int &r){ bool flag; int test; for (int i = 1; iflag = true; for (int j = n - 1; j >= i; j--){ if (num[j]test = num[j]; num[j] = num[j - 1]; num[j - 1] = test; flag = false; r++; } no++; } if (flag){ return; } } } void MaoPaoUp(int num[], int n, int &no, int &r){ bool flag; int test; for (int i = 1; iflag = true; for (int j = n - 1; j >= i; j--){ if (num[j]>num[j - 1]){ test = num[j]; num[j] = num[j - 1]; num[j - 1] = test; flag = false; r++; } no++; } if (flag){ return; } } }

void ChaRu(int num[], int n, int &no, int &r)//直接插入排序 { // :比较次数，r : 移动次数。 int i, j, x; for (i = 1; i{ no++; x = num[i]; j = i - 1; while ((j >= 0) && (x{ r++; num[j + 1] = num[j]; j--; } // 顺序比较和移动 num[j + 1] = x; } }

void ChaRuUp(int num[], int n, int &no, int &r)//直接插入排序 { //:比较次数，r : 移动次数。 int i, j, x; for (i = 1; i{ no++; x = num[i]; j = i - 1; while ((j >= 0) && (x>num[j])) { r++; num[j + 1] = num[j]; j--; } // 顺序比较和移动 num[j + 1] = x; } }

void XuanZe(int num[], int n, int &no, int &r)//直接选择排序/:比较次数,r:移动次数 { int x; int i, j, k; for (i = 1; i <= n - 1; i++) { k = i - 1; for (j = i; j <= n - 1; j++) { no++; if (num[j] < num[k]) k = j; } if (k != i - 1) { r++; x = num[i - 1]; num[i - 1] = num[k]; num[k] = x; } } }

void XuanZeUp(int num[], int n, int &no, int &r)//直接选择排序/:比较次数,r:移动次数 { int x; int i, j, k; for (i = 1; i <= n - 1; i++) { k = i - 1; for (j = i; j <= n - 1; j++) { no++; if (num[j] > num[k]) k = j; } if (k != i - 1) { r++; x = num[i - 1]; num[i - 1] = num[k]; num[k] = x; } } }

void ShuChu(int num[], int n, int no, int r, char name[]){ printf("===============输出%s排序后数据如下==============\n\n", name); for (int x = 0; xprintf("%d\t", num[x]); } printf("\n比较的次数为:%d\t移动的次数为:%d", no, r); printf("\n===========================================================\n\n"); } int main(){ int num[100]; int n = 100; int no1, no2, no3, no4; int r1, r2, r3, r4; int no11, no22, no33, no44; int r11, r22, r33, r44; char name1[] = "希尔正序"; char name11[] = "希尔逆序"; char name2[] = "冒泡正序"; char name22[] = "冒泡逆序"; char name3[] = "直接插入正序"; char name33[] = "直接插入逆序"; char name4[] = "直接选择正序"; char name44[] = "直接选择逆序"; int item1[100]; int item2[100]; int item3[100]; int item4[100]; int item22[100]; int item33[100]; int item44[100]; no4 = no3 = no2 = no1 = 0; r4 = r3 = r2 = r1 = 0; no44 = no33 = no22 = no11 = 0; r44 = r33 = r22 = r11 = 0; printf("============初始的随机数据如下===========\n\n"); for (int i = 0; inum[i] = rand() %100; printf("%d\t", num[i]); }

合集下载

各种排序的时间复杂度

各种排序的时间复杂度

排序算法所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

分类在计算机科学所使用的排序算法通常被分类为：计算的复杂度（最差、平均、和最好表现），依据串列（list）的大小（n）。

一般而言，好的表现是O。

(n log n)，且坏的行为是Ω(n2)。

对於一个排序理想的表现是O(n)。

仅使用一个抽象关键比较运算的排序算法总平均上总是至少需要Ω(n log n)。

记忆体使用量（以及其他电脑资源的使用）稳定度：稳定排序算法会依照相等的关键（换言之就是值）维持纪录的相对次序。

也就是一个排序算法是稳定的，就是当有两个有相等关键的纪录R和S，且在原本的串列中R出现在S之前，在排序过的串列中R也将会是在S之前。

一般的方法：插入、交换、选择、合并等等。

交换排序包含冒泡排序（bubble sort）和快速排序（quicksort）。

选择排序包含shaker排序和堆排序（heapsort）。

当相等的元素是无法分辨的，比如像是整数，稳定度并不是一个问题。

然而，假设以下的数对将要以他们的第一个数字来排序。

(4, 1) (3, 1) (3, 7) (5, 6)在这个状况下，有可能产生两种不同的结果，一个是依照相等的键值维持相对的次序，而另外一个则没有：(3, 1) (3, 7) (4, 1) (5, 6) (维持次序)(3, 7) (3, 1) (4, 1) (5, 6) (次序被改变)不稳定排序算法可能会在相等的键值中改变纪录的相对次序，但是稳定排序算法从来不会如此。

不稳定排序算法可以被特别地时作为稳定。

作这件事情的一个方式是人工扩充键值的比较，如此在其他方面相同键值的两个物件间之比较，就会被决定使用在原先资料次序中的条目，当作一个同分决赛。

然而，要记住这种次序通常牵涉到额外的空间负担。

排列算法列表在这个表格中，n是要被排序的纪录数量以及k是不同键值的数量。

稳定的冒泡排序（bubble sort）— O(n2)鸡尾酒排序 (Cocktail sort, 双向的冒泡排序) — O(n2)插入排序（insertion sort）— O(n2)桶排序（bucket sort）— O(n); 需要 O(k) 额外记忆体计数排序 (counting sort) — O(n+k); 需要 O(n+k) 额外记忆体归并排序（merge sort）— O(n log n); 需要 O(n) 额外记忆体原地归并排序— O(n2)二叉树排序（Binary tree sort）— O(n log n); 需要 O(n) 额外记忆体鸽巢排序 (Pigeonhole sort) — O(n+k); 需要 O(k) 额外记忆体基数排序（radix sort）—O(n·k); 需要 O(n) 额外记忆体Gnome sort — O(n2)Library sort — O(n log n) with high probability, 需要(1+ε)n 额外记忆体不稳定选择排序（selection sort）— O(n2)希尔排序（shell sort）— O(n log n) 如果使用最佳的现在版本Comb sort — O(n log n)堆排序（heapsort）— O(n log n)Smoothsort — O(n log n)快速排序（quicksort）—O(n log n) 期望时间, O(n2) 最坏情况; 对於大的、乱数串列一般相信是最快的已知排序Introsort — O(n log n)Patience sorting —O(n log n + k) 最外情况时间, 需要额外的 O(n + k) 空间, 也需要找到最长的递增子序列（longest increasing subsequence）不实用的排序算法Bogo排序—O(n × n!) 期望时间, 无穷的最坏情况。

各种经典排序算法

各种经典排序算法


希尔插入排序——过程
设待排序共有10个记录，其关键字分别为47, 33, 61, 82, 71,
11, 25, 47, 57, 02，增量序列取值依次为5, 3, 1。
排 序
希尔插入排序——特点
希尔排序实质上还是一种插入排序，其主要特点是： 每一趟以不同的增量进行排序。在每趟的插入排序中，记录 的关键字是和同一组中的前一个关键字进行比较，所以关键
排 序
3、排序的基本操作
排序的概念：就是要整理文件中的记录，使之按关键字 递增(或递减)次序排列起来。
排序过程的组成步骤：首先比较两个关键字的大小； 然 后将记录从一个位置移动到另一个位置。 对记录的关键字大小进行比较 将记录从一个位置移动到另一个位置 当待排序记录的关键字均不相同时，则排序结果是唯一 的，否则排序的结果不一定唯一。
3．将L.r[i] 插入到L.r[j+1]的位臵上。
具体方法：先将第一个数据看成是一个有序的子序列， 然后从第2个数据起逐个插入到这个有序的子序列中去， 相应的元素要移动。
排 序
例：
待排元素序列：[53] 第一次排序： 第二次排序： 第三次排序： 第四次排序： 第五次排序： [27 [27 [15 [15 [15 27 53] 36 27 27 27 36 36 53] 36 36 36 15 15 15 53] 53 42 69 69 69 69 69] 53 42 42 42 42 42 69] 对于有n个数 据元素的待排 序列，插入操 作要进行n-1 次
有序序列L.r[1..i-1]
L.r[i]
无序序列 L.r[i..n]
有序序列L.r[1..i]
无序序列 L.r[i+1..n]
排序—时间复杂度为O（n2）的三种排序算法

排序—时间复杂度为O（n2）的三种排序算法

排序—时间复杂度为O（n2）的三种排序算法1 如何评价、分析⼀个排序算法？很多语⾔、数据库都已经封装了关于排序算法的实现代码。

所以我们学习排序算法⽬的更多的不是为了去实现这些代码，⽽是灵活的应⽤这些算法和解决更为复杂的问题，所以更重要的是学会如何评价、分析⼀个排序算法并在合适的场景下正确使⽤。

分析⼀个排序算法，主要从以下3个⽅⾯⼊⼿：1.1 排序算法的执⾏效率1）最好情况、最坏情况和平均情况时间复杂度待排序数据的有序度对排序算法的执⾏效率有很⼤影响，所以分析时要区分这三种时间复杂度。

除了时间复杂度分析，还要知道最好、最坏情况复杂度对应的要排序的原始数据是什么样的。

2）时间复杂度的系数、常数和低阶时间复杂度反映的是算法执⾏时间随数据规模变⼤的⼀个增长趋势，平时分析时往往忽略系数、常数和低阶。

但如果我们排序的数据规模很⼩，在对同⼀阶时间复杂度的排序算法⽐较时，就要把它们考虑进来。

3）⽐较次数和交换（移动）次数内排序算法中，主要进⾏⽐较和交换（移动）两项操作，所以⾼效的内排序算法应该具有尽可能少的⽐较次数和交换次数。

1.2 排序算法的内存消耗也就是分析算法的空间复杂度。

这⾥还有⼀个概念—原地排序，指的是空间复杂度为O(1)的排序算法。

1.3 稳定性如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变，那么这种排序算法叫做稳定的排序算法；如果前后顺序发⽣变化，那么对应的排序算法就是不稳定的排序算法。

在实际的排序应⽤中，往往不是对单⼀关键值进⾏排序，⽽是要求排序结果对所有的关键值都有序。

所以，稳定的排序算法往往适⽤场景更⼴。

2 三种时间复杂度为O(n2)的排序算法2.1 冒泡排序2.1.1 原理两两⽐较相邻元素是否有序，如果逆序则交换两个元素，直到没有逆序的数据元素为⽌。

每次冒泡都会⾄少让⼀个元素移动到它应该在的位置。

2.1.2 实现void BubbleSort(int *pData, int n) //冒泡排序{int temp = 0;bool orderlyFlag = false; //序列是否有序标志for (int i = 0; i < n && !orderlyFlag; ++i) //执⾏n次冒泡{orderlyFlag = true;for (int j = 0; j < n - 1 - i; ++j) //注意循环终⽌条件{if (pData[j] > pData[j + 1]) //逆序{orderlyFlag = false;temp = pData[j];pData[j] = pData[j + 1];pData[j + 1] = temp;}}}}测试结果2.1.3 算法分析1）时间复杂度最好情况时间复杂度：当待排序列已有序时，只需⼀次冒泡即可。

常用排序算法的时间复杂度和空间复杂度

常用排序算法的时间复杂度和空间复杂度

常⽤排序算法的时间复杂度和空间复杂度以上快速排序和归并排序的空间复杂度不正确没有的参考图1，以图2为准（对，就是懒得重新画图了）排序法最差时间分析平均时间复杂度稳定度空间复杂度冒泡排序O(n2)O(n2)稳定O(1)快速排序O(n2)O(n*log2n)不稳定O(log2n)~O(n)选择排序O(n2)O(n2)稳定O(1)⼆叉树排O(n2)O(n*log2n)不稳定O(n)序插⼊排序O(n2)O(n2)稳定O(1)堆排序O(n*log2n)O(n*log2n)不稳定O(1)希尔排序O O不稳定O(1)1.插⼊排序由N-1趟排序组成，对于p=1到p=N-1趟，插⼊排序保证从位置0到位置p上的元素为已排序状态。

时间复杂度：O(N^2)代码void InsertionSort(ElementType A[],int N){int j,p;ElementType Tmp;for(p=1;p<N;p++){Tmp=A[j];//把A[j]保存下来，因为它要被插⼊到前⾯的某个位置去for(j=p;j>0&&A[j-1]>Tmp;j--)//⼤于A[j]的元素逐个后移{A[j]=A[j-1];}A[j]=Tmp;}}2.希尔排序希尔排序使⽤⼀个序列h1，h2，h3，ht，叫做增量排序。

在使⽤增量hk的⼀趟排序之后，对于每个i我们有A[i]<A[i+hk]，所有相隔hk的元素被排序。

时间复杂度：O(N^(1+a))，其中0<a<1。

//代码不太好理解，使⽤了3层循环void ShellSort(ElementType A[],int N){int j,p,Increment;ElementType Tmp;for(Increment=N/2;Increment>0;Increment/=2){for(p=Increment;p<N;p++){Tmp=A[p];for(j=p;j>=Increment;j-=Increment){if(A[j]<A[j-Increment])A[j]=A[j-Increment];elsebreak;}A[j]=Tmp;}}}3. 堆排序思想：建⽴⼩顶堆，然后执⾏N次deleteMin操作。