devbox
酷酷是懒虫
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构 排序算法_直接插入排序一般时间复杂度

作者：酷酷是懒虫 | 2024-08-11 21:01:32

赞

踩

直接插入排序一般时间复杂度

越努力越幸运！ 

转载自：https://www.javazhiyin.com/13397.html 

 

稳定排序与不稳定排序 

选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法，而冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法

直接插入排序 

直接插入排序介绍

直接插入排序(Straight Insertion Sort)的基本思想是：把n个待排序的元素看成为一个有序表和一个无序表。开始时有序表中只包含1个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，将它插入到有序表中的适当位置，使之成为新的有序表，重复n-1次可完成排序过程。

直接插入排序图文说明

下面选取直接插入排序的一个中间过程对其进行说明。假设{20,30,40,10,60,50}中的前3个数已经排列过，是有序的了；接下来对10进行排列。示意图如下：

直接插入排序

 

图中将数列分为有序区和无序区。我们需要做的工作只有两个：(1)取出无序区中的第1个数，并找出它在有序区对应的位置。(2)将无序区的数据插入到有序区；若有必要的话，则对有序区中的相关数据进行移位。

直接插入排序的时间复杂度和稳定性

直接插入排序时间复杂度

直接插入排序的时间复杂度是O(N2)。

假设被排序的数列中有N个数。遍历一趟的时间复杂度是O(N)，需要遍历多少次呢？N-1！因此，直接插入排序的时间复杂度是O(N*N)。

直接插入排序稳定性

直接插入排序是稳定的算法，它满足稳定算法的定义。

算法稳定性 -- 假设在数列中存在a[i]=a[j]，若在排序之前，a[i]在a[j]前面；并且排序之后，a[i]仍然在a[j]前面。则这个排序算法是稳定的！

 

直接插入排序实现

Java实现

实现代码(InsertSort.java)

  1. /**
  2. * 直接插入排序：Java
  3. *
  4. *
  5. */
  6.  
  7. public class InsertSort {
  8.  
  9.    /*
  10.     * 直接插入排序
  11.     *
  12.     * 参数说明：
  13.     *     a -- 待排序的数组
  14.     *     n -- 数组的长度
  15.     */
  16.    public static void insertSort(int[] a, int n) {
  17.        int i, j, k;
  18.  
  19.        for (i = 1; i < n; i++) {
  20.  
  21.            //为a[i]在前面的a[0...i-1]有序区间中找一个合适的位置
  22.            for (j = i - 1; j >= 0; j--)
  23.                if (a[j] < a[i])
  24.                    break;
  25.  
  26.            //如找到了一个合适的位置
  27.            if (j != i - 1) {
  28.                //将比a[i]大的数据向后移
  29.                int temp = a[i];
  30.                for (k = i - 1; k > j; k--)
  31.                    a[k + 1] = a[k];
  32.                //将a[i]放到正确位置上
  33.                a[k + 1] = temp;
  34.            }
  35.        }
  36.    }
  37.  
  38.    public static void main(String[] args) {
  39.        int i;
  40.        int[] a = {20,40,30,10,60,50};
  41.  
  42.        System.out.printf("before sort:");
  43.        for (i=0; i<a.length; i++)
  44.            System.out.printf("%d ", a[i]);
  45.        System.out.printf("n");
  46.  
  47.        insertSort(a, a.length);
  48.  
  49.        System.out.printf("after  sort:");
  50.        for (i=0; i<a.length; i++)
  51.            System.out.printf("%d ", a[i]);
  52.        System.out.printf("n");
  53.    }
  54. }

输出结果：

  1. before sort:20 40 30 10 60 50 
  2. after  sort:10 20 30 40 50 60

 希尔排序

要点

希尔(Shell)排序又称为缩小增量排序，它是一种插入排序。它是直接插入排序算法的一种威力加强版。该方法因DL．Shell于1959年提出而得名。

希尔排序的基本思想是：

把记录按步长 gap 分组，对每组记录采用直接插入排序方法进行排序。

