重学数据结构和算法（四）之冒泡排序、插入排序、选择排序 |
您所在的位置：网站首页 › 数据结构排序中11*和11哪个大 › 重学数据结构和算法（四）之冒泡排序、插入排序、选择排序 |
重学数据结构和算法（四）之冒泡排序、插入排序、选择排序
|
最近学习了极客时间的《数据结构与算法之美》很有收获，记录总结一下。 欢迎学习老师的专栏：数据结构与算法之美 代码地址：https://github.com/peiniwan/Arithmetic 排序我们知道，时间复杂度反应的是数据规模 n 很大的时候的一个增长趋势，所以它表示的时候会忽略系数、常数、低阶。但是实际的软件开发中，我们排序的可能是 10 个、100 个、1000 个这样规模很小的数据，所以，在对同一阶时间复杂度的排序算法性能对比的时候，我们就要把系数、常数、低阶也考虑进来。 基于比较的排序算法的执行过程，会涉及两种操作，一种是元素比较大小，另一种是元素交换或移动。所以，如果我们在分析排序算法的执行效率的时候，应该把比较次数和交换（或移动）次数也考虑进去。  排序算法的内存消耗 算法的内存消耗可以通过空间复杂度来衡量，排序算法也不例外。不过，针对排序算法的空间复杂度，我们还引入了一个新的概念，原地排序（Sorted in place）。原地排序算法，就是特指空间复杂度是 O(1) 的排序算法。冒泡、插入、选择，都是原地排序算法。 排序算法的稳定性 针对排序算法，我们还有一个重要的度量指标，稳定性。这个概念是说，如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。 我通过一个例子来解释一下。比如我们有一组数据 2，9，3，4，8，3，按照大小排序之后就是 2，3，3，4，8，9。这组数据里有两个 3。 经过某种排序算法排序之后，如果两个 3 的前后顺序没有改变，那我们就把这种排序算法叫作稳定的排序算法；如果前后顺序发生变化，那对应的排序算法就叫作不稳定的排序算法。 稳定排序算法可以保持金额相同的两个对象，在排序之后的前后顺序不变 稳定排序有：插入排序，基数排序，归并排序 ，冒泡排序 ，基数排序。不稳定的排序算法有：快速排序，希尔排序，简单选择排序，堆排序。排序的稳定性,就是指,在对a关键字排序后会不会改变其他关键字的顺序。冒泡排序（Bubble Sort）稳定、原地排序 我们要对一组数据 4，5，6，3，2，1，从小到大进行排序。经过一次冒泡操作之后，6 这个元素已经存储在正确的位置上。要想完成所有数据的排序，我们只要进行 6 次这样的冒泡操作就行了。  实际上，刚讲的冒泡过程还可以优化。当某次冒泡操作已经没有数据交换时，说明已经达到完全有序，不用再继续执行后续的冒泡操作。我这里还有另外一个例子，这里面给 6 个元素排序，只需要 4 次冒泡操作就可以了。  代码语言：javascript复制// 冒泡排序，a表示数组，n表示数组大小
public void bubbleSort(int[] a, int n) {
if (n a[j+1]) { // 交换
int tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
flag = true; // 表示有数据交换
}
}
if (!flag) break; // 没有数据交换，提前退出
}
}插入排序（Insertion Sort）稳定、原地排序 基本思想是每一步将一个待排序的记录，插入到前面已经排好序的有序序列中去，直到插完所有元素为止。 一个有序的数组，我们往里面添加一个新的数据后，如何继续保持数据有序呢？很简单，我们只要遍历数组，找到数据应该插入的位置将其插入即可。  这是一个动态排序的过程，即动态地往有序集合中添加数据，我们可以通过这种方法保持集合中的数据一直有序。而对于一组静态数据，我们也可以借鉴上面讲的插入方法，来进行排序，于是就有了插入排序算法。 插入排序具体是如何借助上面的思想来实现排序的呢？  首先，我们将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。 要排序的数据是 4，5，6，1，3，2，其中左侧为已排序区间，右侧是未排序区间。  插入排序也包含两种操作，一种是元素的比较，一种是元素的移动。 当我们需要将一个数据 a 插入到已排序区间时，需要拿 a 与已排序区间的元素依次比较大小，找到合适的插入位置。找到插入点之后，我们还需要将插入点之后的元素顺序往后移动一位，这样才能腾出位置给元素 a 插入。 代码语言：javascript复制// 插入排序，a表示数组，n表示数组大小 public void insertionSort(int[] a, int n) { if (n = 0; --j) { if (a[j] > value) { a[j+1] = a[j]; // 数据移动，将大于temp的往后移动一位 } else { break; } } a[j+1] = value; // 插入数据 } }插入排序和冒泡排序的时间复杂度相同，都是 O(n2)，在实际的软件开发里，为什么我们更倾向于使用插入排序算法而不是冒泡排序算法呢？ 冒泡排序的数据交换要比插入排序的数据移动要复杂，冒泡排序需要 3 个赋值操作，而插入排序只需要 1 个。我们来看这段操作：冒泡排序中数据的交换操作： 代码语言：javascript复制冒泡排序中数据的交换操作： if (a[j] > a[j+1]) { // 交换 int tmp = a[j]; a[j] = a[j+1]; a[j+1] = tmp; flag = true; } 插入排序中数据的移动操作： if (a[j] > value) { a[j+1] = a[j]; // 数据移动 } else { break; }我们把执行一个赋值语句的时间粗略地计为单位时间（unit_time），然后分别用冒泡排序和插入排序对同一个逆序度是 K 的数组进行排序。用冒泡排序，需要 K 次交换操作，每次需要 3 个赋值语句，所以交换操作总耗时就是 3* K 单位时间。而插入排序中数据移动操作只需要 K 个单位时间。 二分法插入排序二分法插入排序是在插入第i个元素时，对前面的0～i-1元素进行折半，先跟他们中间的那个元素比，如果小，则对前半再进行折半，否则对后半进行折半，直到left>right，然后以左下标为标准，左及左后边全部后移，然后左位置前插入该数据。 二分法没有排序，只有查找。所以当找到要插入的位置时。移动必须从最后一个记录开始，向后移动一位，再移动倒数第2位，直到要插入的位置的记录移后一位。  代码语言：javascript复制 private static void sort(int[] a) {
// {4, 6, 8, 7, 3, 5, 9, 1}
// {4, 6, 7, 8, 3, 5, 9, 1}
for (int i = 1; i < a.length; i++) {
int temp = a[i];//7
int left = 0;
int right = i - 1;//2
int mid = 0;
//确定(找到)要插入的位置
while (left = left; j--) {
//以左下标为标准，左及左后边全部后移，然后左位置前插入该数据。
a[j + 1] = a[j];
}
if (left != i) {//如果相等，不需要移动
//左位置插入该数据
a[left] = temp;
}
}
}希尔排序（O(n^1.3)）希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。先取一个小于n的整数d1作为第一个增量，把数组的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2 |
【本文地址】
今日新闻 |
推荐新闻 |