黑马程序员技术交流社区
标题: 数据结构 [打印本页]
作者: 慢慢慢时光 时间: 2019-6-6 15:04
标题: 数据结构
排序算法大部分编程语言，都会提供排序函数，平常项目，也会经常使用排序
最经典，最常用的排序：冒泡排序、插入排序、选择排序、归并排序、快速排序、计数排序、基数排序和桶排序
排序算法时间复杂度是否基于比较
冒泡、插入、选择O(n²)是
快排、归并O(nlogn)是
桶、计数、基数O(n)否
思考题：插入排序和冒泡排序的时间复杂度相同，都是O(n2)，在实际的软件开发里，为什么我们更倾向于使用插入排序算法而不是冒泡排序算法呢？
1. 如何分析一个“排序算法”？学习排序算法，我们除了学习它的算法原理、代码实现之外，更重要的是要学会如何评价、分析一个排序算法。分析一个排序算法，要从哪几个方面入手呢？
排序算法的执行效率一般会从这几个方面来衡量：
1. 最好情况、最坏情况、平均情况时间复杂度要分别给出最好情况、最坏情况、平均情况下的时间复杂度。除此之外，你还要说出最好、最坏时间复杂度对应的要排序的原始数据是什么样的。
为什么要区分这三种时间复杂度呢？
第一，有些排序算法会区分，为了好对比，所以我们最好都做一下区分。
第二，对于要排序的数据，有的接近有序，有的完全无序。有序度不同的数据，对于排序的执行时间肯定是有影响的，我们要知道排序算法在不同数据下的性能表现。
2. 时间复杂度的系数、常数 、低阶时间复杂度反应的是数据规模n很大的时候的一个增长趋势，实际的软件开发中，我们排序的可能是10个、100个、1000个这样规模很小的数据，所以，在对同一阶时间复杂度的排序算法性能对比的时候，我们就要把系数、常数、低阶也考虑进来。
3. 比较次数和交换（或移动）次数基于比较的排序算法的执行过程，会涉及两种操作，一种是元素比较大小，另一种是元素交换或移动。
排序算法的内存消耗算法的内存消耗可以通过空间复杂度来衡量
针对排序算法的空间复杂度，我们还引入了一个新的概念，原地排序（Sorted in place）。原地排序算法，就是特指空间复杂度是O(1)的排序算法。我们今天讲的三种排序算法，都是原地排序算法。
排序算法的稳定性针对排序算法，我们还有一个重要的度量指标，稳定性。如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。
真正软件开发中，我们要排序的往往不是单纯的整数，而是一组对象，我们需要按照对象的某个key来排序。
比如说，我们现在要给电商交易系统中的“订单”排序。订单有两个属性，一个是下单时间，另一个是订单金额。如果我们现在有10万条订单数据，我们希望按照金额从小到大对订单数据排序。对于金额相同的订单，我们希望按照下单时间从早到晚有序。对于这样一个排序需求，我们怎么来做呢？
最先想到的方法是：我们先按照金额对订单数据进行排序，然后，再遍历排序之后的订单数据，对于每个金额相同的小区间再按照下单时间排序。这种排序思路理解起来不难，但是实现起来会很复杂
借助稳定排序算法，这个问题可以非常简洁地解决。解决思路是这样的：我们先按照下单时间给订单排序，注意是按照下单时间，不是金额。排序完成之后，我们用稳定排序算法，按照订单金额重新排序。两遍排序之后，我们得到的订单数据就是按照金额从小到大排序，金额相同的订单按照下单时间从早到晚排序的。
稳定排序算法可以保持金额相同的两个对象，在排序之后的前后顺序不变。第一次排序之后，所有的订单按照下单时间从早到晚有序了。在第二次排序中，我们用的是稳定的排序算法，所以经过第二次排序之后，相同金额的订单仍然保持下单时间从早到晚有序。
2 冒泡排序1. 概念冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复n次，就完成了n个数据的排序工作。
2. 代码实现public class BubbleSort {
// 冒泡排序，a表示数组，n表示数组大小
public static void bubbleSort(int[] a,int n){
if(n<=1) return;
for(int i=0;i<n;i++){
// 设立退出循环的标志位
boolean 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;//没有数据交换，提前退出
}
}
public static void main(String[] args) {
int[] a = {1,2,7,5,9,3};
bubbleSort(a,a.length);
for (int i = 0; i < a.length; i++) {
System.out.println(a);
}
}
}3. 问题描述1. 冒泡排序是原地排序算法吗？只涉及相邻数据的交换操作，只需要长良机的临时空间，空间复杂度为O(1)，原地排序
2. 冒泡排序是稳定的排序算法吗？只有交换才改变两个元素的前后顺序，为保证冒泡算法稳定性，相邻两个元素大小相等时，不做交换，相同大小的数据在排序前后顺序不变，稳定
3. 冒泡排序的时间复杂度最好情况，有序，只需要进行一次冒泡，就可以结束，时间复杂度为O(n)；最坏，倒序排列，n次冒泡，最坏时间复杂度为O(n²)
平均时间复杂度，对于包含n个数据的数组，n个数据有n!种排列方式。不同排列方式，执行时间不同。有一种思路，通过“有序度”和“逆序度”两个概念分析
有序度是数组中具有有序关系的元素对的个数。数学表达式：有序元素对：a<=a[j]，如果i<j
对于倒序排列的数组，有序度为0；完全有序的，有序度n*(n-1)/2，完全有序的有序度叫²
逆序度相反，默认从小到大为有序。逆序元素对：a>a[j]，如果i<j
逆序度=满有序度-有序度，排序过程就是增加有序度，减少逆序度，最后达到满有序度
冒泡排序包含两个操作原子，比较和交换。每交换一次，有序度加1，交换次数确定，也就是逆序度，为n*(n-1)/2-初始有序度
对于包含n个数据的数组进行冒泡排序，平均交换次数是多少呢？最坏情况，初始有序度0，进行n*(n-1)/2 次交换。最好情况，初始有序度为n*(n-1)/2 ，不需要交换，取中间值n*(n-1)/4 ，表示初始有序度的平均情况
也就是说，平均情况，需要n*(n-1)/4 次交换，比较操作肯定比交换操作多，而复杂度的上限为O(n²)，因此平均时间复杂度就是O(n²)
3. 插入排序（Insertion Sort）一个有序的数组，往里面添加一个新的数据，如何继续保持数据有序呢？只要遍历数组，找到数据应该插入的位置将其插入。
这是个动态过程，动态的往有序集合添加数据，通过该方法保持集合中的数据一直有序。而对于静态数据，也可以借鉴上面的过程。
插入排序具体是如何借助上面的思想实现排序呢？
首先，将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素。插入算法的核心思想是取未排序区间的元素，在已排序区间找合适的插入位置将其插入，并保证已排序区间数据一直有序。重复该过程，直到未排序区间中元素为空，算法结束。
插入排序也包含两种操作，一种是元素的比较，一种是元素的移动。当我们需要将一个数据a插入到已排序区间，需要拿a与已排序区间的元素依次比较大小，找到合适的插入位置。找到插入点后，需要将插入点之后的元素顺序往后移动一位，腾出位置给a插入。
对于不同的查找插入点方法（从头到尾，从尾到头），元素比较次数有区别。但对于一个给定的初始序列，移动操作的次数固定，等于逆序度。
看马士兵老师的视频，非常形象，比喻为打扑克，斗地主，接牌后怎么给手里的牌排序？就是插入排序！
代码实现public class InsertionSort {
// 插入排序，a表示数组，n表示数组大小
public static void insertionSort(int[] a, int n) {
if (n <= 1) return;
for (int i = 1; i < n; i++) {
int value = a;
// 指针，从i-1开始，每次都和后边的值比大小，挪位置，直到确定位置
int j = i - 1;
// 查找插入的位置
for (; j >= 0; j--) {
if (a[j] > value) {
a[j + 1] = a[j]; //数据移动
} else {
break;
}
}
a[j + 1] = value; // 插入数据
}
}
public static void main(String[] args) {
int[] a = {1,3,7,9,2,4};
insertionSort(a,a.length);
for (int i = 0; i < a.length; i++) {
System.out.println(a);
}
}
}3. 三个问题描述1. 插入排序是原地排序吗插入排序的运行不需要额外的存储空间，空间复杂度为O(1)，原地排序
2. 插入排序稳定吗在插入排序中，对于值相同的元素，可以选择将后面出现的元素，插入到前面出现元素的后边，保持原有的前后顺序不变，稳定。
3. 插入排序的时间复杂度如果已经有序，从尾到头查找插入位置，每次只需要比较一个数据就能确定插入的位置，最好时间复杂度为O(n)，注意：这是从尾到头遍历已经有序的数据。
如果数组是倒序的，每次插入都相当于在数组的第一个位置插入新的数据，需要移动大量的数据，最坏时间复杂度为O(n²)
我们在数组中插入一个数据的平均时间复杂度为O(n)，对于插入排序，每次插入操作都相当于在数组中插入一个数据，循环执行n次插入操作，平均时间复杂度为O(n²)
4. 选择排序（Selection Sort）实现思路类似插入排序，也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找最小的元素，将其放到已排序区间的末尾。
快排的时间复杂度为O(1)，是一种原地排序算法。选择排序的最好时间复杂度、最坏和平均时间复杂度都是O(n²)
选择排序不稳定，每次都要找剩余未排序元素的最小值，并和前面的元素交换位置，破坏了稳定性。
比如5,8,5,2,9，使用选择排序，第一次找到最小元素2，与第一个5交换位置，第一个5和中间的5的顺序就变了，不稳定。
5. 解答开篇冒泡排序和插入排序的时间复杂度都是O(n²)
| 欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) |
黑马程序员IT技术论坛 X3.2 |