随着步长逐渐减小，所分成的组包含的记录越来越多，当步长的值减小到 1 时，整个数据合成为一组，构成一组有序记录，则完成排序。

 

我们来通过演示图，更深入的理解一下这个过程。 

希尔排序

 

在上面这幅图中：

初始时，有一个大小为 10 的无序序列。

在第一趟排序中，我们不妨设 gap1 = N / 2 = 5，即相隔距离为 5 的元素组成一组，可以分为 5 组。接下来，按照直接插入排序的方法对每个组进行排序。

在第二趟排序中，我们把上次的 gap 缩小一半，即 gap2 = gap1 / 2 = 2 (取整数)。这样每相隔距离为 2 的元素组成一组，可以分为 2 组。按照直接插入排序的方法对每个组进行排序。

在第三趟排序中，再次把 gap 缩小一半，即gap3 = gap2 / 2 = 1。 这样相隔距离为 1 的元素组成一组，即只有一组。按照直接插入排序的方法对每个组进行排序。此时，排序已经结束。

需要注意一下的是，图中有两个相等数值的元素 5 和 5 。我们可以清楚的看到，在排序过程中，两个元素位置交换了。

所以，希尔排序是不稳定的算法。

 

核心代码

  1. public void shellSort(int[] list) {
  2.  
  3.    int gap = list.length / 2;
  4.  
  5.    while (1 <= gap) {
  6.  
  7.        // 把距离为 gap 的元素编为一个组，扫描所有组
  8.        for (int i = gap; i < list.length; i++) {
  9.            int j = 0;
  10.            int temp = list[i];
  11.  
  12.            // 对距离为 gap 的元素组进行排序
  13.            for (j = i - gap; j >= 0 && temp < list[j]; j = j - gap) {
  14.                list[j + gap] = list[j];
  15.            }
  16.            list[j + gap] = temp;
  17.        }
  18.  
  19.        System.out.format("gap = %d:t", gap);
  20.        printAll(list);
  21.        gap = gap / 2; // 减小增量
  22.    }
  23. }

 

算法分析

希尔排序的算法性能

 

希尔排序

 

时间复杂度

步长的选择是希尔排序的重要部分。只要最终步长为1任何步长序列都可以工作。

算法最开始以一定的步长进行排序。然后会继续以一定步长进行排序，最终算法以步长为1进行排序。当步长为1时，算法变为插入排序，这就保证了数据一定会被排序。

Donald Shell 最初建议步长选择为N/2并且对步长取半直到步长达到1。虽然这样取可以比O(N2)类的算法（插入排序）更好，但这样仍然有减少平均时间和最差时间的余地。

可能希尔排序最重要的地方在于当用较小步长排序后，以前用的较大步长仍然是有序的。比如，如果一个数列以步长5进行了排序然后再以步长3进行排序，那么该数列不仅是以步长3有序，而且是以步长5有序。如果不是这样，那么算法在迭代过程中会打乱以前的顺序，那就不会以如此短的时间完成排序了。

步长序列

最坏情况下复杂度

希尔排序

希尔排序希尔排序

希尔排序

希尔排序希尔排序

希尔排序

希尔排序希尔排序

 

已知的最好步长序列是由Sedgewick提出的(1, 5, 19, 41, 109,...)，该序列的项来自这两个算式。这项研究也表明“比较在希尔排序中是最主要的操作，而不是交换。”用这样步长序列的希尔排序比插入排序和堆排序都要快，甚至在小数组中比快速排序还快，但是在涉及大量数据时希尔排序还是比快速排序慢。

算法稳定性

由上文的希尔排序算法演示图即可知，希尔排序中相等数据可能会交换位置，所以希尔排序是不稳定的算法。

直接插入排序和希尔排序的比较

  • 直接插入排序是稳定的；而希尔排序是不稳定的。

  • 直接插入排序更适合于原始记录基本有序的集合。

  • 希尔排序的比较次数和移动次数都要比直接插入排序少，当N越大时，效果越明显。 

  • 在希尔排序中，增量序列gap的取法必须满足：最后一个步长必须是 1 。 

  • 直接插入排序也适用于链式存储结构；希尔排序不适用于链式结构。

 

