数据结构和算法基础（8）——排序算法

一、排序介绍 1.分类 1.1 内部排序和外部排序。

• 内部排序值将需要处理的所有数据都加载到内存中进行排序.
• 外部排序借助外部存储进行排序。

常见的内部排序有：

1.2 非线性时间比较类排序和线性时间非比较类排序

• 非线性时间比较类排序：通过比较来决定元素间的相对次序，由于时间复杂度不能突破O(nlogn)，因此成为非线性时间比较类排序。
• 线性时间非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此被称为线性时间非比较类排序。
  

2.排序算法一张图分析

---

二、十大排序算法 1.冒泡排序 1.1 原理

通过对待排序序列从前往后（从下标较小的元素开始），依次比较相邻元素的值，若发现逆序则交换。每一次循环都会将大的值放到后面。

1.2 代码

	private static void bubbleSort(int[] array) {
        for (int i = 0;i < array.length-1;i++) {
            boolean isSwap = false;
            for (int j = 0;j < array.length -i-1;j++) {
                if (array[j] > array[j+1]) {
                    int temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                    isSwap =true;
                }
            }
            if (!isSwap){
                break;
            }
        }
    }

1.3 分析

（1）最优的情况也就是开始就已经排序好序了，那么就可以不用交换元素了，则时间花销为：[ n(n-1) ] / 2；所以最优的情况时间复杂度为：O( n^2 )。
（2）最坏的情况是逆序，那么比较次数是[ n(n-1) ] / 2，交换次数是[ n(n-1) ] / 2，总执行次数[ n^2 - n ]
（3）平均的时间复杂度为：O( n^2 )。
（4）上述代码是优化过的冒泡排序，最优时间复杂度O( n)。
（5）是稳定排序，相同值的元素不会交换位置。
（6）只需要额外一个临时变量，空间复杂度为O( 1)。

---

2.选择排序 2.1 原理

（1）每一次遍历的过程中，都假定第一个索引为当前索引，和其他索引处的值一次进行比较。如果其他索引小于当前索引，则当前索引值变为其他索引下标，最终当前索引为最小值所在的下标。
（2）交换第一个索引处和当前索引处的值。

2.2 代码

	private static void selectSort(int[] array) {
        for (int i = 0;i < array.length-1;i++) {
            int tempIndex = i;
            int temp = array[i];
            for (int j = i + 1;j < array.length;j++) {
                if (temp > array[j]) {
                    temp = array[j];
                    tempIndex = j;
                }
            }
            if (tempIndex != i) {
                array[tempIndex] = array[i];
                array[i] = temp;
            }
        }
    }

2.3 分析

（1）最好、最差、平均时间复杂度都是O(n^2)，应为都要比较[ n(n-1) ] / 2次，保留最高阶项，去掉常数因子，为 O(n^2)。
（2）选择排序是不稳定排序。
（3）选择排序是原地排序，空间复杂度O(1)。

---

3.插入排序 3.1 原理

（1）把所有元素分为两组，已经排序和未排序。
（2）找到未排序的组中的第一个元素，向已经排序的组中进行插入。
（3）倒叙遍历已经排序的元素，依次和待插入的元素进行比较，知道找到一个元素小于待插入元素，那么就把待插入元素放到这个位置，其他元素往后移动一位。

3.2 代码

	public static void StraightInsertionSort(int[] a) {
	   for (int i = 1; i < a.length  ;i ++) {
	       for (int j = i; j > 0;j --) {
                if (a[j] < a[j-1]) {
                    int temp = a[j];
                    a[j] = a[j-1];
                    a[j-1] = temp;
                } else {
                    break;
                }
           }
       }
    }

3.3 分析

（1）最好情况是原数组有序时间复杂度为n，最坏情况为原数组逆序时间复杂度为O(n^2)，平均时间复杂度为 O(n^2)。
（2）空间复杂度为O(1)，是原地排序。
（3）插入排序是稳定排序。

---

4.希尔排序 4.1 原理

希尔排序是插入排序的一种，又称缩小增量排序，是插入排序算法的一种更高效的改进版本。
前面的插入排序，存在一个不友好的问题：如果已排序元素为[2,5,7,9,10]，如果下一个待插入元素为1，我们需要拿着1依次和10，9，7，5，2交换位置。如果我们想提高效率，直观的想法是一次交换。
（1）选定一个增长量h，按照增长量h作为数据分组的依据，对数据进行分组。
（2）对分好组的每一组数据完成插入排序。
（3）减少增长量，最小减为1，重复第二步的 *** 作。

4.2代码

    public static void shellSort(int[] array) {
	    int temp = 0;
	    // 第一层循环，逐步减少增量
	   for (int gap = array.length / 2; gap > 0 ;gap/=2) {
	       // 内层两次循环和插入排序一样
           // 第二层循环从每个数组的第2个元素开始，所以从gap开始
	       for (int i = gap;i<array.length;i++) {
	           // 第三层循环用来从未排序数组往排序数组中插入j-gap是下一个要比较的元素，应该要大于等于0.
	           for (int j = i ;j >= gap; j -= gap) {
	               if (array[j] < array[j -gap]) {
	                   temp = array[j];
                       array[j] = array[j-1];
                       array[j-1] = temp;
                   }else {
	                   break;
                   }
               }
           }
       }
    }

4.3 分析

（1） 希尔排序的时间的时间复杂度为O(n ^(2/3))，希尔排序时间复杂度的下界是n*log2n。希尔排序没有快速排序算法快 O(n(logn))，因此中等大小规模表现良好，对规模非常大的数据排序不是最优选择。但是比O( )复杂度的算法快得多。
（2）空间复杂度为O(1)，是原地排序。
（3）希尔排序是不稳定排序。

4.4 希尔排序突破O(N^2)的原因

为啥希尔能突破O(N^2) 的界，可以用逆序数来理解。
假设我们要从小到大排序，一个数组中取两个元素如果前面比后面大，则为一个逆序，容易看出排序的本质就是消除逆序对。
可以证明对于随机数组，逆序数是N^2 数量级的，如果每次交换只能消除一个逆序对，那么就要执行 O(N^2)次，这就是为啥冒泡、插入等算法只能到平方级别的原因。
反过来，基于交换元素的排序要想突破这个下界，必须执行一些比较，交换相隔比较远的元素，使得一次交换能消除一个以上的逆序，希尔、快排、堆排等等算法都是交换比较远的元素，只不过规则各不同罢了。

但是不相邻的交换可以一次消除多个逆序对，那么会不会造成更多的逆序对呢？
答案是：这个需要人为制造规则保证这件事不发生，举个例子：
假设从小到大排序，简单起见设数组元素两两不等
现在发现了a[i]>a[j]，i 若a[k] 若a[k]>a[i]，交换a[j]和a[i]后，三者的逆序数从2变为1（例如2 3 1变成1 3 2）
若a[i]>a[k]>a[j]，交换a[i]和a[j]后，三者的逆序数从3变为0（例如3 2 1变成1 2 3）
所以，除非你去交换两个本来有序的元素，否则逆序数必然是递减的。

---

5.快速排序 5.1 原理

快速排序是对冒泡排序的一种改进。，它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据都要小。然后再按照此方法对这两部分进行快速排序，整个排序过程递归进行。
（1）首先设定一个分界值，通过该分解值将数组分成左右两个部分。
（2）将大于等于分界值的数据放到数组右边，小于分解值的数据放到数组的左边。
（3）然后左边和右边独立排序。每边重复（1）（2）步。

5.2代码