#include #include #include #include
当前位置：文档之家 › 十六种经典排序算法

十六种经典排序算法

  • 格式：docx
  • 大小：23.52 KB
  • 文档页数：15

下载文档原格式

  / 15

合集下载

数据结构最基础的十大算法

数据结构最基础的十大算法

数据结构最基础的十大算法数据结构是计算机科学中的重要分支，它研究如何组织和存储数据以便于访问和修改。

在数据结构中，算法是解决问题的关键。

下面将介绍数据结构中最基础的十大算法。

1. 线性搜索算法线性搜索算法是最简单的算法之一，它的作用是在一个列表中查找一个特定的元素。

该算法的时间复杂度为O(n)，其中n是列表中元素的数量。

2. 二分搜索算法二分搜索算法是一种更高效的搜索算法，它的时间复杂度为O(log n)。

该算法要求列表必须是有序的，它通过将列表分成两半来查找元素，直到找到目标元素为止。

3. 冒泡排序算法冒泡排序算法是一种简单的排序算法，它的时间复杂度为O(n^2)。

该算法通过比较相邻的元素并交换它们的位置来排序列表。

4. 快速排序算法快速排序算法是一种更高效的排序算法，它的时间复杂度为O(nlog n)。

该算法通过选择一个基准元素并将列表分成两部分来排序列表。

5. 插入排序算法插入排序算法是一种简单的排序算法，它的时间复杂度为O(n^2)。

该算法通过将每个元素插入到已排序的列表中来排序列表。

6. 选择排序算法选择排序算法是一种简单的排序算法，它的时间复杂度为O(n^2)。

该算法通过选择最小的元素并将其放在列表的开头来排序列表。

7. 堆排序算法堆排序算法是一种更高效的排序算法，它的时间复杂度为O(n log n)。

该算法通过将列表转换为堆并进行排序来排序列表。

8. 归并排序算法归并排序算法是一种更高效的排序算法，它的时间复杂度为O(n log n)。

该算法通过将列表分成两部分并将它们合并来排序列表。

9. 哈希表算法哈希表算法是一种高效的数据结构，它的时间复杂度为O(1)。

该算法通过将键映射到哈希表中的位置来存储和访问值。

10. 树算法树算法是一种重要的数据结构，它的时间复杂度取决于树的深度。

树算法包括二叉树、AVL树、红黑树等。

以上是数据结构中最基础的十大算法，它们在计算机科学中有着广泛的应用。

八大排序算法

八大排序算法

八大排序算法排序有内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。

我们这里说说八大排序就是内部排序。

基本思想:将一个记录插入到已排序好的有序表中，从而得到一个新，记录数增1的有序表。

即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。

要点：设立哨兵，作为临时存储和判断数组边界之用。

直接插入排序示例：如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。

所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。