完整参考代码

JAVA版本代码实现(范例代码中的初始序列和本文图示中的序列完全一致)。

  1. package notes.javase.algorithm.sort;
  2.  
  3. public class ShellSort {
  4.    public void shellSort(int[] list) {
  5.        int gap = list.length / 2;
  6.  
  7.        while (1 <= gap) {
  8.            // 把距离为 gap 的元素编为一个组，扫描所有组
  9.            for (int i = gap; i < list.length; i++) {
  10.                int j = 0;
  11.                int temp = list[i];
  12.  
  13.                // 对距离为 gap 的元素组进行排序
  14.                for (j = i - gap; j >= 0 && temp < list[j]; j = j - gap) {
  15.                    list[j + gap] = list[j];
  16.                }
  17.                list[j + gap] = temp;
  18.            }
  19.  
  20.            System.out.format("gap = %d:t", gap);
  21.            printAll(list);
  22.            gap = gap / 2; // 减小增量
  23.        }
  24.    }
  25.  
  26.    // 打印完整序列
  27.    public void printAll(int[] list) {
  28.        for (int value : list) {
  29.            System.out.print(value + "t");
  30.        }
  31.        System.out.println();
  32.    }
  33.  
  34.    public static void main(String[] args) {
  35.        int[] array = {
  36.                9, 1, 2, 5, 7, 4, 8, 6, 3, 5
  37.        };
  38.  
  39.        // 调用希尔排序方法
  40.        ShellSort shell = new ShellSort();
  41.        System.out.print("排序前:tt");
  42.        shell.printAll(array);
  43.        shell.shellSort(array);
  44.        System.out.print("排序后:tt");
  45.        shell.printAll(array);
  46.    }
  47. }

 

运行结果

  1. 排序前:     9    1    2    5    7    4    8    6    3    5    
  2. gap = 5:    4    1    2    3    5    9    8    6    5    7    
  3. gap = 2:    2    1    4    3    5    6    5    7    8    9    
  4. gap = 1:    1    2    3    4    5    5    6    7    8    9    
  5. 排序后:      1    2    3    4    5    5    6    7    8    9

冒泡排序 

冒泡排序介绍

冒泡排序(Bubble Sort)，又被称为气泡排序或泡沫排序。

它是一种较简单的排序算法。它会遍历若干次要排序的数列，每次遍历时，它都会从前往后依次的比较相邻两个数的大小；如果前者比后者大，则交换它们的位置。这样，一次遍历之后，最大的元素就在数列的末尾！ 采用相同的方法再次遍历时，第二大的元素就被排列在最大元素之前。重复此操作，直到整个数列都有序为止！

 

冒泡排序图文说明

 

 

 

下面以数列{20,40,30,10,60,50}为例，演示它的冒泡排序过程(如下图)。

冒泡排序

 

我们先分析第1趟排序

  • 当i=5,j=0时，a[0]<a[1]。此时，不做任何处理！

  • 当i=5,j=1时，a[1]>a[2]。此时，交换a[1]和a[2]的值；交换之后，a[1]=30，a[2]=40。

  • 当i=5,j=2时，a[2]>a[3]。此时，交换a[2]和a[3]的值；交换之后，a[2]=10，a[3]=40。

  • 当i=5,j=3时，a[3]<a[4]。此时，不做任何处理！

  • 当i=5,j=4时，a[4]>a[5]。此时，交换a[4]和a[5]的值；交换之后，a[4]=50，a[3]=60。

 

于是，第1趟排序完之后，数列{20,40,30,10,60,50}变成了{20,30,10,40,50,60}。此时，数列末尾的值最大。

 

根据这种方法：

  • 第2趟排序完之后，数列中a[5...6]是有序的。

  • 第3趟排序完之后，数列中a[4...6]是有序的。

  • 第4趟排序完之后，数列中a[3...6]是有序的。

  • 第5趟排序完之后，数列中a[1...6]是有序的。

 

