复旦大学961-数据结构-第四章-排序（一）排序的基本概念；插入排序,希尔排序

妖狐艹你老母 2022-12-12 15:21 90阅读 0赞

[961全部内容链接][961]

### 文章目录 ###

*  排序的基本概念
 *  插入排序
 *   *  直接插入排序
     *  折半插入排序
     *  希尔(Shell)排序

# 排序的基本概念 #

**排序**，就是重新排列列表中的元素，使表中的元素满足按关键字有序的过程。

排序算法分为两种，**稳定的**和**不稳定的**，假设有下列一串数据：7,2,**8**,4,9,8。该数据中有两个8，这里使用粗细来标记。对于稳定的排序，排序后的结果中两个8不会互换位置，即2,4,7,**8**,8,9。 但是对于不稳定的排序，排序之后，两个8的顺序就“有可能”发生变化，如2,4,7,8,**8**,9

根据数据是否全部存放于内存，还可以把排序分为两种：

1.  **内部排序**：内部排序指的是要排序的数据比较小，可以直接全部存放于内存中
2.  **外部排序**：相对于内部排序，要排序的数量比较大，比如几个G甚至几个T，无法直接存放于内存中，所以一次只能将一部分数据放入内存。这种排序称为外部排序。

# 插入排序 #

插入排序的基本思想：将待排序的序列分为两部分，前面是已经排好序的，后面是未排序的。每次从未排序的序列中选出一个，插入到已经排好序的序列。直到所有未排序序列为空。

## 直接插入排序 ##

根据插入排序的思想，可以很容易的想到直接排序算法。

<table> 
 <thead> 
  <tr> 
   <th>有序[ 0, …i ]</th> 
   <th>i + 1 (待排序元素)</th> 
   <th>i + 2，…，n (无序数列)</th> 
  </tr> 
 </thead> 
 <tbody></tbody> 
</table>

直接插入排序思想，第一部分为有序序列，第二部分是无序序列的第一个元素，第三部分是剩下的无序数列。算法（从小到大排列）如下：

1.  从数组下标1开始进行循环，来选择待排序元素x
2.  使x与其前面的一个元素进行对比，若比前面的元素小，则交换两个元素，否则说明x已经到了它想到的位置
3.  重复2过程，直到x到了它应该到的地方
4.  待1过程循环完毕，即排序完毕，该序列有序。

Java代码如下：

public static void insertionSort(Comparable[] array) { 
        if (array == null) return;
    
        for (int i = 1; i < array.length; i++) {   // 从1位置开始，依次将后面的无序序列都插入到前面的有序序列
    
            Comparable temp = array[i];
            int j; 
            // 从最后一个开始比较，若已经比较到了0这个位置，或前面的元素比temp小，则说明此轮已经排序完成。
            for (j = i; j > 0 && temp.compareTo(array[j-1]) < 0; j--) {  
                array[j] = array[j - 1];  // 这里之所以没有使用交换，是因为下一轮前面的元素又得把j-1给替换掉，所以统一在循环结束进行交换。
            }
            array[j] = temp; // 此时j就是要插入的位置，插入即可
        }
    }

复杂度分析

*  时间复杂度：平均时间复杂度和最坏的时间复杂度为O(n2)，这个应该没啥好说的，两层for循环。 最好的时间复杂度为O(n)，这个是因为当要排序的序列近乎有序时，每轮的比较都发现前一个元素已经比自己小了，这样就可以继续进行下一轮了。最终产生很少的元素交换。所以最好的时间复杂度为O(n)
 *  空间复杂度：O(1)

稳定性：稳定的。每次比较时，只有前面的元素比后面的元素大时，才会发生交换，若相等则不会交换，所以是稳定的。 但是出题的时候可能会变成大于等于都会交换，此时就会是不稳定的。

适用性：此方式适用于顺序存储（数组）和链式存储。因为不存在随机访问。

## 折半插入排序 ##

与直接插入排序差不多。直接插入排序是边比较边交换，而折半插入排序是：先对前面的有序数列进行折半查找，找出要插入的位置，然后再统一交换。其实效率差不多。但是折半插入不适用于链式存储。

代码如下：  
TODO，非重点，后期补充

## 希尔(Shell)排序 ##

希尔排序也是利用了直接插入的特性（近乎有序的序列时间复杂度O(n)）。基本思想为：

1.  将序列分成若干组，然后对每组进行直接插入排序。
2.  然后减小组的数量，相当于增大每组元素的个数，然后再次进行直接插入排序
3.  重复2，当只剩一下一组时，即该组代表整个数组，进行最后一次排序，然后排序就完成了。

希尔排序难理解的地方就是这个分组，它并不是将相邻的元素分成一组。而是将相距固定距离的元素分为一组，如将下标 0,3,6,9…的元素分为一组，相应的1,4,7,11…分为一组。此时距离d=3。用专业的话就是：先将待排序的表分割成若干型如 L\[i, i+d, i+2d, … , i+kd\]的“特殊”子表，即把相隔某个“增量”的记录组成一个子表，对各个子表分别进行直接插入排序，当整个表中的元素已呈“基本有序”时，再对全体记录进行一次直接插入排序。

对于增量d，每轮都要进行递减。推荐的方式是，第一次取n/2，第二次取 n/2/2，每次除以2，直到为0。 但是出题时往往会给出不同的d的递减方式，来让你求每轮的排序结果。

举例：

该例子中，经过了三轮将该序列排为有序序列。其中组号那一行的括号中相同的代表被分到了一组。考试中不需要单独画出分组情况。这里只是为了方便理解。

用java实现，代码如下：

public static void shellSort(Comparable[] array) { 
        if (array == null) return;
    
        for (int d = array.length / 2; d > 0; d = d / 2) {  // 第一轮 d=n/2,第二轮d=n/2/2，依次类推，直到d=0结束
    
            for (int i = d; i < array.length; i++) {   // i取d，类似直接插入排序中的i=1
                Comparable temp = array[i];  // 记录第一个位置的元素，用于该组交换过后的赋值
                int j;
                for (j = i; j >= d && temp.compareTo(array[j - d]) < 0; j = j - d) {   // 让当前元素与其 -kd 的元素对比，然后进行插入
                    array[j] = array[j - d];
                }
                array[j] = temp;
            }
        }
    }

注意这里的第二个for循环。希尔排序虽然将其分成了若干组，但实际执行的时候，并不是将第一组排序完成之后才进行第二组排序。 而是先对第1组的第1个元素进行插入排序，然后对第2组的第1个元素进行排序，然后第3组的第1个，依次类推。然后是第1组的第二个元素…

复杂度分析:

*  时间复杂度：最好的时间复杂度为O(n)，平均复杂度为O(n1.3)，最坏的时间复杂度为O(n2)
 *  空间复杂度：空间复杂度O(1)

稳定性：不稳定。若两个相同的数据被分为了不同的组，则有可能顺序会被调换

适用性：只适用于顺序存储。因为要用到随机访问的特性。

[961]: https://blog.csdn.net/zhaohongfei_358/article/details/111414370