目录
一、如何分析一个排序算法？
1、算法的执行效率
2、排序算法的内存消耗
3、排序算法的稳定性
二、冒泡排序
一、冒泡排序原理
二、性能分析
三 、代码实现
三、插入排序
一、排序原理
二、性能分析
三、代码实现
四、选择排序
一、排序原理
二、性能分析
三、代码实现
问题：插入和冒泡复杂度都是O(n2)，为什么实际开发中更倾向与插入算法呢？
一、如何分析一个排序算法？
1、算法的执行效率
- 最好情况，最坏情况，平均时间复杂度
- 时间复杂度的系数，常数，低阶。在实际开发中有能数据规模很小，所以在对同一阶时间复杂度的排序算法分析时，就要考虑到 系数，常数，低阶
- 比较次数和交换次数
2、排序算法的内存消耗
原地排序算法：特指空间复杂度是O(1)的排序算法。如，冒泡，插入，选择
3、排序算法的稳定性
稳定性：如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间的先后位置顺序不变
相同值元素，哪个在前在后什么关系，为什么考虑算法的稳定性？
实际开发中，要排序的往往是一组对象，需要按照对象的key来排序
例如:
先按照下单时间给订单排序，排序完成后用稳定排序算法按照订单金额重新排序。保证了相同值的数据按照下单时间排序
二、冒泡排序
一、冒泡排序原理
1、冒泡排序只操作相邻两个数据
2、对相邻数据进行比较，看关系是否满足要求，不满足则交换
3、一次冒泡排序至少让一个元素到它应在的位置，重复n次，就完成了排序
4、排序优化，如果某次冒泡不存在数据交换，则说明已经达到完全有序，所以终止冒泡
如果按照从小到大排序，每一次冒泡都比较相邻的数据，如果前者大于后者就相互交换，一次冒泡结束，最大的值就到了最后。第二次冒泡将第二大的值移动到最后倒数第二位，重复数组长度-1次，就可以达到有序
二、性能分析
冒泡排序是原地排序算法：冒泡的过程只涉及到数据的交换，只需要常量级的临时空间，所以空间复杂度为O(1)
冒泡排序是稳定的排序算法：相同大小的数据不进行交换，不改变顺序
冒泡排序的时间复杂度：
- 最好时间复杂度 ：O(n) 1次冒泡
- 最坏时间复杂度：O(n2) 6次冒泡
平均时间复杂度O(n2)分析：
1、有序度：有序元素对：a[i] <= a[j], 如果 i < j。
倒序的数组有序度为0。完全有序的数组 1，2，3，4，5，6，有序度为n*(n-1)/2,就是15 。这种完全有序的数组的有序度叫满有序度
2、逆序度：逆序元素对：a[i] > a[j], 如果 i < j。
公式：逆序度 = 满有序度 - 有序度 排序的过程就是增加有序度，减少逆序度的过程，最好达到满有序度，说明排序完成
例如：
4，5，6，3，2，1 满有序度为15，初始有序度为3.每交换一次数据有序度+1.需要交换的次数一定的,为逆序度 15-3=12 进行12次交换数据
对于n个数据进行冒泡排序，平均交换次数？
最好情况，初始有序度为n*(n-1)/2，不需要交换数据，最坏情况，初始有序度为0，需要交换n*(n-1)/2次数据。我们取平均值为n*(n-1)/4
比较操作肯定要比交换操作多，而复杂度的上限是 O(n2)，所以平均时间复杂度为O(n2)
三 、代码实现
/**
* 冒泡排序
* @author chao
*/
public class Bubble_Sort {
public static void main(String[] args) {
int[] arrays = {3,5,4,1,2,6};
Bubble_Sort.sort(arrays, arrays.length);
System.out.println(Arrays.toString(arrays));
}
public static void sort(int[] arrays,int n) {
for (int i = 0; i < n-1 ; i++) {
boolean flag= false; //用来判断有木有交换数据
for (int j = 0; j < n-i-1; j++) {
if(arrays[j+1] < arrays[j]) {
int temp = arrays[j];
arrays[j]=arrays[j+1];
arrays[j+1]=temp;
flag=true;
}
}
//如果没有交换数据就跳出循环
if(!flag){
break;
}
}
//严蔚民书上的伪代码实现
// boolean flag = true;
// for (int i = n-1; i >0 && flag; i--) {
// flag=false;
// for (int j = 0; j < i; j++) {
// if(arrays[j+1] < arrays[j]) {
// int temp = arrays[j];
// arrays[j]=arrays[j+1];
// arrays[j+1]=temp;
// flag=true;
// }
// }
//
// }
}
}
/**
* 向下冒泡排序
* @author chao
*/
public class Bubble_Sort2 {
public static void main(String[] args) {
int[] arrays = { 3, 2, 6, 4, 5, 1 };
Bubble_Sort2.sort(arrays, arrays.length);
System.out.println(Arrays.toString(arrays));
}
/**
* 向下冒泡。可能比冒泡更易懂？
*
* 算法概要：
* 从0开始，用这个元素去跟后面的所有元素比较，如果发现这个元素大于后面的某个元素，则交换。
* 3 2 6 4 5 1
* 第一趟是从 index=0 也就是 3， 开始跟index=1及其后面的数字比较
* 3 大于 2，交换，变为 2 3 6 4 5 1，此时index=0的位置变为了2
* 接下来将用2跟index=2比较
* 2 不大于 6 不交换
* 2 不大于 4 不交换
* 2 不大于 5 不交换
* 2 大于 1，交换，变为 1 3 6 4 5 2，第一趟排序完成。
*
* 第二趟是从 index=1 也就是 3，开始跟index=2及其后面的数字比较
* 3 不大于 6 不交换
* 3 不大于 4 不交换
* 3 不大于 5 不交换
* 3 大于 2，交换，变为 1 2 6 4 5 3，第二趟排序完成。
*
* 第三趟是从 index=2 也就是 6，开始跟index=3及其后面的数字比较
* 6 大于 4，交换，变为 1 2 4 6 5 3, 此时 index = 2 的位置变为了4
* 接下来将用4跟index=4比较
* 4 不大于 5 不交换
* 4 大于 3，交换，变为 1 2 3 6 5 4，第三趟排序完成。
*
* 第四趟是从 index=3 也就是 6，开始跟index=4及其后面的数字比较
* 6 大于 5，交换，变为 1 2 3 5 6 4, 此时 index = 3 的位置变为了5
* 接下来将用5跟index=5比较
* 5 大于 4，交换，变为 1 2 3 4 6 5, 第四趟排序完成。
*
* 第五趟是从 index=4 也就是 6，开始跟index=5及其后面的数字比较
* 6 大于 5，交换，变为 1 2 3 4 5 6, 此时 index = 4 的位置变为了5
* 接下来将用5跟index=6比较
* index = 6 已经不满足 index < length 的条件，整个排序完成。
*/
public static void sort(int[] arrays, int n) {
if (arrays.length == 1)
return;
for (int i = 0; i < arrays.length - 1; i++) {
for (int j = i + 1; j < arrays.length; j++) {
if (arrays[i] > arrays[j]) {
int temp = arrays[i];
arrays[i] = arrays[j];
arrays[j] = temp;
}
}
}
}
}
三、插入排序
一、排序原理
首先，我们将数组中的数据分为2个区间，即已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素。插入算法的核心思想就是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间中的元素一直有序。重复这个过程，直到未排序中元素为空，算法结束
如上图，左侧为已排序区间，右边为未排序区间。每次取未排序区间的元素，如取图中1，和左侧进行一一比较寻找合适的位置，将前面的元素依次后移给 1 腾出空间。
移动次数等于逆序度: 例如上图 初始有序度为5，满有序度为15，逆有序度为10=3+3+4
二、性能分析
原地排序算法：不需要额外的存储空间
稳定排序算法：值相同的元素，将后面出现的元素，插入到前面出现元素的后面，保持原有前后顺序不变
插入排序的时间复杂度：
- 最好时间复杂度 ：O(n) 从头到尾遍历已有序数据
- 最坏时间复杂度：O(n2) 每次 插入相等于在数组的第一位插入新数据，所以要移动大量数据
- 平均时间复杂度: O(n2)
三、代码实现
/**
* 插入排序
* @author chao
*/
public class Insert_Sort {
public static void main(String[] args) {
int[] arrs = { 5, 4, 2, 7, 8 };
Insert_Sort.InsertSort(arrs, arrs.length);
System.out.println(Arrays.toString(arrs));
}
public static void InsertSort(int[] arrays, int n) {
for (int i = 1; i < n; i++) {
int value = arrays[i];
int j = i - 1;
for (; j >= 0; --j) {
// 找到自己的插入位置
if (arrays[j] > value) {
// 如果前面的元素比自己大就移动元素
arrays[j + 1] = arrays[j];
} else {
// 否则跳出循环
break;
}
}
// 在需要插入的位置插入数据
arrays[j + 1] = value;
}
}
}
四、选择排序
一、排序原理
类似插入排序，也分已排序区间和未排序区间。但是选择排序每次会从未排序区间找到最小的元素，将其放到已排序区间的末尾
二、性能分析
空间复杂度：选择排序是原地排序算法。
稳定性：选择排序不是稳定的排序算法。比如5，8，5，2，9 找到最小元素是2和5交换就不稳定了
时间复杂度：都是O(n^2)
1. 最好情况：O(n^2)。
2. 最坏情况：O(n^2)。
3. 平均情况：O(n^2)。
三、代码实现
/*
* 选择排序
*/
public class Selection_Sort {
public static void main(String[] args) {
int[] arrs = { 5, 4, 2, 7, 8, 1 };
Selection_Sort.selectSort(arrs, arrs.length);
System.out.println(Arrays.toString(arrs));
}
public static void selectSort(int arrs[], int n) {
for (int i = 0; i < n; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
// 寻找到最小数的下标
if (arrs[minIndex] > arrs[j]) {
minIndex = j;
}
}
// 交换数据
int minValue = arrs[i];
arrs[i] = arrs[minIndex];
arrs[minIndex] = minValue;
}
}
}
问题：插入和冒泡复杂度都是O(n2)，为什么实际开发中更倾向与插入算法呢？
我们前面分析冒泡排序和插入排序的时候讲到，冒泡排序不管怎么优化，元素交换的次数是一个固定值，是原始数据的逆序度。插入排序是同样的，不管怎么优化，元素移动的次数也等于原始数据的逆序度。
但是，从代码实现上来看，冒泡排序的数据交换要比插入排序的数据移动要复杂，冒泡排序需要 3 个赋值操作，而插入排序只需要 一个
//冒泡排序中数据的交换操作：
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;
}