第5趟排序之后，整个数列也就是有序的了。

冒泡排序的时间复杂度和稳定性

冒泡排序时间复杂度

冒泡排序的时间复杂度是O(N2)。假设被排序的数列中有N个数。遍历一趟的时间复杂度是O(N)，需要遍历多少次呢？N-1次！因此，冒泡排序的时间复杂度是O(N2)。

冒泡排序稳定性

冒泡排序是稳定的算法，它满足稳定算法的定义。

算法稳定性 -- 假设在数列中存在a[i]=a[j]，若在排序之前，a[i]在a[j]前面；并且排序之后，a[i]仍然在a[j]前面。则这个排序算法是稳定的！

冒泡排序实现

冒泡排序Java实现

实现代码(BubbleSort.java)

  1. /**
  2. * 冒泡排序：Java
  3. *
  4. * 
  5. */
  6.  
  7. public class BubbleSort {
  8.  
  9.    /*
  10.     * 冒泡排序
  11.     *
  12.     * 参数说明：
  13.     *     a -- 待排序的数组
  14.     *     n -- 数组的长度
  15.     */
  16.    public static void bubbleSort1(int[] a, int n) {
  17.        int i,j;
  18.  
  19.        for (i=n-1; i>0; i--) {
  20.            // 将a[0...i]中最大的数据放在末尾
  21.            for (j=0; j<i; j++) {
  22.  
  23.                if (a[j] > a[j+1]) {
  24.                    // 交换a[j]和a[j+1]
  25.                    int tmp = a[j];
  26.                    a[j] = a[j+1];
  27.                    a[j+1] = tmp;
  28.                }
  29.            }
  30.        }
  31.    }
  32.  
  33.    /*
  34.     * 冒泡排序(改进版)
  35.     *
  36.     * 参数说明：
  37.     *     a -- 待排序的数组
  38.     *     n -- 数组的长度
  39.     */
  40.    public static void bubbleSort2(int[] a, int n) {
  41.        int i,j;
  42.        int flag;                 // 标记
  43.  
  44.        for (i=n-1; i>0; i--) {
  45.  
  46.            flag = 0;            // 初始化标记为0
  47.            // 将a[0...i]中最大的数据放在末尾
  48.            for (j=0; j<i; j++) {
  49.                if (a[j] > a[j+1]) {
  50.                    // 交换a[j]和a[j+1]
  51.                    int tmp = a[j];
  52.                    a[j] = a[j+1];
  53.                    a[j+1] = tmp;
  54.  
  55.                    flag = 1;    // 若发生交换，则设标记为1
  56.                }
  57.            }
  58.  
  59.            if (flag==0)
  60.                break;            // 若没发生交换，则说明数列已有序。
  61.        }
  62.    }
  63.  
  64.    public static void main(String[] args) {
  65.        int i;
  66.        int[] a = {20,40,30,10,60,50};
  67.  
  68.        System.out.printf("before sort:");
  69.        for (i=0; i<a.length; i++)
  70.            System.out.printf("%d ", a[i]);
  71.        System.out.printf("n");
  72.  
  73.        bubbleSort1(a, a.length);
  74.        //bubbleSort2(a, a.length);
  75.  
  76.        System.out.printf("after  sort:");
  77.        for (i=0; i<a.length; i++)
  78.            System.out.printf("%d ", a[i]);
  79.        System.out.printf("n");
  80.    }
  81. }

 

上面3种实现的原理和输出结果都是一样的。下面是它们的输出结果：

  1. before sort:20 40 30 10 60 50 
  2. after  sort:10 20 30 40 50 60

快速排序 

快速排序介绍

快速排序(Quick Sort)使用分治法策略。

它的基本思想是：选择一个基准数，通过一趟排序将要排序的数据分割成独立的两部分；其中一部分的所有数据都比另外一部分的所有数据都要小。然后，再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

