给数组排序的三种简单算法:冒泡排序法,选择排序法,插入排序法。
用升序的例子来说明一下各算法的原理吧:
冒泡排序算法是先把数组的第1个元素与第2个元素比较,如果第1个大于第2个,则交换两者的位置,反之则不交换;接着比较第2个元素与第3个元素……这样比较、交换一遍后,数组当中最大的元素已经排到了最后;接下来从第1个元素开始,循环前面的操作,循环的次数比元素的个数少1,每次循环时比较大小的次数比上一次循环次数少1。这样每次循环的结果都是把大的元素排到最后,看起来像烧开水冒水泡,故名“冒泡排序算法”。
设数组元素个数为n,冒泡排序法第1次循环需要比较n-1次,第2次循环需要比较n-2次,第n次循环需要比较1次。每次的循环比较的次数可以写成这样一个序列:n-1,n-2,n-3……1,总共的比较次数为((n-1)+1)(n-1)/2,即n(n-1)/2。这里n(n-1)可以看成n^2(n值越大,n^2与n(n-1)的差别就越可以忽略不计),即n^2/2。用大O表示法表示算法效率为O(N^2)。交换次数在最理想情况下为0,在最糟糕的情况下每次比较都需要交换。所以第1次循环时交换的次数平均为(n-1)/2,第2次为(n-2)/2,最后可得出总交换次数为((n-1)/2+1/2)(n-1)/2,即n(n-1)/4,同理可用大O表示法表示算法效率为O(N^2)。
插入排序算法需要用到一个“指针”(一个用来标记最小值下标的临时变量)。其原理是先把“指针”指向第1个元素,即0。接着拿“指针”指着的元素和每一个元素作比较,如果被比较的元素小于“指针”指着的元素,就把“指针”指向被比较的元素,这样比较完一次,指针指着的元素就是最小的元素,然后把它与第一个元素交换位置。接着把“指针”指向第2个元素,开始循环刚才的操作。设元素个数为n,循环需要n-1次。插入排序过程中,比较大小的次数为((n-1)+1)(n-1)/2,即n(n-1)/2,用大O表示法表示算法效率为O(N^2)。理想情况下数据交换次数为0,在最糟糕的情况下每循环一次就交换一次数据(虽然最糟糕情况下每次比较都会把临时变量重新赋值一次,但相对于冒泡法每次的交换操作来说,赋值操作耗的资源少。交换操作至少等于3次赋值操作外加3次计算--个人理解)。所以平均交换次数为(n-1)/2,用大O表示法表示算法效率为O(N)。由此看来,选择排序法比冒泡排序法要快。但在数据量少的情况下效果不是很明显。
插入排序法是先把数组的第1个元素当作一个有序数组,再拿非有序数组的第1个元素(即整个数组的第2个元素)(暂且称它为参考元素吧)与之前的有序数组依次比较(当然第1次比较时,有序数组元素只有一个,所以只需要比较一次),如果第2个元素比第1个元素大,则跳出本次循环;反之,则将第1个元素向后移一个位置,覆盖掉第2个元素,然后把参考元素的值赋给第1个元素。接着开始第2次比较,这时有序数组中已经有两个元素了,所以拿第3个元素作参数元素,将它与前面的有序数组中的元素依次比较,如果参数元素比前面的元素大,这时因为参考元素不可能比有序数组中的其它元素小了,所以跳出本次循环;反之,则将这个比参考元素小的元素往后移动一个位置,直到有序数组中与参考元素比较的元素比参考小,这时把参考元素的值赋给较小的那个元素所在的下一个位置,这样循环。设元素个数为n,则循环次数为n-1。最理想情况下每次循环的比较次数为1;最糟糕的情况下第一次循环的比较次数为1,第2次为2,第n-1次为n-1,总次数为(1+(n-1))(n-1)/2,即n(n-1)/2。所以平均比较次数为((n-1)+n(n-1)/2)/2,即(n^2+n-2)/2,相对n^2来说,n-2可以忽略,得大O表示法:O(N^2)。理想情况下交换次数为0,最糟糕情况下,交换次数为n-1(虽然最糟糕情况下每次比较都会移动数组中的元素,而这移动操作其实就是给数组中元素重新赋值的操作,同选择排序法一样,相对于冒泡法每次的交换操作来说,赋值操作耗的资源少。交换操作至少等于3次赋值操作外加3次计算--个人理解)。所以平均交换次数为(n-1)/2,用大O表示算法效率为:O(N)。
以上说明都以升序排序为例,降序排序稍有不同。
分享到:
相关推荐
本资源“易语言数组排序算法集合”提供了多种常见的排序算法的源代码实现,对于学习易语言以及算法理解都有极大的帮助。下面将详细介绍其中提及的几种排序算法。 1. **冒泡排序**: 冒泡排序是最基础的排序算法之...
本话题聚焦于“易语言自定义数据类型数组排序”,将深入探讨如何在易语言中创建、操作自定义数据类型数组,并实现各种排序算法,如根据产地、类别和售价等属性进行排序。 自定义数据类型在易语言中允许我们定义包含...
数组排序算法在C语言中有着广泛的应用,不仅限于上述的几种方法。其他常见的排序算法还包括冒泡排序、插入排序、快速排序、归并排序等,每种都有其适用的场景和优缺点。在实际编程中,根据数据规模、稳定性、空间...
数组排序是计算机科学中基础且重要的概念,尤其是在数据处理和算法设计中不可或缺。数组是一种线性数据结构,其中元素按照特定顺序存储。排序数组是指将数组中的元素按特定规则(通常为升序或降序)重新排列的过程。...
在编程领域,数组和排序算法是基础且至关重要的概念,特别是在Java编程中。数组是一种数据结构,它允许我们在内存中存储相同类型的数据项,并通过索引来访问这些元素。理解数组和掌握高效的排序算法对于编写高性能的...
冒泡排序算法是一种简单的排序算法,它通过比较相邻元素的值来将数组排序。其时间复杂度为O(n^2),因此它在小规模数据中的应用是非常广泛的。但是,当数据规模很大时,冒泡排序算法的效率就会下降。 接下来,我们...
### Java数组排序三种方法 #### 一、类排序方法(使用`Arrays.sort()`) 在Java中,`java.util.Arrays`类提供了一系列实用的方法来处理数组。其中,`sort()`方法可以方便地对数组进行排序。 **特点:** - **简单...
总结来说,LabVIEW中的二维数组排序涉及理解二维数组的结构,掌握各种排序方法,包括按行、按列及自定义排序,以及处理数据类型转换和性能优化。熟练掌握这些技能将使你在LabVIEW编程中游刃有余,处理各种数据处理...
这个项目的目标是创建一个一维数组排序程序,它具有灵活性,能够处理不同来源的数据,并提供三种经典的排序算法供用户选择:冒泡排序、选择排序和插入排序。下面我们将详细探讨这些知识点。 **一、一维数组** 一维...
数组排序通常涉及两种主要的算法:内部排序和外部排序。内部排序是指数据记录在内存中进行排序,而外部排序则涉及到大量数据需要在磁盘等外部存储器间移动。易语言中,我们主要关注内部排序,因为这里的描述提到的是...
易语言源码易语言数组排序算法集合源码.rar 易语言源码易语言数组排序算法集合源码.rar 易语言源码易语言数组排序算法集合源码.rar 易语言源码易语言数组排序算法集合源码.rar 易语言源码易语言数组排序算法集合...
本文将深入探讨五种常见的排序算法:堆排序、归并排序、选择排序、快速排序以及插入排序,并分析它们在不同数组状态下的时间复杂度。 1. **堆排序**: 堆排序是一种基于比较的排序算法,它利用了完全二叉树的特性...
综上所述,"任意插入一个数,给数组排序"涉及到的基本知识点包括数组的管理、插入操作以及排序算法的实现。理解这些概念对于编写高效、灵活的代码至关重要。在实际编程时,要根据具体需求选择合适的方法,并考虑到...
在本资源中,"文本数组排序模块测试程序"是一个用于验证和测试排序算法正确性的工具,可能是由开发者SanYe创建的。 排序算法是计算机科学中的核心部分,常见的有冒泡排序、选择排序、插入排序、快速排序、归并排序...
这两种方法都属于简单排序算法,适合小规模数据的排序,但对于大规模数据,它们的效率较低。 1. 冒泡排序:冒泡排序是一种基础的排序算法,通过比较相邻元素并交换位置(如果需要)来实现排序。这个过程会重复多次...
**冒泡排序**是一种简单的排序算法,它通过重复遍历数组,比较相邻元素并交换位置来实现排序。冒泡排序的时间复杂度在最好情况下(已排序数组)为O(n),最坏情况(反序数组)为O(n^2),平均情况也是O(n^2)。虽然冒泡...
在 MATLAB 中,数组排序是一个非常常见的操作,尤其在数据分析和科学计算中。MATLAB 提供了多种内置函数来满足不同的排序需求。以下是一些主要的排序方法及其详细说明: 1. **sort 函数**: - `sort(A)`:对一维...
该文档涵盖了数组排序的基本概念,包括如何实现各种排序算法,如冒泡排序、选择排序、插入排序、归并排序和快速排序。此外,文档还为每个排序算法提供了详细的代码示例和实现细节。 该文档还涵盖了高级主题,如如何...
数组排序是计算机科学中基础且重要的概念,尤其在算法和数据结构的学习中占有核心地位。本文将详细探讨数组的五种基本排序方法,包括冒泡排序、选择排序、插入排序、快速排序以及归并排序。这五种方法各有特点,适用...
本篇将深入探讨几种经典排序算法,这些算法不仅理论性强,而且在实际开发中具有广泛的应用。 首先,我们来了解最基本的冒泡排序(Bubble Sort)。冒泡排序是一种简单的排序方法,通过不断交换相邻的逆序元素,使...