下载文档原格式
⼗⼤经典排序算法总结最近⼏天在研究算法，将⼏种排序算法整理了⼀下，便于对这些排序算法进⾏⽐较，若有错误的地⽅，还请⼤家指正0、排序算法说明0.1 排序术语稳定：如果a=b,且a原本排在b前⾯，排序之后a仍排在b的前⾯不稳定：如果a=b,且a原本排在b前⾯，排序之后排在b的后⾯时间复杂度：⼀个算法执⾏所耗费的时间空间复杂度：⼀个算法执⾏完所需内存的⼤⼩内排序：所有排序操作都在内存中完成外排序：由于数据太⼤，因此把数据放在磁盘中，⽽排序通过磁盘和内存的数据传输才能进⾏0.2算法时间复杂度、空间复杂度⽐较0.3名词解释n:数据规模k:桶的个数In-place:占⽤常数内存，不占⽤额外内存Out-place:占⽤额外内存0.4算法分类1.冒泡排序冒泡排序是⼀种简单的排序算法。
它重复地⾛访过要排序的数列，⼀次⽐较两个元素，如果它们的顺序错误就把它们交换过来。
⾛访数列的⼯作是重复地进⾏直到没有再需要交换，也就是说该数列已经排序完成。
这个算法的名字由来是因为越⼩的元素会经由交换慢慢“浮”到数列的顶端1.1算法描述⽐较相邻的元素，如果前⼀个⽐后⼀个打，就交换对每⼀对相邻元素做同样的⼯作，从开始第⼀对到结尾最后⼀对，这样在最后的元素应该会是最⼤的数针对所有的元素重复以上的步骤，除了最后⼀个重复步骤1-3，知道排序完成1.2动图演⽰1.3代码实现public static int[] bubbleSort(int[] array) {if (array.length == 0)return array;for (int i = 0; i < array.length; i++)for (int j = 0; j < array.length - 1 - i; j++)if (array[j + 1] < array[j]) {int temp = array[j + 1];array[j + 1] = array[j];array[j] = temp;}return array;}1.4算法分析最佳情况：T(n) = O(n) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(n2)2.选择排序表现简单直观的最稳定的排序算法之⼀，因为⽆论什么数据都是O(n2)的时间复杂度，⾸先在未排序序列中找到最⼩（⼤）元素，与数组中第⼀个元素交换位置，作为排序序列的起始位置，然后再从剩余未排序元素中继续寻找最⼩（⼤）的元素，与数组中的下⼀个元素交换位置，也就是放在已排序序列的末尾2.1算法描述1.初始状态：⽆序区为R[1..n],有序区为空2.第i躺排序开始时，当前有序区和⽆序区R[1..i-1]、R[i..n]3.n-1趟结束，数组有序化2.2动图演⽰2.3代码实现public static int[] selectionSort(int[] array) {if (array.length == 0)return array;for (int i = 0; i < array.length; i++) {int minIndex = i;for (int j = i; j < array.length; j++) {if (array[j] < array[minIndex]) //找到最⼩的数minIndex = j; //将最⼩数的索引保存}int temp = array[minIndex];array[minIndex] = array[i];array[i] = temp;}return array;}2.4算法分析最佳情况：T(n) = O(n2) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(n2)3、插⼊排序是⼀种简单直观的排序算法，通过构建有序序列，对于未排序序列，在已排序序列中从后向前扫描，找到相应位置并插⼊，需要反复把已排序元素逐步向后挪位，为最新元素腾出插⼊空间3.1算法描述1.从第⼀个元素开始，该元素可以认为已经被排序2.取出下⼀个元素（h），在已排序的元素序列中从后往前扫描3.如果当前元素⼤于h，将当前元素移到下⼀位置4.重复步骤3，直到找到已排序的元素⼩于等于h的位置5.将h插⼊到该位置6.重复步骤2-53.2动图演⽰3.3代码实现public static int[] insertionSort(int[] array) {if (array.length == 0)return array;int current;for (int i = 0; i < array.length - 1; i++) {current = array[i + 1];int preIndex = i;while (preIndex >= 0 && current < array[preIndex]) {array[preIndex + 1] = array[preIndex];preIndex--;}array[preIndex + 1] = current;}return array;}3.4算法分析最佳情况：T(n) = O(n) 最坏情况：T(n) = O(n2) 平均情况：T(n) = O(n2)4、希尔排序是简单插⼊排序经过改进之后的⼀个更⾼效的版本，也称为缩⼩增量排序，同时该算法是冲破O(n2）的第⼀批算法之⼀。
第10章排序10.1 知识点分析1．排序基本概念：（1）排序将数据元素的任意序列，重新排列成一个按关键字有序（递增或递减）的序列的过程称为排序。
（2）排序方法的稳定和不稳定若对任意的数据元素序列，使用某个排序方法，对它按关键字进行排序，若对原先具有相同键值元素间的位置关系，排序前与排序后保持一致，称此排序方法是稳定的；反之，则称为不稳定的。
（3）内排序整个排序过程都在内存进行的排序称为内排序，本书仅讨论内排序。
（4）外排序待排序的数据元素量大，以致内存一次不能容纳全部记录，在排序过程中需要对外存进行访问的排序称为外排序。
2．直接插入排序直接插入排序法是将一个记录插到已排序好的有序表中，从而得到一个新的，记录数增1的有序表。
3．二分插入排序二分插入排序法是用二分查找法在有序表中找到正确的插入位置，然后移动记录，空出插入位置，再进行插入的排序方法。
4．希尔排序希尔排序的基本思想是：先选取一个小于n的整数d1作为第一个增量，把待排序的数据分成d1个组，所有距离为d1的倍数的记录放在同一个组内，在各组内进行直接插入排序，每一趟排序会使数据更接近于有序。
然后，取第二个增量d2，d2< d1，重复进行上述分组和排序，直至所取的增量d i=1（其中d i< d i-1 < ……< d2< d1），即所有记录在同一组进行直接插入排序后为止。
5．冒泡排序冒泡法是指每相邻两个记录关键字比大小，大的记录往下沉（也可以小的往上浮）。
每一遍把最后一个下沉的位置记下，下一遍只需检查比较到此为止；到所有记录都不发生下沉时，整个过程结束。
6．快速排序快速排序法是通过一趟排序，将待排序的记录组分割成独立的两部分，其中前一部分记录的关键字均比枢轴记录的关键字小；后一部分记录的关键字均比枢轴记录的关键字大，枢轴记录得到了它在整个序列中的最终位置并被存放好。
第二趟再分别对分割成两部分子序列，再进行快速排序，这两部分子序列中的枢轴记录也得到了最终在序列中的位置而被存放好，并且它们又分别分割出独立的两个子序列……。
C语⾔⼋⼤排序算法C语⾔⼋⼤排序算法，附动图和详细代码解释！来源：C语⾔与程序设计、⽵⾬听闲等⼀前⾔如果说各种编程语⾔是程序员的招式，那么数据结构和算法就相当于程序员的内功。
想写出精炼、优秀的代码，不通过不断的锤炼，是很难做到的。
⼆⼋⼤排序算法排序算法作为数据结构的重要部分，系统地学习⼀下是很有必要的。
1、排序的概念排序是计算机内经常进⾏的⼀种操作，其⽬的是将⼀组“⽆序”的记录序列调整为“有序”的记录序列。
排序分为内部排序和外部排序。
若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序。
反之，若参加排序的记录数量很⼤，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。
2、排序分类⼋⼤排序算法均属于内部排序。
如果按照策略来分类，⼤致可分为：交换排序、插⼊排序、选择排序、归并排序和基数排序。
如下图所⽰：3、算法分析1.插⼊排序*直接插⼊排序*希尔排序2.选择排序*简单选择排序*堆排序3.交换排序*冒泡排序*快速排序4.归并排序5.基数排序不稳定排序：简单选择排序，快速排序，希尔排序，堆排序稳定排序：冒泡排序，直接插⼊排序，归并排序，奇数排序1、插⼊排序将第⼀个和第⼆个元素排好序，然后将第3个元素插⼊到已经排好序的元素中，依次类推（插⼊排序最好的情况就是数组已经有序了）因为插⼊排序每次只能操作⼀个元素，效率低。
元素个数N，取奇数k=N/2，将下标差值为k的数分为⼀组（⼀组元素个数看总元素个数决定），在组内构成有序序列，再取k=k/2，将下标差值为k的数分为⼀组，构成有序序列，直到k=1，然后再进⾏直接插⼊排序。
3、简单选择排序选出最⼩的数和第⼀个数交换，再在剩余的数中⼜选择最⼩的和第⼆个数交换，依次类推4、堆排序以升序排序为例，利⽤⼩根堆的性质（堆顶元素最⼩）不断输出最⼩元素，直到堆中没有元素1.构建⼩根堆2.输出堆顶元素3.将堆低元素放⼀个到堆顶，再重新构造成⼩根堆，再输出堆顶元素，以此类推5、冒泡排序改进1：如果某次冒泡不存在数据交换，则说明已经排序好了，可以直接退出排序改进2：头尾进⾏冒泡，每次把最⼤的沉底，最⼩的浮上去，两边往中间靠16、快速排序选择⼀个基准元素，⽐基准元素⼩的放基准元素的前⾯，⽐基准元素⼤的放基准元素的后⾯，这种动作叫分区，每次分区都把⼀个数列分成了两部分，每次分区都使得⼀个数字有序，然后将基准元素前⾯部分和后⾯部分继续分区，⼀直分区直到分区的区间中只有⼀个元素的时候，⼀个元素的序列肯定是有序的嘛，所以最后⼀个升序的序列就完成啦。
计算机基本算法简介：计算机基本算法是计算机科学中非常重要的一部分。
它涵盖了各种计算问题的解决方案，通过运算和逻辑推理来实现。
基本算法的设计和优化可以提高计算机程序的性能，并解决各种现实生活中的问题。
本文将介绍几种常见的计算机基本算法，包括排序算法、查找算法和图算法。
一、排序算法排序是计算机科学中最常见的问题之一，也是很多其他算法的基础。
以下是几种常见的排序算法：1. 冒泡排序冒泡排序是一种简单但效率较低的排序算法。
它通过多次迭代，每次比较相邻的两个元素并交换位置，将较大的元素逐步移动到数组的末尾，直到整个数组有序。
2. 快速排序快速排序是一种高效的排序算法。
它采用分治策略，将问题分解为子问题并递归地解决。
快速排序的关键是选择一个基准元素，将数组分为比基准元素小和大的两部分，并对这两部分分别进行排序。
3. 归并排序归并排序是一种稳定的排序算法。
它使用分治策略将问题分解为子问题，并将子问题的解合并起来。
归并排序的关键是将两个已排序的子数组合并为一个有序的数组。
二、查找算法查找是另一个常见的计算机问题，它涉及在给定数据集中寻找特定元素的过程。
以下是几种常见的查找算法：1. 顺序查找顺序查找是最简单的查找算法。
它从数据集的第一个元素开始逐一比较，直到找到目标元素或遍历完整个数据集。
2. 二分查找二分查找是一种高效的查找算法，但要求数据集必须有序。
它通过将数据集分成两部分，并根据目标元素与中间元素的大小关系确定目标元素在哪一部分，然后递归地在相应的部分查找。
3. 哈希查找哈希查找利用哈希函数将目标元素映射到一个数组中的索引，并在该索引处查找目标元素。
哈希查找的优势在于查找速度快，但要求数据集必须事先建立好哈希表。
三、图算法图算法用于解决与图相关的问题，包括最短路径、最小生成树等。
以下是几种常见的图算法：1. 深度优先搜索（DFS）深度优先搜索是一种用于图遍历的算法。
它从图的一个顶点开始，沿着路径一直向下搜索，直到无法继续为止，然后返回上一个顶点，继续搜索其他路径，直到遍历完整个图。
简单排序算法排序算法是计算机科学中最基本、最常用的算法之一。
通过对原始数据集合进行排序，可以更方便地进行搜索、统计、查找等操作。
常用的排序算法有冒泡排序、选择排序、插入排序等。
本文将介绍这些简单排序算法的具体实现及其优缺点。
一、冒泡排序（Bubble Sort）冒泡排序是一种基础的交换排序算法。
它通过不断地交换相邻的元素，从而将数据集合逐渐排序。
具体实现步骤如下：1.比较相邻的元素。
如果第一个比第二个大，就交换它们两个；2.对每一对相邻元素做同样的工作，从第一对到最后一对，这样一轮排序后，就可以确保最后一个元素是最大的元素；3.针对所有元素重复以上的步骤，除了最后一个；4.重复步骤1~3，直到排序完成。
冒泡排序的优点是实现简单、容易理解。
缺点是排序效率较低，尤其是对于较大的数据集合，时间复杂度为O(n²)。
二、选择排序（Selection Sort）选择排序是一种基础的选择排序算法。
它通过在数据集合中选择最小的元素，并将其放置到最前面的位置，然后再从剩余元素中选出最小的元素，放置到已排序部分的末尾。
具体实现步骤如下：1.在未排序序列中找到最小元素，存放到排序序列的起始位置；2.再从剩余未排序元素中继续寻找最小元素，放到排序序列末尾；3.重复步骤1~2，直到排序完成。
选择排序的优点是实现简单、固定时间复杂度O(n²)。
缺点是排序效率仍然较低，尤其是对于大数据集合，因为每次只能交换一个元素，所以相对于冒泡排序，它的移动次数固定。
三、插入排序（Insertion Sort）插入排序是一种基础的插入排序算法。
它将未排序的元素一个一个插入到已排序部分的正确位置。
具体实现步骤如下：1.从第一个元素开始，该元素可以认为已经被排序；2.取出下一个元素，在已经排序的元素序列中从后往前扫描；3.如果该元素（已排序）大于新元素，将该元素移到下一位置；4.重复步骤3，直到找到已排序的元素小于或等于新元素的位置；5.将新元素插入到该位置后；6.重复步骤2~5，直到排序完成。
数据结构的常用算法一、排序算法排序算法是数据结构中最基本、最常用的算法之一。
常见的排序算法有冒泡排序、选择排序、插入排序、快速排序、归并排序等。
1. 冒泡排序冒泡排序是一种简单的排序算法，它重复地比较相邻的两个元素，如果它们的顺序错误就将它们交换过来。
通过多次的比较和交换，最大（或最小）的元素会逐渐“浮”到数列的顶端，从而实现排序。
2. 选择排序选择排序是一种简单直观的排序算法，它每次从待排序的数据中选择最小（或最大）的元素，放到已排序序列的末尾，直到全部元素排序完毕。
3. 插入排序插入排序是一种简单直观的排序算法，它将待排序的数据分为已排序区和未排序区，每次从未排序区中取出一个元素，插入到已排序区的合适位置，直到全部元素排序完毕。
4. 快速排序快速排序是一种常用的排序算法，它采用分治的思想，通过一趟排序将待排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分小，然后再按此方法对这两部分数据进行快速排序，递归地进行，最终实现整个序列有序。
5. 归并排序归并排序是一种稳定的排序算法，它采用分治的思想，将待排序的数据分成若干个子序列，分别进行排序，然后将排好序的子序列合并成更大的有序序列，直到最终整个序列有序。
二、查找算法查找算法是在数据结构中根据给定的某个值，在数据集合中找出目标元素的算法。
常见的查找算法有线性查找、二分查找、哈希查找等。
1. 线性查找线性查找是一种简单直观的查找算法，它从数据集合的第一个元素开始，依次比较每个元素，直到找到目标元素或遍历完整个数据集合。
2. 二分查找二分查找是一种高效的查找算法，它要求数据集合必须是有序的。
通过不断地将数据集合分成两半，将目标元素与中间元素比较，从而缩小查找范围，最终找到目标元素或确定目标元素不存在。
3. 哈希查找哈希查找是一种基于哈希表的查找算法，它通过利用哈希函数将目标元素映射到哈希表中的某个位置，从而快速地找到目标元素。
三、图算法图算法是解决图结构中相关问题的算法。
【十大经典排序算法（动图演示）】必学十大经典排序算法0.1 算法分类十种常见排序算法可以分为两大类：比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。
非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。
0.2 算法复杂度0.3 相关概念稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
不稳定：如果a原本在b的前面，而a=b，排序之后a 可能会出现在b 的后面。
时间复杂度：对排序数据的总的操作次数。
反映当n变化时，操作次数呈现什么规律。
空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。
1、冒泡排序（Bubble Sort）冒泡排序是一种简单的排序算法。
它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。
走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
1.1 算法描述比较相邻的元素。
如果第一个比第二个大，就交换它们两个；对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；针对所有的元素重复以上的步骤，除了最后一个；重复步骤1~3，直到排序完成。
1.2 动图演示1.3 代码实现1.unction bubbleSort(arr) {2. varlen = arr.length;3. for(vari = 0; i arr[j+1]) {// 相邻元素两两对比6. vartemp = arr[j+1];// 元素交换7. arr[j+1] = arr[j];8. arr[j] = temp;9. }10. }11. }12. returnarr;13.}2、选择排序（Selection Sort）选择排序(Selection-sort)是一种简单直观的排序算法。
数据结构实验报告实验题目：几种基本排序算法的实现：耀班级：计嵌151学号：1513052017一、实验目的实现直接插入排序，冒泡排序，简单选择排序，快速排序，希尔排序，堆排序等6种常用部排序算法，比较各算法的比较次数和移动次数。
二、数据结构设计(1)设计待排序记录的存储结构。
(2)设计待排序数据的存储结构。
(3)输入：待排序数据的数据个数和数据可由键盘输入，也可由程序生成伪随机数，以菜单方式选择上述排序方法中的一个，并指明输出第几趟排序的结果。
(4)输出：各趟排序结果或指定趟的排序结果，以及对应的关键字比较次数和移动次数。
三、算法设计与N-S图算法设计：编写一个主函数main()，在主函数中设计一个简单的菜单，分别调用6种部排序算法。
为了对各种排序算法的性能进行比较，算法中的主要工作是在已知算法的适当位置插入对关键字的比较次数和移动次数的计数操作。
为此，可设立一个实现排序算法中的关键字比较的函数；设立一个实现排序算法中的关键字移动的函数；设立一个实现排序算法中的关键字交换的函数，从而解决比较次数和移动次数的统计问题。
数据的输入也可以通过菜单选择输入方式：键盘输入或由伪随机数程序生成数据，以便随时更换排序数据，并按照不同要求对排序数据进行排序，输出排序的结果以及对应的关键字比较次数和移动次数。
对于测试数据，算法中可以考虑几组数据的典型性，如正序，逆序和不同程度等，以取得直观的感受，从而对不同算法进行比较。
四、程序清单#include<iostream>using namespace std;void showMenu(){cout << " * 菜单* " << endl;cout << " 1.直接插入排序" << endl;cout << " 2.冒泡排序" << endl;cout << " 3.简单选择排序" << endl;cout << " 4.快速排序" << endl;cout << " 5.希尔排序" << endl;cout << " 6.堆排序" << endl;cout << " 7.退出程序" << endl;}struct SqList{int * key;int length;};void CreateSqList(SqList &sl)//type为int{int n;cout << "建立顺序表" << endl << "请输入顺序表的长度" << endl;cin >> n;sl.length = n;sl.key = new int[sl.length + 1];cout << "请输入数据：" << endl;for (int i = 1; i <= sl.length; i++){cin >> sl.key[i];}}void Copy(SqList &L1,SqList &L2){L2.length = L1.length;L2.key = new int[L1.length + 1];for (int i = 1; i <=L1.length; i++){L2.key[i] = L1.key[i];}}void OutPut(SqList &L){for (int j = 1; j <= L.length; ++j)cout << L.key[j] << "\t";cout << endl;}void InsertSort(SqList & L){//对顺序表L作直接插入排序int k = 0;int compare_Time, move_Time;compare_Time = move_Time = 0;for (int i = 2; i <= L.length; i++){if (L.key[i] <= L.key[i - 1])//"<"需将L.key[i]插入有序子表{L.key[0] = L.key[i];//复制为哨兵L.key[i] = L.key[i - 1];int j;for (j = i - 2; L.key[0] <= L.key[j]; --j){compare_Time++;L.key[j + 1] = L.key[j];//记录后移move_Time++;}L.key[j + 1] = L.key[0];//插入到正确位置k++;cout << "第" << k << "趟排序结果："; OutPut(L);}compare_Time++;}cout << "比较次数为：" << compare_Time << endl;cout << "移动次数为：" << move_Time << endl;}void BubbleSort(SqList & L){int k = 0;int compare_Time, move_Time;compare_Time = move_Time = 0;for (int i = 1; i<L.length; i++)//用i控制比较趟数共n-1趟{int t;for (int j = 1; j <= L.length - i; j++){compare_Time++;if (L.key[j]>L.key[j + 1]){t = L.key[j];L.key[j] = L.key[j + 1];L.key[j + 1] = t;move_Time++;}}k++;cout << "第" << k << "趟排序结果："; OutPut(L);}cout << "比较次数为：" << compare_Time << endl;cout << "移动次数为：" << move_Time << endl;}int SelectMinKey(SqList& L, int n, int &compare_Time){int min = n;int minkey;//最小值minkey = L.key[n];for (int i = n + 1; i <= L.length; i++){if (L.key[i]<minkey){minkey = L.key[i];min = i;}compare_Time++;}return min;}void SelectSort(SqList & L){//对顺序表L作简单选择排序int j;int t;int k = 0;int move_Time = 0, compare_Time = 0;for (int i = 1; i <= L.length; i++){j = SelectMinKey(L, i, compare_Time);//在L.key[i]--L.key[L.length]中选择最小的记录并将其地址赋给jif (i != j)//交换记录{t = L.key[i];L.key[i] = L.key[j];L.key[j] = t;move_Time++;}compare_Time++;k++;cout << "第" << k << "趟排序结果："; OutPut(L);}cout << "比较次数为：" << compare_Time << endl;cout << "移动次数为：" << move_Time << endl;}int Partition(SqList& L, int low, int high,int &compare_Time,int &move_Time){//交换顺序表L中子表key[low]--key[high]中的记录，枢轴记录到位，并返回其所在位置，//此时在它之前（后）的记录均不大（小）于它int pivotkey;L.key[0] = L.key[low];//用子表的第一个记录作枢轴记录pivotkey = L.key[low];//关键字while (low<high)//从表的两端交替向中间扫描{compare_Time++;while (low<high&&L.key[high] >= pivotkey) --high;L.key[low] = L.key[high];move_Time++;//将比枢轴小的记录移至低端while (low<high&&L.key[low] <= pivotkey) ++low;L.key[high] = L.key[low];//将比枢轴大的记录移至高端move_Time++;}L.key[low] = L.key[0];//枢轴记录到位return low;//返回枢轴位置}void QSort(SqList& L, int low, int high,int &k,int &compare_Time,int &move_Time) {int mid;//接收枢轴位置if (low<high){mid = Partition(L, low, high,compare_Time,move_Time);k++;cout << "第" << k << "趟排序结果："; OutPut(L);QSort(L, low, mid - 1,k,compare_Time,move_Time);//对低子表进行排序QSort(L, mid + 1, high, k, compare_Time, move_Time);//对高子表进行排序}}void QuitSort(SqList & L)//对顺序表进行快速排序{int k = 0;int compare_Time = 0, move_Time = 0;QSort(L, 1, L.length,k,compare_Time,move_Time);cout << "比较次数为：" << compare_Time << endl;cout << "移动次数为：" << move_Time << endl;}void ShellInsert(SqList &L, int dk, int &compare_Time, int &move_Time){//对顺序表进行一趟希尔插入排序for (int i = dk + 1; i <= L.length; i++)if (L.key[i] <= L.key[i - dk]){compare_Time++;L.key[0] = L.key[i];int j;for (j = i - dk; j > 0 && L.key[0] <= L.key[j]; j -= dk){compare_Time++;L.key[j + dk] = L.key[j];move_Time++;}L.key[j + dk] = L.key[0];}}void ShellSort(SqList &L, int dlta[], int t){int compare_Time = 0, move_Time = 0;//按增量序列dl[0]--dl[t-1]对顺序表L作哈希排序for (int k = 0; k < t; k++){ShellInsert(L, dlta[k], compare_Time, move_Time);cout << "第" << k+1 << "趟排序结果："; OutPut(L);}cout << "比较次数为：" << compare_Time << endl;cout << "移动次数为：" << move_Time << endl;}void HeapAdjust(SqList& L, int s, int m, int &compare_Time, int &move_Time){//对顺序表做查找，从值最大的孩子结点向下筛选，找到最大值int rc = L.key[s];for (int j = 2 * s; j <= m; j *= 2){if (j<m&&L.key[j] <= L.key[j + 1])//找到值相对较大的孩子结点，并依次向下筛选{j++;}compare_Time++;if (rc>L.key[j]) break;//如果rc最大则推出while循环L.key[s] = L.key[j];//最大值赋值s = j;//交换位置move_Time++;}L.key[s] = rc;}void HeapSort(SqList & L){//对顺序表L进行堆排序int value,i;int k = 0;int compare_Time = 0, move_Time = 0;for (i = L.length / 2; i>0; i--)//把L.key[1...L.length]调整为大顶堆HeapAdjust(L, i, L.length, compare_Time, move_Time);for (i = L.length; i>1; --i){value = L.key[1];L.key[1] = L.key[i];L.key[i] = value;HeapAdjust(L, 1, i - 1, compare_Time, move_Time);//将L.key[1...i-1]重新调整为大顶堆k++;cout << "第" << k << "趟排序结果："; OutPut(L);}cout << "比较次数为：" << compare_Time << endl;cout << "移动次数为：" << move_Time << endl;}int main(){int choice;SqList sq,sp;CreateSqList(sq);Copy(sq, sp);showMenu();cout << "Please enter your choice: ";cin >> choice;while (choice != 0){switch (choice){case 1:InsertSort(sq); cout << "最终结果：";OutPut(sq); break;case 2:BubbleSort(sq); cout << "最终结果：";OutPut(sq); break;case 3:SelectSort(sq); cout << "最终结果：";OutPut(sq); break;case 4:QuitSort(sq); cout << "最终结果：";OutPut(sq); break;case 5:int *p, n;cout << "请输入增量个数：" << endl;cin >> n;p = new int[n];cout << "请输入各个增量的值：" << endl;for (int i = 0; i < n; i++){cin >> p[i];}ShellSort(sq, p, n); cout << "最终结果：";OutPut(sq); break;case 6:HeapSort(sq); cout << "最终结果：";OutPut(sq); break;case 7:cout << "程序运行结束，退出程序。