快速排序流程：

  1. 从数列中挑出一个基准值。

  2. 将所有比基准值小的摆放在基准前面，所有比基准值大的摆在基准的后面(相同的数可以到任一边)；在这个分区退出之后，该基准就处于数列的中间位置。

  3. 递归地把"基准值前面的子数列"和"基准值后面的子数列"进行排序。

 

快速排序图文说明

下面以数列a={30,40,60,10,20,50}为例，演示它的快速排序过程(如下图)。

快速排序

 

上图只是给出了第1趟快速排序的流程。在第1趟中，设置x=a[i]，即x=30。

  1. 从"右 --> 左"查找小于x的数：找到满足条件的数a[j]=20，此时j=4；然后将a[j]赋值a[i]，此时i=0；接着从左往右遍历。

  2. 从"左 --> 右"查找大于x的数：找到满足条件的数a[i]=40，此时i=1；然后将a[i]赋值a[j]，此时j=4；接着从右往左遍历。

  3. 从"右 --> 左"查找小于x的数：找到满足条件的数a[j]=10，此时j=3；然后将a[j]赋值a[i]，此时i=1；接着从左往右遍历。

  4. 从"左 --> 右"查找大于x的数：找到满足条件的数a[i]=60，此时i=2；然后将a[i]赋值a[j]，此时j=3；接着从右往左遍历。

  5. 从"右 --> 左"查找小于x的数：没有找到满足条件的数。当i>=j时，停止查找；然后将x赋值给a[i]。此趟遍历结束！

按照同样的方法，对子数列进行递归遍历。最后得到有序数组！

快速排序的时间复杂度和稳定性

快速排序稳定性

快速排序是不稳定的算法，它不满足稳定算法的定义。

算法稳定性 -- 假设在数列中存在a[i]=a[j]，若在排序之前，a[i]在a[j]前面；并且排序之后，a[i]仍然在a[j]前面。则这个排序算法是稳定的！

快速排序时间复杂度

快速排序的时间复杂度在最坏情况下是O(N2)，平均的时间复杂度是O(N*lgN)。

这句话很好理解：假设被排序的数列中有N个数。遍历一次的时间复杂度是O(N)，需要遍历多少次呢？至少lg(N+1)次，最多N次。

(01) 为什么最少是lg(N+1)次？快速排序是采用的分治法进行遍历的，我们将它看作一棵二叉树，它需要遍历的次数就是二叉树的深度，而根据完全二叉树的定义，它的深度至少是lg(N+1)。因此，快速排序的遍历次数最少是lg(N+1)次。

(02) 为什么最多是N次？这个应该非常简单，还是将快速排序看作一棵二叉树，它的深度最大是N。因此，快读排序的遍历次数最多是N次。

 

快速排序实现

快速排序Java实现

实现代码(QuickSort.java)

  1. /**
  2. * 快速排序：Java
  3. *
  4. */
  5.  
  6. public class QuickSort {
  7.  
  8.    /*
  9.     * 快速排序
  10.     *
  11.     * 参数说明：
  12.     *     a -- 待排序的数组
  13.     *     l -- 数组的左边界(例如，从起始位置开始排序，则l=0)
  14.     *     r -- 数组的右边界(例如，排序截至到数组末尾，则r=a.length-1)
  15.     */
  16.    public static void quickSort(int[] a, int l, int r) {
  17.  
  18.        if (l < r) {
  19.            int i,j,x;
  20.  
  21.            i = l;
  22.            j = r;
  23.            x = a[i];
  24.            while (i < j) {
  25.                while(i < j && a[j] > x)
  26.                    j--; // 从右向左找第一个小于x的数
  27.                if(i < j)
  28.                    a[i++] = a[j];
  29.                while(i < j && a[i] < x)
  30.                    i++; // 从左向右找第一个大于x的数
  31.                if(i < j)
  32.                    a[j--] = a[i];
  33.            }
  34.            a[i] = x;
  35.            quickSort(a, l, i-1); /* 递归调用 */
  36.            quickSort(a, i+1, r); /* 递归调用 */
  37.        }
  38.    }
  39.  
  40.    public static void main(String[] args) {
  41.        int i;
  42.        int a[] = {30,40,60,10,20,50};
  43.  
  44.        System.out.printf("before sort:");
  45.        for (i=0; i<a.length; i++)
  46.            System.out.printf("%d ", a[i]);
  47.        System.out.printf("n");
  48.  
  49.        quickSort(a, 0, a.length-1);
  50.  
  51.        System.out.printf("after  sort:");
  52.        for (i=0; i<a.length; i++)
  53.            System.out.printf("%d ", a[i]);
  54.        System.out.printf("n");
  55.    }
  56. }

