排序算法 - 希尔排序（插入）

谁践踏了优雅 2022-12-04 07:32 173阅读 0赞

# 排序算法概览 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70_pic_center]

# 插入排序 #

工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

/** * 插入排序原理：寻找未排序后的第一个位置，插入已排序中的对应位置 */
        public void insertSort(int[] arr) { 
            int length = arr.length;
            int cur;
            for (int i = 1; i < length; i++) { 
                cur = arr[i];
                int changeIndex = i - 1;
                while (changeIndex >= 0 && arr[changeIndex] > cur) { 
                    arr[changeIndex + 1] = arr[changeIndex];
                    changeIndex--;
                }
                arr[changeIndex+1] = cur;
            }
        }

# 希尔排序 #

希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

> 减少往后移动次数

/** * 获取增量 减少往后移动次数 * * @param arr */
        public void ShellSort(int[] arr) { 
            int length = arr.length;
            int gap = length / 2;
            int cur;
            while (gap > 0) { 
                for (int i = gap; i < length; i++) { 
                    cur = arr[i];
                    int changeIndex = i - gap;
                    while (changeIndex >= 0 && arr[changeIndex] > cur) { 
                        arr[changeIndex + gap] = arr[changeIndex];
                        changeIndex -= gap;
                    }
                    arr[changeIndex + gap] = cur;
                }
                gap /= 2;
            }
        }

# 问题 #

如何将一副扑克牌按花色排序（花色顺序是黑桃、红桃、梅花和方片），限制条件是所有牌都是背面朝上排成一列，而你一次只能翻看两张牌或者交换两张牌（保持背面朝上）。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/296b15d2742c47a98bd5d1fc072fb2bd.png