算法-02-排序-冒泡插入选择排序

       一般最经典的、最常用的：冒泡排序、插入排序、选择排序、归并排序、快速排序、计数排序、基数排序、桶排序。那么我们如何分析一个"排序算法"呢？

1-分析排序算法要点

       时间复杂度：具体是指最好情况、最坏情况、平均情况下的时间复杂度。
       时间复杂度的系数，常数，低阶：对于排序规模很小的数据，在对同一阶时间复杂度的排序算法性能对比的时候，我们就要把系数、常数、低阶也考虑进来。
       比较次数和交换次数：在分析排序算法的执行效率的时候，应该把比较次数和交换（或移动）次数也考虑进去。
       排序算法的内存消耗：算法的内存消耗可以通过空间复杂度来衡量，排序算法也不例外；原地排序（Sorted in place）算法，就是特指空间复杂度是O(1)的排序算法。。
       排序算法的稳定性：如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。

2-冒泡-插入-选择排序

2.1-冒泡排序(Bubble Sort)

       冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复n次，就完成了n个数据的排序工作。
工作原理：原始数据14,15,16,13,12,11，冒泡排序的经过如下图：

我们展示一下第1轮冒泡出16的过程：

下图是多轮冒泡的结果

       Java代码体现，为了减少不必要的排序次数，我们如果发现没有数据交换，就可以结束排序，这样可以减少循环次数。

@Slf4j
public class BubbleSort {public static void main(String[] args) {int[] arr={10,8,9,15,23,6,24};sort(arr);}public static void sort(int[] arr) {int length = arr.length;if (length <= 1) {return;}for (int i = 0; i < length; i++) {boolean flag = false;for (int j = 0; j < length - i - 1; j++) {if (arr[j] > arr[j + 1]) {int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;flag = true;}}if(! flag){break;}}log.info("排序后数组arr={}",arr);}
}

（1）冒泡的过程只涉及相邻数据的交换操作，只需要常量级的临时空间，所以它的空间复杂度为O(1)，是一个原地排序算法。
（2）在冒泡排序中，只有交换才可以改变两个元素的前后顺序。为了保证冒泡排序算法的稳定性，当有相邻的两个元素大小相等的时候，我们不做交换，相同大小的数据在排序前后不会改变顺序，所以冒泡排序是稳定的排序算法。
（3）最好情况下，要排序的数据已经是有序的了，我们只需要进行一次冒泡操作，就可以结束了，所以最好情况时间复杂度是O(n)。而最坏的情况是，要排序的数据刚好是倒序排列的，我们需要进行n次冒泡操作，所以最坏情况时间复杂度为O(n^2)。平均情况下的时间复杂度就是O(n^2)。

2.2-插入排序(Insertion Sort)

       插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。

原始数组：14,15,16,13,12,11；排序的流程图如下：

@Slf4j
public class InsertionSort {public static void main(String[] args) {int[] arr = {10, 8, 9, 15, 23, 6, 24};sort(arr);}public static void sort(int[] arr) {int length = arr.length;if (length <= 1) {return;}for (int i = 1; i < length; i++) {int value = arr[i];int j = i - 1;for (; j >= 0; j--) {if (arr[j] > value) {arr[j + 1] = arr[j];} else {break;}}arr[j+1]=value;}log.info("排序后数组arr={}", arr);}
}

（1）从实现过程可以很明显地看出，插入排序算法的运行并不需要额外的存储空间，所以空间复杂度是O(1)，也就是说，这是一个原地排序算法。
（2）在插入排序中，对于值相同的元素，我们可以选择将后面出现的元素，插入到前面出现元素的后面，这样就可以保持原有的前后顺序不变，所以插入排序是稳定的排序算法。
（3）最好是时间复杂度为O(n)，最坏情况时间复杂度为O(n^2)，平均时间复杂度为O(n^2)。

2.3-选择排序（Selection Sort）

       选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素，将最小元素放到已排序区间的第一个位置。

@Slf4j
public class SelectionSort {public static void main(String[] args) {int[] arr = {10, 8, 9, 15, 23, 6, 24};sort(arr);}public static void sort(int[] arr) {int length = arr.length;if (length <= 1) {return;}int minIndex;//最小值元素索引int min;//最小值元素for (int i = 0; i < arr.length - 1; i++) {minIndex = i;min = arr[i];for (int j = i + 1; j < arr.length; j++) {if (min > arr[j]) {min = arr[j];minIndex = j;}}//交换if (minIndex != i) {arr[minIndex] = arr[i];arr[i] = min;}}log.info("排序后数组arr={}", arr);}
}

（1）选择排序空间复杂度为O(1)，是一种原地排序算法。
（2）选择排序是一种不稳定的排序算法。选择排序每次都要找剩余未排序元素中的最小值，并和前面的元素交换位置，这样破坏了稳定性。
（3）选择排序的最好情况时间复杂度、最坏情况和平均情况时间复杂度都为O(n^2)。

3-小结

 冒泡，插入，选择排序的平均时间复杂度都是O(n^2)，三种排序算法对比结果如下图：

       冒泡排序和插入排序的时间复杂度都是O(n2)，都是原地排序算法，插入排序要比冒泡排序性能更好。因为冒泡排序的数据交换要比插入排序的数据移动要复杂，冒泡排序需要3个赋值操作，而插入排序只需要1个，冒泡排序耗费更多的时间单位。