输出结果：

  1. before sort:30 40 60 10 20 50
  2. after  sort:10 20 30 40 50 60

 简单选择排序

选择排序介绍

选择排序(Selection sort)是一种简单直观的排序算法。

它的基本思想是：首先在未排序的数列中找到最小(or最大)元素，然后将其存放到数列的起始位置；接着，再从剩余未排序的元素中继续寻找最小(or最大)元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

 

选择排序图文说明

下面以数列{20,40,30,10,60,50}为例，演示它的选择排序过程(如下图)。

选择排序

 

排序流程

  • 第1趟：i=0。找出a[1...5]中的最小值a[3]=10，然后将a[0]和a[3]互换。 数列变化：20,40,30,10,60,50 -- > 10,40,30,20,60,50

  • 第2趟：i=1。找出a[2...5]中的最小值a[3]=20，然后将a[1]和a[3]互换。 数列变化：10,40,30,20,60,50 -- > 10,20,30,40,60,50

  • 第3趟：i=2。找出a[3...5]中的最小值，由于该最小值大于a[2]，该趟不做任何处理。 

  • 第4趟：i=3。找出a[4...5]中的最小值，由于该最小值大于a[3]，该趟不做任何处理。 

  • 第5趟：i=4。交换a[4]和a[5]的数据。 数列变化：10,20,30,40,60,50 -- > 10,20,30,40,50,60

 

选择排序的时间复杂度和稳定性

选择排序时间复杂度

选择排序的时间复杂度是O(N2)。

假设被排序的数列中有N个数。遍历一趟的时间复杂度是O(N)，需要遍历多少次呢？N-1！因此，选择排序的时间复杂度是O(N2)。

选择排序稳定性

选择排序是稳定的算法，它满足稳定算法的定义。

算法稳定性 -- 假设在数列中存在a[i]=a[j]，若在排序之前，a[i]在a[j]前面；并且排序之后，a[i]仍然在a[j]前面。则这个排序算法是稳定的！

 

选择排序实现

选择排序Java实现

实现代码(SelectSort.java)

  1. /**
  2. * 选择排序：Java
  3. *
  4. *
  5. */
  6.  
  7. public class SelectSort {
  8.  
  9.    /*
  10.     * 选择排序
  11.     *
  12.     * 参数说明：
  13.     *     a -- 待排序的数组
  14.     *     n -- 数组的长度
  15.     */
  16.    public static void selectSort(int[] a, int n) {
  17.        int i;        // 有序区的末尾位置
  18.        int j;        // 无序区的起始位置
  19.        int min;    // 无序区中最小元素位置
  20.  
  21.        for(i=0; i<n; i++) {
  22.            min=i;
  23.  
  24.            // 找出"a[i+1] ... a[n]"之间的最小元素，并赋值给min。
  25.            for(j=i+1; j<n; j++) {
  26.                if(a[j] < a[min])
  27.                    min=j;
  28.            }
  29.  
  30.            // 若min!=i，则交换 a[i] 和 a[min]。
  31.            // 交换之后，保证了a[0] ... a[i] 之间的元素是有序的。
  32.            if(min != i) {
  33.                int tmp = a[i];
  34.                a[i] = a[min];
  35.                a[min] = tmp;
  36.            }
  37.        }
  38.    }
  39.  
  40.    public static void main(String[] args) {
  41.        int i;
  42.        int[] a = {20,40,30,10,60,50};
  43.  
  44.        System.out.printf("before sort:");
  45.        for (i=0; i<a.length; i++)
  46.            System.out.printf("%d ", a[i]);
  47.        System.out.printf("n");
  48.  
  49.        selectSort(a, a.length);
  50.  
  51.        System.out.printf("after  sort:");
  52.        for (i=0; i<a.length; i++)
  53.            System.out.printf("%d ", a[i]);
  54.        System.out.printf("n");
  55.    }
  56. }