算法的实现：1.void print(int a[], int n ,int i){2. cout<<i <<":";3.for(int j= 0; j<8; j++){4. cout<<a[j] <<" ";5. }6. cout<<endl;7.}8.9.10.void InsertSort(int a[], int n)11.{12.for(int i= 1; i<n; i++){13.if(a[i] < a[i-1]){ //若第i个元素大于i-1元素，直接插入。

小于的话，移动有序表后插入14.int j= i-1;15.int x = a[i]; //复制为哨兵，即存储待排序元素16. a[i] = a[i-1]; //先后移一个元素17.while(x < a[j]){ //查找在有序表的插入位置18. a[j+1] = a[j];19. j--; //元素后移20. }21. a[j+1] = x; //插入到正确位置22. }23. print(a,n,i); //打印每趟排序的结果24. }25.26.}27.28.int main(){29.int a[8] = {3,1,5,7,2,4,9,6};30. InsertSort(a,8);31. print(a,8,8);32.}效率：时间复杂度：O（n^2）.其他的插入排序有二分插入排序，2-路插入排序。

C语言八大排序算法

C语言八大排序算法

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. 图算法：图算法用于处理图数据结构相关的问题，常用的图算法包括深度优先（DFS）、广度优先（BFS）、最小生成树算法（Prim和Kruskal算法）、最短路径算法（Dijkstra算法和Floyd-Warshall算法）等。

4.动态规划：动态规划是一种解决最优化问题的方法，常用于求解最长公共子序列、背包问题等。

动态规划通过将问题分解为子问题，并保存子问题的解，以便在需要时重复利用，从而降低问题的复杂度。

5.贪心算法：贪心算法是一种通过局部最优选择来得到全局最优解的方法，常用于求解最小生成树问题、哈夫曼编码等。

贪心算法每次选择最优的局部解，然后继续下一步，直到得到全局最优解。

6.回溯算法：回溯算法用于求解排列、组合、子集等问题。

回溯算法通过尝试不同的选择，并回溯到上一步，直到找到解。

7. 字符串匹配算法：字符串匹配是一项常见的操作，常用的字符串匹配算法包括暴力匹配、KMP算法、Boyer-Moore算法等。

这些算法用于在一个字符串中寻找另一个字符串，并返回匹配的位置或结果。

8. 最大流算法：最大流算法用于解决网络流问题，常用的最大流算法包括Ford-Fulkerson算法、Edmonds-Karp算法、Dinic算法等。

9. 最小割算法：最小割算法用于分割网络中的最小割，常用的最小割算法包括Ford-Fulkerson算法、Karger算法等。

10.基本数据结构：编程中常用的基本数据结构包括数组、链表、栈、队列、树、图等，对这些数据结构的操作和算法是编程中的基础。

以上只是一些常见的编程算法，实际上还有许多其他的算法，如最长递增子序列、快速幂、拓扑排序等。

cgh常用算法

cgh常用算法

cgh常用算法常用的算法有很多，可以分为查找算法、排序算法、图算法、动态规划算法等等。

下面我将详细介绍一些常用的算法及其应用。

一、查找算法：1.线性查找：从头至尾逐个比较，找到目标元素则返回其位置，否则返回-1。

常用于无序数组或链表中的查找。

2.二分查找：将有序数组以二分的方式不断缩小范围，找到目标元素则返回其位置，否则返回-1。

时间复杂度为O(logN)，常用于有序数组或链表中的查找。

二、排序算法：1.冒泡排序：从头至尾不断比较相邻两个元素，如果顺序错误则交换，最大（最小）元素逐渐沉底，直到排序完成。

时间复杂度为O(N^2)。

2.插入排序：将数组分为已排序和未排序两部分，依次将未排序部分中的元素插入已排序部分的合适位置。

时间复杂度为O(N^2)，但对于小规模数据较为高效。

3.选择排序：将数组分为已排序和未排序两部分，每次从未排序部分中选择最小（最大）的元素插入已排序部分的末尾。

时间复杂度为O(N^2)，与数据状况无关。

4.快速排序：通过分治的思想，选择一个元素作为基准，将数组划分为比基准小和比基准大的两部分，然后对两个部分递归排序。

时间复杂度为O(NlogN)，是一种高效的排序算法。

5.归并排序：通过分治的思想，将数组分成两个子数组，分别对两个子数组进行排序，然后将排序好的子数组合并成一个有序数组。

时间复杂度为O(NlogN)，稳定且效率高。

三、图算法：1.深度优先搜索（DFS）：从起点开始，沿着一条路径遍历完当前路径，再回溯到前一个节点继续遍历其他路径，直到遍历完整个图。

常用于求解连通分量、拓扑排序等问题。

2.广度优先搜索（BFS）：从起点开始，先遍历其所有相邻节点，再依次遍历下一层的节点，直到遍历完整个图。

常用于求解最短路径、连通性等问题。

3.最小生成树算法：Prim算法和Kruskal算法用于求解带权无向图的最小生成树，分别基于贪心和并查集思想。

4.最短路径算法：Dijkstra算法和Bellman-Ford算法用于求解带权有向图的单源最短路径，分别基于贪心和动态规划思想。

计算机领域常用算法列表

计算机领域常用算法列表

计算机领域常用算法列表在计算机科学领域，算法是解决问题的基础工具。

各种算法的应用领域广泛，包括数据处理、搜索、排序、图形处理、机器学习等。

本文将介绍计算机领域常用的一些算法，以帮助读者了解和熟悉这些算法的基本原理和应用。

一、搜索算法1. 顺序搜索算法顺序搜索算法是最简单的搜索算法之一，其基本思想是按顺序逐个比较目标元素和列表中的元素，直到找到匹配项或搜索完整个列表。

顺序搜索算法适用于未排序的列表。

2. 二分搜索算法二分搜索算法也称为折半搜索算法，适用于已排序的列表。

其基本思想是将列表从中间切分，然后将目标元素与中间元素进行比较，根据比较结果缩小搜索范围，以达到快速搜索的目的。

3. 广度优先搜索算法广度优先搜索算法是一种图遍历算法，用于搜索图或树的结构。

它从起始节点开始，按照广度优先的方式依次访问与当前节点相邻的节点，直到找到目标节点或访问完整个图。

二、排序算法1. 冒泡排序算法冒泡排序算法是一种简单且常用的排序算法。

它通过不断比较相邻的元素并交换位置，将最大或最小的元素逐步“冒泡”到正确的位置，直到整个列表有序。

2. 快速排序算法快速排序算法是一种高效的排序算法。

它通过选择一个基准元素，将列表划分为两个子列表，其中一个子列表的元素都小于基准元素，另一个子列表的元素都大于基准元素。

然后对子列表递归地应用快速排序算法，最终得到有序列表。

3. 归并排序算法归并排序算法是一种稳定的排序算法。

它将列表划分为多个子列表，然后逐个合并子列表，直到得到完全排序的列表。

归并排序算法的核心思想是分治法，将大问题拆分为小问题并解决。

三、图算法1. 最短路径算法最短路径算法用于求解两个节点之间的最短路径。

著名的最短路径算法有迪杰斯特拉算法和弗洛伊德算法。

迪杰斯特拉算法适用于单源最短路径问题，而弗洛伊德算法适用于所有节点对之间的最短路径问题。

2. 最小生成树算法最小生成树算法用于求解连通图的最小生成树。

其中，普里姆算法和克鲁斯卡尔算法是两种常用的最小生成树算法。

五种常见的排序方法

五种常见的排序方法在计算机科学中，排序是一种非常重要的操作，它可以将一组数据按照一定的顺序排列。

排序算法是计算机科学中最基本的算法之一，它的应用范围非常广泛，例如数据库查询、数据压缩、图像处理等。

本文将介绍五种常见的排序算法，包括冒泡排序、选择排序、插入排序、快速排序和归并排序。

一、冒泡排序冒泡排序是一种简单的排序算法，它的基本思想是将相邻的元素两两比较，如果前面的元素大于后面的元素，则交换它们的位置，一遍下来可以将最大的元素放在最后面。

重复这个过程，每次都可以确定一个最大的元素，直到所有的元素都排好序为止。

冒泡排序的时间复杂度为O(n^2)，空间复杂度为O(1)。

二、选择排序选择排序是一种简单的排序算法，它的基本思想是每次从未排序的元素中选择最小的元素，将它放到已排序的元素的末尾。

重复这个过程，直到所有的元素都排好序为止。

选择排序的时间复杂度为O(n^2)，空间复杂度为O(1)。

三、插入排序插入排序是一种简单的排序算法，它的基本思想是将一个元素插入到已排序的元素中，使得插入后的序列仍然有序。

重复这个过程，直到所有的元素都排好序为止。

插入排序的时间复杂度为O(n^2)，空间复杂度为O(1)。

四、快速排序快速排序是一种高效的排序算法，它的基本思想是选择一个基准元素，将序列分成两个子序列，其中一个子序列的所有元素都小于基准元素，另一个子序列的所有元素都大于基准元素。

然后递归地对这两个子序列进行排序。

快速排序的时间复杂度为O(nlogn)，空间复杂度为O(logn)。

五、归并排序归并排序是一种高效的排序算法，它的基本思想是将序列分成两个子序列，然后递归地对这两个子序列进行排序，最后将这两个有序的子序列合并成一个有序的序列。

归并排序的时间复杂度为O(nlogn)，空间复杂度为O(n)。

总结在实际的应用中，选择合适的排序算法非常重要，不同的排序算法有不同的优劣势。

冒泡排序、选择排序和插入排序是三种简单的排序算法，它们的时间复杂度都为O(n^2)，在处理小规模的数据时比较适用。

Python的十种常见算法

Python的⼗种常见算法⼗种排序算法1. 常见算法分类⼗种常见排序算法⼀般分为以下⼏种：（1）⾮线性时间⽐较类排序：a. 交换类排序（快速排序、冒泡排序）b. 插⼊类排序（简单插⼊排序、希尔排序）c. 选择类排序（简单选择排序、堆排序）d. 归并排序（⼆路归并排序、多路归并排序）（2）线性时间⾮⽐较类排序：a. 技术排序b. 基数排序c. 桶排序总结：（1）在⽐较类排序种，归并排序号称最快，其次是快速排序和堆排序，两者不相伯仲，但是有⼀点需要注意，数据初始排序状态对堆排序不会产⽣太⼤的影响，⽽快速排序却恰恰相反。

（2）线性时间⾮⽐较类排序⼀般要优于⾮线性时间⽐较类排序，但前者对待排序元素的要求较为严格，⽐如计数排序要求待待排序数的最⼤值不能太⼤，桶排序要求元素按照hash分桶后桶内元素的数量要均匀。

线性时间⾮⽐计较类排序的典型特点是以空间换时间。

2. 算法描述于实现2.1 交换类排序交换类排序的基本⽅法是：两两⽐较待排序记录的排序码，交换不满⾜顺序要求的偶对，直到全部满⾜位置。

常见的冒泡排序和快速排序就属于交换类排序。

2.1.1 冒泡排序算法思想：从数组中第⼀个数开始，依次便利数据组中的每⼀个数，通过相邻⽐较交换，每⼀轮循环下来找出剩余未排序数终端最⼤数并“冒泡”⾄数列的顶端。

算法步骤：（1）从数组中第⼀个数开始，依次与下⼀个数⽐较并次交换⽐⾃⼰⼩的数，直到最后⼀个数。

如果发⽣交换，则继续下⾯的步骤，如果未发⽣交换，则数组有序，排序结束，此时时间复杂度未O(n)；（2）每⼀轮“冒泡”结束后，最⼤的数将出现在乱序数列的最后⼀位。

重复步骤1。

稳定性：稳定排序。

时间复杂度：O(n)⾄O(n2)，平均时间复杂度为O(n2)。

最好的情况：如果待排序数据列为正序，则⼀趟排序就可完成排序，排序码的⽐较次数为(n-1)次，且没有移动，时间复杂度为O(n)。

最坏的情况：如果待排序数据序列为逆序，则冒泡排序需要(n-1)趟起泡，每趟进⾏（n-i）次排序码的⽐较和移动，即⽐较和移动次数均达到最⼤值：⽐较次数：Cmax=∑i=1n−1(n−i)=n(n−1)/2=O(n^2)移动次数等于⽐较次数，因此最坏时间复杂度为O(n^2)实例代码：# 冒泡排序def bubble_sort(nums):for i in range(len(nums)-1): # 这个循环负责冒泡排序进⾏的次数for j in range(len(nums)-i-1): # j为列表下标if nums[j] > nums[j+1]:nums[j], nums[j+1] = nums[j+1], nums[j]return numsprint(bubble_sort([45, 32, 8, 33, 12, 22, 19, 97]))# 输出：[8, 12, 19, 22, 32, 33, 45, 97]2.1.2 快速排序冒泡排序是在相邻的两个记录进⾏⽐较和交换，每次交换只能上移或下移⼀个位置，导致总的⽐较与移动次数较多。

全排列算法解析(完整版)

由于本文的，内容比较多，所以希望读者根据自己的要求阅读，不要一次性读完，有些章节 可以分开读。第 1 节到第 5 节提供了全排列的概念和一个初始的算法。第 6 节到第 8 节主要 讲述了字典序的全排列算法。第 9 到第 10 节讲了有关字典序中中介数的概念。第 11 到第 12 节主要介绍了不同的中介数方法，仅供扩展用。第 13 节到 15 节介绍了邻位对换法的全 排的有关知识。16 节讲了有关邻位对换法的中介数，仅供参考。第 17 节讲了组合数生成的 算法。 1.全排列的定义和公式： 从 n 个数中选取 m（m<=n）个数按照一定的顺序进行排成一个列，叫作从 n 个元素中取 m 个元素的一个排列。由排列的定义，显然不同的顺序是一个不同的排列。从 n 个元素中取 m 个元素的所有排列的个数，称为排列数。从 n 个元素取出 n 个元素的一个排列，称为一个全 排列。全排列的排列数公式为 n!，通过乘法原理可以得到。 2.时间复杂度： n 个数（字符、对象）的全排列一共有 n!种，所以全排列算法至少时 O(n!)的。如果要对全 排列进行输出，那么输出的时间要 O(n*n!)，因为每一个排列都有 n 个数据。所以实际上， 全排列算法对大型的数据是无法处理的，而一般情况下也不会要求我们去遍历一个大型数据 的全排列。 3.列出全排列的初始思想：
void Permutation(int A[], int m, int n) {
int i, int temp; if(m = = n)
{ for(i = 0;i<n;i++) { if(i != n-1) printf("%d ",A[i]); //有加空格 else printf("%d" A[i]); //没加空格 } //直接输出，因为前 n-1 个数已经确定，递归到只有 1 个数。 printf("\n"); return;

C语言常用简单算法

C语言常用简单算法C语言是一种广泛应用的编程语言，支持各种算法的实现。

以下是一些常用的简单算法，涵盖了排序、查找、递归等方面。

1. 冒泡排序（Bubble Sort）：通过不断比较相邻元素的大小，将较大的元素逐步“冒泡”到数组的末尾。

2. 选择排序（Selection Sort）：每次从未排序的数组中选择最小（或最大）的元素，放到已排序数组的末尾。

3. 插入排序（Insertion Sort）：将数组分为已排序和未排序两个部分，每次将未排序部分中的元素插入到已排序部分的正确位置。

4. 快速排序（Quick Sort）：选择一个基准元素，将数组分成两部分，将小于基准的元素放在左边，大于基准的元素放在右边，然后递归地对两部分进行排序。

5. 归并排序（Merge Sort）：将待排序数组递归地分成两部分，分别进行排序，然后再将两个有序的数组合并成一个有序的数组。

6. 二分查找（Binary Search）：对于有序数组，通过比较中间元素和目标值的大小，缩小查找范围，直到找到目标值或查找范围为空。

7. 线性查找（Linear Search）：对于无序数组，逐个比较数组中的元素和目标值，直到找到目标值或遍历完整个数组。

8. 求阶乘（Factorial）：使用递归方式或循环方式计算给定数字的阶乘。

9. 斐波那契数列（Fibonacci Sequence）：使用递归方式或循环方式生成斐波那契数列。

10. 汉诺塔（Tower of Hanoi）：使用递归方式实现汉诺塔问题的解决，将一组盘子从一个柱子移动到另一个柱子。

11. 判断回文数（Palindrome）：判断给定数字是否为回文数，即正序和倒序相同。

12.求最大公约数（GCD）：使用辗转相除法或欧几里德算法求两个数的最大公约数。

13.求最小公倍数（LCM）：通过最大公约数求得最小公倍数。

14. 求质数（Prime Number）：判断给定数是否为质数，即只能被1和自身整除。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

//头文件定义 #include "stdafx.h" #include #include #include #include #include

void bubbleSort(int *a,int len);//冒泡算法 void UpdBubbleSort1(int *a,int len);//改进冒泡算法1 ----找到一次循环的已排好序位置 void UpdbubbleSort2(int *a,int len); //改进冒泡算法2 --一次循环找到最大\最小值

void quickSort_update(int *a, int len, int k); //改进快速排序--先使>8的块基本有序--实测比一般快速排序节约28%时间(59秒,1亿条随机数据，逆序数时间较长) void qsort_improve(int *a,int low,int high, int k);//改进快速排序子算法

void InsertSort(int *a, int n); //直接插入排序 void shellSort(int *a, int n);//直接插入排序威力加强版本--希尔排序(适用逆序数，1亿逆序数据93s 1亿随机数据223s) void ShellSort_local(int *a, int len, int dk);

void HeapSort(int *H,int length); //堆排序-step1:建堆 2：n/2个父节点堆有序 3、从堆尾元素依次和堆顶交换 void BuildingHeap(int *H, int length); //堆排序---子函数 (逆序数据50s,1亿条随机数据133秒) void HeapAdjust(int *H,int s, int length); //堆排序---子函数

unsigned long ulrand(void);//产生大的随机数

void selectSort(int *a, int n); //选择排序 int SelectMinKey(int *a, int n, int i); void SelectSort_double(int *r,int n);

typedef int ElemType ; void MergeSort(ElemType *r, ElemType *rf, int lenght);//归并排序(1亿逆序：30s 1亿随机：46s ) void Merge(ElemType *r,ElemType *rf, int i, int m, int n); //65148-65149 /* 总结提升算法效率方法

1、减小循环次数，大循环在里面，小循环再外面-----循环次数多的话切换用时多， 2、侦测已完成任务，提前结束 3、递归算法占用的空间较大，容易溢出, 优点是算法复杂度低

*/ void QuickSort(int *a,int low,int high); //(全完逆序100w数据40分钟---已验证) int LocalQuickSort(int *a,int low,int high); void Swap(int *p1,int *p2);

void PrintArray(int *a,int len); void InitArray(int *a,int len);

int first_posi=0; int privotKey=0;

int SortOkSign=0;//无 //需交换的标志 #define lenArr 100000000

int lastChangePos=lenArr-1;//最后一次交换的位置 int gloData=0; int k=0,m=0,n=0,x=0;

int *p= (int *) malloc(lenArr*sizeof(int)); int b[lenArr];

int main() { //int len=5; if(p==NULL) { printf("malloc Error"); return 0; } clock_t start_2,end_2; // InitArray(p,lenArr); // start_1=clock(); //开始时间start_1,end_1,

// InsertSort(p,lenArr); // UpdbubbleSort2(p,lenArr); // QuickSort(p,0,lenArr-1); //PrintArray(p,lenArr); // quickSort_update(p,lenArr-1,10); //InsertSort(p,lenArr); // HeapSort(p,lenArr); // MergeSort(p,b,lenArr); // end_1=clock(); //结束时间

InitArray(p,lenArr); // PrintArray(p,lenArr);

start_2=clock(); //结束时间 // shellSort(p,lenArr); // bubbleSort(p,lenArr);

HeapSort(p,lenArr); end_2=clock(); // PrintArray(p,lenArr); double db2=(double)(end_2-start_2)/CLOCKS_PER_SEC; printf("\n排序时间%lf",db2); return 0; }

//改进冒泡算法 ---检测已排序好的尾部段，不再排序 void UpdBubbleSort1(int *a,int len) { int tempInt=0; for(int j=len;j>0;j--) { int min_posi=(j-1)for(int i=0;i{ if(a[i]>a[i+1]) { tempInt=a[i]; a[i]=a[i+1]; a[i+1]=tempInt; SortOkSign=1; lastChangePos=i+1; } } if(0==SortOkSign) { break; }

}

}

//将r[i…m]和r[m +1 …n]归并到辅助数组rf[i…n] void Merge(ElemType *r,ElemType *rf, int i, int m, int n) { int j,k; for(j=m+1,k=i; i<=m && j <=n ; ++k) { if(r[j] < r[i]) rf[k] = r[j++]; else rf[k] = r[i++]; } while(i <= m) rf[k++] = r[i++]; while(j <= n) rf[k++] = r[j++]; } void MergeSort(ElemType *r, ElemType *rf, int lenght) {

for(int g=0;grf[g]=r[g];

int len = 1; ElemType *q = r; // ElemType *tmp ; while(len < lenght) { int s = len; len = 2 * s ; int i = 0; while(i+ len <=lenght) { Merge(q, rf, i, i+ s-1, i+ len-1 ); //对等长的两个子表合并 i = i+ len; } if(i + s-1<=lenght-1) { Merge(q, rf, i, i+ s -1, lenght -1); //对不等长的两个子表合并 }

// tmp = q; q = rf; rf = tmp; //交换q,rf，以保证下一趟归并时，仍从q 归并到rf

for(int g=0;gq[g]=rf[g];

} rf=q; }

void HeapSort(int *H,int length) //堆排序- { //初始堆 BuildingHeap(H, length); //从最后一个元素开始对序列进行调整 for (int i = length-1; i > 0; --i) { //交换堆顶元素H[0]和堆中最后一个元素 int temp = H[i]; H[i] = H[0]; H[0] = temp; //每次交换堆顶元素和堆中最后一个元素之后，都要对堆进行调整 HeapAdjust(H,0,i);

//printf("\n第%d次排序结果:",length-i); // PrintArray(p,lenArr); } }

void BuildingHeap(int *H, int length) //堆排序----子函数 { //最后一个有孩子的节点的位置 i= (length -1) / 2 for (int i = (length -1) / 2 ; i >= 0; --i) HeapAdjust(H,i,length); }

void HeapAdjust(int *H,int s, int length) //堆排序---子函数 { int tmp = H[s]; int child = 2*s+1; //左孩子结点的位置。(i+1 为当前调整结点的右孩子结点的位置) while (child < length) { if(child+1 调整结点大的孩子结点) ++child ; } if(H[s]H[s] = H[child]; // 那么把较大的子结点往上移动，替换它的父结点 s = child; // 重新设置s ,即待调整的下一个结点的位置 child = 2*s+1; } else { // 如果当前待调整结点大于它的左右孩子，则不需要调整，直接退出 break; } H[s] = tmp; // 当前待调整的结点放到比其大的孩子结点位置上 }

}