Java 理论概念·经典排序算法

作者 : jamin 本文共1371个字,预计阅读时间需要4分钟 发布时间: 2020-10-18 共1178人阅读

经典排序算法

重温排序算法,动画详见:Magicsort

插入排序

插入排序是一种简单的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用 in-place 排序,因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。

插入排序算法的运作如下:

  1. 从第一个元素开始,该元素可以认为已经被排序。
  2. 取出下一个元素,在已经排序的元素序列中从后向前扫描,如果该元素大于新元素,将该元素移到下一位置。
  3. 重复步骤 2,直到找到已排序的元素小于或者等于新元素的位置,将新元素插入到该位置后。
  4. 重复步骤 2~3,直到完成排序。

插入排序平均时间复杂度 O(n^2),在最好情况下复杂度为 O(n),在最坏情况下复杂度为 O(n^2)。

经典插入算法

经典插入算法:将数列分为有序区和无序区两部分,在每轮循环中从无序区选择一个最小值并入有序区,新增一位有序区同时减少一位无序区,n – 1 轮排序后全部变为有序区,从而完成排序。

public class InsertSort {

    public static void main(String[] args) {
        int[] array = new int[]{2, 3, 1, 4, 7, 8, 3, 5, 2, 6, 8, 9, 1};
        insertSort(array);
        for (int value : array) {
            System.out.print(value + " ");
        }
    }

    /**
     * 插入排序
     *
     * @param array 待排序数组
     */
    public static void insertSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            // 待插入的元素
            int needInsert = array[i];
            // 开始比较的索引
            int index = i - 1;
            while (index >= 0 && array[index] > needInsert) {
                // 将该位置的元素进行后移
                array[index + 1] = array[index];
                // 再比较该位置前一个元素
                index--;
            }
            // 当前位置满足条件
            array[index + 1] = needInsert;
        }
    }

}

二分插入算法

二分插入算法:查找插入位置时使用二分查找的方式,在插入值之前,先在有序区中找到待插入值需要比较的左边界,在数据长度较大时,可以有效减少每轮排序中的查找插入位置的次数。

public class InsertSort {

    public static void insertSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            // 待插入的元素
            int needInsert = array[i];
            // 左右边界
            int left = 0;
            int right = i - 1;

            // 找到待插入数据的合适位置
            while (left <= right) {
                int middle = (left + right) / 2;
                if (needInsert < array[middle]) {
                    right = middle - 1;
                } else {
                    left = middle + 1;
                }
            }

            // 将右边比待插入数据大的数都右移一位
            for (int j = i - 1; j >= left; j--) {
                array[j + 1] = array[j];
            }
            // 当前位置满足条件
            array[left] = needInsert;
        }
    }

}
本站所提供的部分资源来自于网络,版权争议与本站无关,版权归原创者所有!仅限用于学习和研究目的,不得将上述内容资源用于商业或者非法用途,否则,一切后果请用户自负。您必须在下载后的24个小时之内,从您的电脑中彻底删除上述内容资源。如果上述内容资对您的版权或者利益造成损害,请提供相应的资质证明,我们将于3个工作日内予以删除。本站不保证所提供下载的资源的准确性、安全性和完整性,源码仅供下载学习之用!如用于商业或者非法用途,与本站无关,一切后果请用户自负!本站也不承担用户因使用这些下载资源对自己和他人造成任何形式的损失或伤害。如有侵权、不妥之处,请联系站长以便删除!
金点网络 » Java 理论概念·经典排序算法

常见问题FAQ

免费下载或者VIP会员专享资源能否直接商用?
本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。
是否提供免费更新服务?
持续更新,永久免费
是否经过安全检测?
安全无毒,放心食用

提供最优质的资源集合

立即加入 友好社区
×