输出结果：

  1. before sort:20 40 30 10 60 50 
  2. after  sort:10 20 30 40 50 60

堆排序

堆排序

堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。首先简单了解下堆结构。

堆

堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。如下图：

堆排序

 

同时，我们对堆中的结点按层进行编号，将这种逻辑结构映射到数组中就是下面这个样子：

堆排序

该数组从逻辑上讲就是一个堆结构，我们用简单的公式来描述一下堆的定义就是：

大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]  

小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]  

ok，了解了这些定义。接下来，我们来看看堆排序的基本思想及基本步骤：

堆排序基本思想及步骤

堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了

步骤一 构造初始堆。将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)。

1.假设给定无序序列结构如下

堆排序

 

2.此时我们从最后一个非叶子结点开始（叶结点自然不用调整，第一个非叶子结点 arr.length/2-1=5/2-1=1，也就是下面的6结点），从左至右，从下至上进行调整。

堆排序

 

3.找到第二个非叶节点4，由于[4,9,8]中9元素最大，4和9交换。

堆排序

 

这时，交换导致了子根[4,5,6]结构混乱，继续调整，[4,5,6]中6最大，交换4和6。

堆排序

此时，我们就将一个无需序列构造成了一个大顶堆。

 

步骤二 将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。

 

a.将堆顶元素9和末尾元素4进行交换

堆排序

 

b.重新调整结构，使其继续满足堆定义

堆排序

 

c.再将堆顶元素8与末尾元素5进行交换，得到第二大元素8.

堆排序

 

后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序

堆排序

再简单总结下堆排序的基本思路：

  1. 将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;

  2. 将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;

  3. 重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

 

代码实现

  1.  
  2.  
  3. import java.util.Arrays;
  4.  
  5. /**
  6. *
  7. */
  8. public class HeapSort {
  9.    public static void main(String []args){
  10.        int []arr = {9,8,7,6,5,4,3,2,1};
  11.        sort(arr);
  12.        System.out.println(Arrays.toString(arr));
  13.    }
  14.    public static void sort(int []arr){
  15.        //1.构建大顶堆
  16.        for(int i=arr.length/2-1;i>=0;i--){
  17.            //从第一个非叶子结点从下至上，从右至左调整结构
  18.            adjustHeap(arr,i,arr.length);
  19.        }
  20.        //2.调整堆结构+交换堆顶元素与末尾元素
  21.        for(int j=arr.length-1;j>0;j--){
  22.            swap(arr,0,j);//将堆顶元素与末尾元素进行交换
  23.            adjustHeap(arr,0,j);//重新对堆进行调整
  24.        }
  25.  
  26.    }
  27.  
  28.    /**
  29.     * 调整大顶堆（仅是调整过程，建立在大顶堆已构建的基础上）
  30.     * @param arr
  31.     * @param i
  32.     * @param length
  33.     */
  34.    public static void adjustHeap(int []arr,int i,int length){
  35.        int temp = arr[i];//先取出当前元素i
  36.        for(int k=i*2+1;k<length;k=k*2+1){
  37.        //从i结点的左子结点开始，也就是2i+1处开始
  38.            if(k+1<length && arr[k]<arr[k+1]){
  39.            //如果左子结点小于右子结点，k指向右子结点
  40.                k++;
  41.            }
  42.            if(arr[k] >temp){
  43.            //如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
  44.                arr[i] = arr[k];
  45.                i = k;
  46.            }else{
  47.                break;
  48.            }
  49.        }
  50.        arr[i] = temp;//将temp值放到最终的位置
  51.    }
  52.  
  53.    /**
  54.     * 交换元素
  55.     * @param arr
  56.     * @param a
  57.     * @param b
  58.     */
  59.    public static void swap(int []arr,int a ,int b){
  60.        int temp=arr[a];
  61.        arr[a] = arr[b];
  62.        arr[b] = temp;
  63.    }
  64. }

