首页 / 算法 / 数据结构与算法——排序算法(上)
数据结构与算法——排序算法(上)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了数据结构与算法——排序算法(上),小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含12829字,纯文字阅读大概需要19分钟。
内容图文
所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。排序算法,就是如何使得记录按照要求排列的方法。
在这篇博客中,我们接触到的算法都是基于比较的排序算法,如冒泡排序、插入排序(希尔排序)、选择排序等。
如何分析一个“排序算法”?
学习排序算法时,我们除了学习其算法原理、代码实现之外,更重要的是要学会如何评价、分析一个排序算法。
我们通过对算法的执行效率、内存消耗、稳定性,三个方面来展开分析,下面依次解释如何从这三个方面分析一个排序算法。
排序算法的执行效率
对于排序算法执行效率的分析,我们一般会从这几个方面来衡量:
- 最好情况、最坏情况、平均情况时间复杂度
我们在分析排序算法的时间复杂度时,要分别给出最好情况、最坏情况、平均情况下的时间复杂度。除此之外,你还需知道最好、最坏时间复杂度对应的要排序的原始数据是什么样的。
为什么要区分这三种时间复杂度呢?第一,有些排序算法会区分,为了好对比,所以我们都最好做一下区分。第二,对于要排序的数据,有的接近有序,有的完全无序。有序度不同的数据,对于排序的执行时间肯定是有影响的,我们要知道排序算法在不同数据下的性能表现。
- 时间复杂度的系数、常数、低阶
我们知道,时间复杂度反应的是数据规模n很大的时候的一个增长趋势,所以它表示的时候会忽略系数、常数、低阶。但是实际的软件开发中,我们排序的可能是10个、100个、1000个这样规模很小的数据,所以,在对同一阶时间复杂度的排序算法性能对比的时候,我们就要把系数、常数、低阶也考虑进来。
- 比较次数和交换(或移动)的次数
针对基于比较的排序算法,会设计两种操作,一种是元素比较大小,另一种是元素交换或移动。所以,如果我们在分析排序算法的执行效率的时候,应该把比较次数和交换(或移动)次数也考虑进去。
排序算法的内存消耗
我们可以通过时间复杂度来衡量排序算法的内存消耗。针对排序算法的空间复杂度,引入了一个新的概念,原地排序(Sorted in place)。原地排序算法,就是特指空间复杂度是O(1)的排序算法。
排序算法的稳定性
仅仅用执行效率和内存消耗来衡量排序算法的好坏是不够的。针对排序算法,我们还有一个重要的度量指标,稳定性。这个概念是说,如果待排序的序列中存在值相等的元素,经过排序之后,相等元素之间原有的先后顺序不变。
以下面这个例子来解释一下。比如我们有一组数据2,9,3,4,8,3,按照大小排序之后就是2,3,3,4,8,9.
这组数据里有两个3,经过某种排序算法排序之后,如果两个3的前后顺序没有改变,那我们就把这种排序算法矫正稳定的排序算法;如果前后顺序发生变化,那对应的排序算法就叫作不稳定的排序算法。
这里补充介绍一下关于排序算法的稳定性存在的意义,比如我们现在要给电商交易系统中的"订单"排序。订单有两个属性,一个是下单时间,另一个是订单金额。如果我们现在有10万条订单数据,我们希望按照金额从小到大对订单数据排序。对于金额相同的订单,我们希望按照下单时间从早到晚有序。对于这样一个排序需求,针对这种要求,我们最先想到的方法是:我们先按照金额对订单数据进行排序,然后,再遍历排序之后的订单数据,对于每个金额相同的小区间再按照下单时间排序。这种排序思路理解起来不难,但是实现起来会很复杂。
借助稳定排序算法,这个问题可以非常简洁的解决。解决思路是这样的:我们先按照下单时间给订单排序,排序完成之后,我们用稳定排序算法,按照订单的金额重新排序。两遍排序之后,我们得到的订单数据就是按照金额从小到大,金额相同的订单按照下单时间从早到晚排序的。
稳定排序算法可以保存金额相同的两个对象,在排序之后的前后顺序不变。第一次排序后,所有订单按照下单时间从早到晚有序了,在第二次排序中,我们用的是稳定的排序算法,所有经过第二次排序之后,相同金额的订单仍然保持下单时间从早到晚有序。
冒泡排序(Bubble Sort)
冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻两个元素进行比较,看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置,重复n次,就完成了n个数据的排序工作。
下面举一个例子来了解冒泡排序的整个过程,已知要对一组数据4,5,6,3,2,1,从小到大进行排序(一次冒泡的过程)。
A[5] |
1 |
1 |
1 |
1 |
1 |
6 |
A[4] |
2 |
2 |
2 |
2 |
6 |
1 |
A[3] |
3 |
3 |
3 |
6 |
2 |
2 |
A[2] |
6 |
6 |
6 |
3 |
3 |
3 |
A[1] |
5 |
5 |
5 |
5 |
5 |
5 |
A[0] |
4 |
4 |
4 |
4 |
4 |
4 |
可以看出,经过一次冒泡操作之后,"6"这个元素已经存储在正确的位置上。想要完成所有数据的排序,我只要进行6次这样的冒泡操作就行了。
冒泡次数 |
冒泡后的结果 |
|||||
初始状态 |
4 |
5 |
6 |
3 |
2 |
1 |
第1次冒泡 |
4 |
5 |
3 |
2 |
1 |
6 |
第2次冒泡 |
4 |
3 |
2 |
1 |
5 |
6 |
第3次冒泡 |
3 |
2 |
1 |
4 |
5 |
6 |
第4次冒泡 |
2 |
1 |
3 |
4 |
5 |
6 |
第5次冒泡 |
1 |
2 |
3 |
4 |
5 |
6 |
第6次冒泡 |
1 |
2 |
3 |
4 |
5 |
6 |
实际上,该冒泡过程还可以优化。当某次冒泡操作过程中未发生数据交换时,说明已经达到完全有序,不能再继续执行后续的冒泡操作。冒泡排序算法的原理比较好理解,下面是关于优化过的冒泡排序算法实现代码:
void bubbleSort(int a[], int n) // 冒泡排序,a表示数组,n表示数组的大小
{
if (n <= 1) return;
for (int i = 0; i < n; ++i)
{
bool flag = false;
for (int j = 0; j < n - i - 1; ++j)
{
if (a[j] > a[j + 1])
{
int temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
flag = true; // 表示有数据交换
}
}
if (!flag) break; // 没有数据交换
}
}
接下来对冒泡排序进行分析:
- 首先冒泡过程当中只涉及相邻数据的交换操作,只需要常量级的临时空间,所以它的空间复杂度为O(1),因此冒泡排序是一个原地排序算法。
- 在冒泡排序中,只有交换才可以改变两个元素的前后顺序。为了保证冒泡排序算法的稳定性,当有相邻的两个元素大小相等的时候,我们不做交换,相同大小的数据在排序前后不会改变顺序,所以冒泡排序是稳定的排序算法。
- 最好情况下,要排序的数据已经是有序的了,只需进行一次冒泡操作,就可以结束了,所以最好情况时间复杂度是O(n)。而最坏情况下是,要排序的数据刚好是逆序排列的,我们需要进行n次冒泡操作,所以最坏情况时间复杂度为O(n²)。
接下来分析一下平均情况下的时间复杂度。对于包含n个数据的数组,这n个数据就有n!种排列方式。不同的排列方式,冒泡排序执行的时间肯定不同的。这里我们通过数据的“有序度”和“逆序度”这两个概念来进行分析。有序度是数组种具有有序关系的元素对的个数。有序元素对用数据表达式表示就是这样:
有序元素对:a[i] <= a[j],如果i < j。
举例在2,4,3,1,5,6这组数据的有序度为11,因为其有序对位11个,分别是(2, 4)、(2, 3)、(2, 5)、(2, 6)、(4, 5)、(4, 6)、(3, 5)、(3, 6)、(1, 5)、(1, 6)、(5, 6)。同理对于一个倒叙排列 数组,比如6,5,4,3,2,1,有序度为0;对于一个完全有序的数组,比如1,2,3,4,5,6,有序度就是n*(n-1)/2,也就是15。我们把这种完全有序的数组的有序度叫作满有序度。
逆序度的定义正好跟有序度相反(默认从小到大为有序):
逆序元素对:a[i] > a[j],如果i < j。
关于这三个概念,我们还可以得到一个公式:逆序度=满有序度-有序度。我们排序的过程就是一种增加有序度,减少逆序度的过程,最后达到满有序度,就说明排序完成了。冒泡排序包含两个操作原子,比较和交换。每次交换一次,有序度就加1。不管算法怎么改进,交换次数总是确定的,即为逆序度也就是n*(n-1)/2-初始有序度。而对于包含n个数据的数组进行冒泡排序,平均交换次数是多少呢?最坏情况下,初始状态的有序度是0,所以要进行n*(n-1)/2次交换。最好情况下,初始状态的有序度为满有序度,就不需要进行交换。因此我们可以取个中间值n*(n-1)/4,来表示初始有序度既不是很高也不是很低的平均情况。
换句话说,平均情况下,需要n*(n-1)/4次交换操作,比较操作肯定要比交换操作多,而复杂度的上线是O(n²),所以平均情况下的时间复杂度就是O(n²)。
插入排序(Insertion Sort)
我们先来看一个问题。一个有序的数组,我们往里面添加一个新的数据后,如何继续保持数据有序呢?我们只需遍历数组,找到数据应该插入的位置将其插入即可。这是一个动态排序的过程,即动态的往有序集合中添加数据,我们可以通过这种方法保持集合中的数据一直有序。而对于一组静态数据,我们也可以借鉴上面讲的插入方法,来进行排序,于是就有了插入排序算法。
首先,我们将数组中的数据分为两个区间,已排序区间和未排序区间。初始已排序区间只有一个元素,就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素,在已排序区间中找到合适的插入位置将其插入,并保证已排序区间数据一直有序。重复这个过程,直到未排序区间中元素为空,算法结束。
如下面的例子所示,要排的数据是4,5,6,1,3,2,其中左侧为已排序区间,右侧是未排序区间。
插入次数 |
插入后的结果 |
|||||
初始状态 |
4 |
5 |
6 |
1 |
3 |
2 |
第1次插入 |
4 |
5 |
6 |
1 |
3 |
2 |
第2次插入 |
4 |
5 |
6 |
1 |
3 |
2 |
第3次插入 |
4 |
5 |
6 |
1 |
3 |
2 |
第4次插入 |
1 |
4 |
5 |
6 |
3 |
2 |
第5次插入 |
1 |
3 |
4 |
5 |
6 |
2 |
第6次插入 |
1 |
2 |
3 |
4 |
5 |
6 |
插入排序也包含两种操作,一种是元素的比较,一种是元素的移动。当我们需要将一个数据a插入到已排序区间时,需要拿a与已排序区间的元素依次比较大小,找到合适的插入位置。找到插入点之后,我们还需要将插入点之后的元素顺序往后移动一位,这样才能腾出位置给元素a插入。
对于不同的查找插入点方法(从头到尾,从尾到头),元素的比较次数是有区别的。但对于一个给定的初始化序列 ,移动操作的次数总是固定的,就等于逆序度。下面是插入排序的实现代码:
void insertionSort(int a[], int n) // 插入排序,a表示数组,n表示数组的大小
{
if (n <= 1) return;
for (int i = 1; i < n; ++i)
{
int value = a[i];
// 查找插入的位置
for (int j = i - 1; j >= 0; --j)
{
if (a[j] > value) // 元素的比较
a[j + 1] = a[j]; // 元素的移动
else
break;
}
// 插入数据
a[j + 1] = value;
}
}
接下来对插入排序进行分析:
- 首先从插入排序的实现过程来看,其运行中并不需要额外的存储空间,所以空间复杂度是O(1),因此插入排序是一个原地排序算法。
- 在插入排序中,对于值相同的元素,我们可以选择将后面出现的元素,插入到前面出现的元素后面,这样就可以保持原有的前后顺序不变,所以插入排序是稳定的排序算法。
- 最好情况下,要排序的数据已经是有序的,我们并不需要搬移任何数据。如果我们从尾到头在有序区间里查找插入位置,每次只需比较一个数据就能确定插入的位置。所以这种情况下,最好的时间复杂度为O(n)(从尾到头遍历已经有序的数据)。如果数据是倒序的,每次插入都相当于在数组的第一个位置插入新的数据,所以需要移动大量的数据(整个有序区间),所以最坏情况时间复杂度为O(n²)。已知我们在一个数组当中插入一个数据的平均时间复杂度为O(n),因此对于插入排序来说,每次插入操作就相当于在数组中插入一个数据,循环执行n次插入操作,所以平均情况下时间复杂度为O(n²)。
希尔排序(Shell Sort)
希尔排序(Shell Sort)是插入排序的一种,是针对直接插入排序算法的改进,它通过比较相距一定间隔的元素来工作,各趟比较所用的距离随着算法的进行而减少,直到只比较相邻元素的最后一趟排序为止。由于这个原因希尔排序又称缩小增量排序。
希尔排序使用一个序列h1,h2,...,ht,叫作增量序列(increment sequence)。只要h1=1,任何增量序列都是可行的,不过,有些增量序列比另一些增量序列更好。在使用增量hk的一趟排序后,对于每一个i我们都有a[i]≤a[i+k],所有相隔hk的元素都被排序。此时称文件(数据)是hk排序的(hk-sorted)。希尔排序的一个重要性质是:一个hk排序的文件保持它的hk排序性。这个性质也是增量非1之前的所有排序存在的意义。
增量序列的一个流行(但是不好)的选择是使用Shell建议的序列: 和 。如果深入学习希尔排序后,我们会看到,存在一些递增序列,它们对该算法的运行时间给出了重要的改进,即使是一个小的改变都可能剧烈地影响着算法的性能。
下面举一个例子帮助我们理解希尔排序的原理,其中要排序的数据为7,3,0,8,6,1,4,2,5,9。
第一趟 |
增量为5 |
|||||||||
初始数据 |
7 |
3 |
0 |
8 |
6 |
1 |
4 |
2 |
5 |
9 |
子序列1 |
7 |
|
|
|
|
1 |
|
|
|
|
子序列2 |
|
3 |
|
|
|
|
4 |
|
|
|
子序列3 |
|
|
0 |
|
|
|
|
2 |
|
|
子序列4 |
|
|
|
8 |
|
|
|
|
5 |
|
子序列5 |
|
|
|
|
6 |
|
|
|
|
9 |
排序结果 |
1 |
3 |
0 |
5 |
6 |
7 |
4 |
2 |
8 |
9 |
第二趟 |
增量为2 |
|||||||||
初始数据 |
1 |
3 |
0 |
5 |
6 |
7 |
4 |
2 |
8 |
9 |
子序列1 |
1 |
|
0 |
|
6 |
|
4 |
|
8 |
|
子序列2 |
|
3 |
|
5 |
|
7 |
|
2 |
|
9 |
排序结果 |
0 |
2 |
1 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
第三趟 |
增量为1 |
|||||||||
初始数据 |
0 |
2 |
1 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
排序结果 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
下面给出希尔排序的实现代码(使用希尔增量的希尔排序):
void shellSort(int a[], int n)
{
for (int gap = n / 2; gap > 0; gap /= 2)
{
for (int i = gap; i < n; ++i)
{
int tmp = a[i];
int j = i;
for (; j >= gap && tmp < a[j - gap]; j -= gap)
a[j] = a[j - gap];
a[j] = tmp;
}
}
}
下面对希尔排序进行分析:
- 希尔排序算法的时间复杂度与增量序列的选取有关,具体时间复杂度范围在O(n^(1.3-2))。
- 希尔排序算法是一种非稳定性的排序算法。
- 希尔排序的空间复杂度为O(1),因此希尔排序是原地排序算法。
对于希尔排序算法的优化很大程度上依赖于对增量序列的研究。
选择排序(Selection Sort)
选择排序算法的实现思路有点类似插入排序,也分已排序区间和未排序区间(初始情况下已排序区间为空)。但是选择排序每次会从未排序区间中找到最小的元素,将其放到已排序区间的末尾。下面给出了选择排序的原理图,其中要排序的数据为4,5,6,3,2,1,其中左侧为“最终候选人区间”,右侧为未排序区间:
选择次数 |
选择后的结果 |
|||||
初始状态 |
4 |
5 |
6 |
3 |
2 |
1 |
第1次选择 |
1 |
5 |
6 |
3 |
2 |
4 |
第2次选择 |
1 |
2 |
6 |
3 |
5 |
4 |
第3次选择 |
1 |
2 |
3 |
6 |
5 |
4 |
第4次选择 |
1 |
2 |
3 |
4 |
5 |
6 |
第5次选择 |
1 |
2 |
3 |
4 |
5 |
6 |
第6次选择 |
1 |
2 |
3 |
4 |
5 |
6 |
选择排序依旧包含两种基本操作:元素比较操作与元素交换操作。整个选择排序的过程,可以理解成依次确定最终有序区间的每个元素的过程,每次选择出未排序区间当中的最(小)值,与未排序区间的第一个元素进行交换(也就是于已排序区间的尾后元素进行交换),于是扩大了已排序区间,缩减了未排序区间,直到未排序区间仅有一个元素时,排序算法结束。
下面给出选择排序的实现代码:
void selectionSort(int a[], int n)
{
for (int i = 0; i < n - 1; ++i)
{
int value = i;
int j = i + 1;
for (; j < n; ++j)
{
if (a[j] < a[value])
value = j;
}
int flag = a[i];
a[i] = a[value];
a[value] = flag;
}
}
接下来对选择排序进行分析:
- 首先选择排序空间复杂度为O(1),是一种原地排序算法。
- 从之前的选择排序(举例)原理图中,我们可以看出每次选择排序都要找到剩余未排序元素中的最(小)值,并和前面的元素交换位置,这样破坏了稳定性,因此选择排序本身并不是一个稳定的排序算法。
- 选择排序最好情况下时间复杂度、最坏情况下时间复杂度和平均情况下时间复杂度都为O(n²),这一点从实现代码就可以明显的看出,无论要排序数据的有序度如何,选择排序执行的流程都不会改变。
正因为如此,相对于插入排序和冒泡排序,选择排序就稍显逊色了。
为什么我们更倾向于使用插入排序而不是冒泡排序?
我们在之前已经对冒泡排序与选择排序做出了分析,并且我们清楚冒泡排序无论怎么优化,元素交换的次数是一个固定值,就是原始数据的逆序度。插入排序也是同样的,不管怎么优化,元素的移动次数也等于原始数据的逆序度。
但是从代码实现上来看,冒泡排序的数据交换要比插入排序的数据移动要复杂,冒泡排序需要3个赋值操作,而插入排序只需要1个。我们来看这段操作:
// 冒泡排序中数据的交换操作:
if (a[j] > a[j + 1])
{
int temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
flag = true;
}
// 插入排序中数据的移动操作:
if (a[j] > value)
a[j + 1] = a[j];
else
break;
我们把执行一个赋值语句的时间粗略地计为单位时间(unit_time),然后分别用冒泡排序和插入排序对同一个逆序度为K的数组进行排序。用冒泡排序,需要K次交换操作,每次需要3个赋值语句,所以交换操作总耗时就是3*K单位时间。而插入排序中数据移动操作只需要K个单位时间。所以,虽然冒泡排序和插入排序在时间复杂度上是一样的,都是O(n²),但是如果我们希望把性能优化做到极致,那肯定首选插入排序。插入排序的算法思路也有很大的优化空间,比如希尔排序。
内容总结
以上是互联网集市为您收集整理的数据结构与算法——排序算法(上)全部内容,希望文章能够帮你解决数据结构与算法——排序算法(上)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。