结果

[1, 2, 3, 4, 5, 6, 7, 8, 9]

堆排序是一种选择排序，整体主要由构建初始堆+交换堆顶元素和末尾元素并重建堆两部分组成。其中构建初始堆经推导复杂度为O(n)，在交换并重建堆的过程中，需交换n-1次，而重建堆的过程中，根据完全二叉树的性质，[log2(n-1),log2(n-2)...1]逐步递减，近似为nlogn。所以堆排序时间复杂度一般认为就是O(nlogn)级。

 

归并排序

基本思想

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。

分而治之

归并排序

可以看到这种结构很像一棵完全二叉树，本文的归并排序我们采用递归去实现（也可采用迭代的方式去实现）。分阶段可以理解为就是递归拆分子序列的过程，递归深度为log2n。

合并相邻有序子序列

再来看看治阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]，来看下实现步骤。

归并排序

归并排序

 

代码实现

  1. package sortdemo;
  2.  
  3. import java.util.Arrays;
  4.  
  5. /**
  6. * 
  7. */
  8. public class MergeSort {
  9.   public static void main(String []args){
  10.       int []arr = {9,8,7,6,5,4,3,2,1};
  11.       sort(arr);
  12.       System.out.println(Arrays.toString(arr));
  13.   }
  14.   public static void sort(int []arr){
  15.       int []temp = new int[arr.length];
  16.       //在排序前，先建好一个长度等于原数组长度的临时数组，
  17.       //避免递归中频繁开辟空间
  18.       sort(arr,0,arr.length-1,temp);
  19.   }
  20.   private static void sort(int[] arr,int left,int right,int []temp){
  21.       if(left<right){
  22.           int mid = (left+right)/2;
  23.           sort(arr,left,mid,temp);
  24.           //左边归并排序，使得左子序列有序
  25.           sort(arr,mid+1,right,temp);
  26.           //右边归并排序，使得右子序列有序
  27.           merge(arr,left,mid,right,temp);
  28.           //将两个有序子数组合并操作
  29.       }
  30.   }
  31.   private static void merge(int[] arr,int left,int mid,int right,int[] temp){
  32.       int i = left;//左序列指针
  33.       int j = mid+1;//右序列指针
  34.       int t = 0;//临时数组指针
  35.       while (i<=mid && j<=right){
  36.           if(arr[i]<=arr[j]){
  37.               temp[t++] = arr[i++];
  38.           }else {
  39.               temp[t++] = arr[j++];
  40.           }
  41.       }
  42.       while(i<=mid){//将左边剩余元素填充进temp中
  43.           temp[t++] = arr[i++];
  44.       }
  45.       while(j<=right){//将右序列剩余元素填充进temp中
  46.           temp[t++] = arr[j++];
  47.       }
  48.       t = 0;
  49.       //将temp中的元素全部拷贝到原数组中
  50.       while(left <= right){
  51.           arr[left++] = temp[t++];
  52.       }
  53.   }
  54. }

执行结果

[1, 2, 3, 4, 5, 6, 7, 8, 9]

 

归并排序是稳定排序，它也是一种十分高效的排序，能利用完全二叉树特性的排序一般性能都不会太差。java中Arrays.sort()采用了一种名为TimSort的排序算法，就是归并排序的优化版本。从上文的图中可看出，每次合并操作的平均时间复杂度为O(n)，而完全二叉树的深度为|log2n|。总的平均时间复杂度为O(nlogn)。而且，归并排序的最好，最坏，平均时间复杂度均为O(nlogn)。

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号