顺序排列算法，简单选择排序算法解

文章目录 1. 插入排序1.1 插入排序的思想1.2 插入排序的算法步骤1.3 插入排序的代码1.4 插入排序的复杂度分析1.5 插入排序的稳定性分析 2. 折半插入排序2.1 折半插入排序的思想2.2 折半插入排序的算法步骤2.3 折半插入排序的代码2.4 折半插入排序的复杂度分析2.5 折半插入排序的稳定性分析 3. 希尔排序3.1 希尔排序的思想3.2 希尔排序的算法步骤3.3 希尔排序的代码3.4 希尔排序的复杂度分析3.5 希尔排序的稳定性分析

1. 插入排序 1.1 插入排序的思想 插入排序的思想就像一个人排序一手扑克牌一样，我们要从牌堆里拿走一张牌插入到手上的正确位置。我们保证手上已有的牌总是排好序的，需要插入的牌从右到左将它与手上已有牌进行比较，找到正确位置插入。可以选择不同的方法在手上已有顺序的牌中找到应该插入的位置； 从右往左挨个比较大小；折半插入，因为手上牌已经有序，所以可以通过二分法查找插入位置。 1.2 插入排序的算法步骤

??插入排序是指在待排序的元素中，假设前面n-1（其中n>=2）个数已经是排好顺序的，现将第n个数插到前面已经排好的序列中，然后找到合适自己的位置，使得插入第n个数的这个序列也是排好顺序的。按照此法对所有元素进行插入，直到整个序列排为有序的过程，称为插入排序。

??（1）将待排序序列的第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。

??（2）从头到尾依次扫描未排序的序列，将扫描到的每个元素插入有序序列的适当位置（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面）。

1.3 插入排序的代码

C++实现代码：

class Solution {public: vector sortArray(vector& nums) { insertSort(nums); return nums; } void insertSort(vector& nums) { for (auto i=1; i= 0 && nums[j] > cur) { nums[j+1] = nums[j]; –j; } nums[j+1] = cur; } }}; 1.4 插入排序的复杂度分析 时间复杂度：

最优时间复杂度：O(n)

最差时间复杂度：O(n^2)

平均时间复杂度：O(n^2)空间复杂度：O(1) 1.5 插入排序的稳定性分析

??插入排序是稳定排序算法。

2. 折半插入排序 2.1 折半插入排序的思想

??折半插入排序（binary insertion sort）是对插入排序算法的一种改进，由于排序算法过程中，就是不断的依次将元素插入前面已排好序的序列中。由于前半部分为已排好序的数列，这样我们不用按顺序依次寻找插入点，可以采用折半查找的方法来加快寻找插入点的速度。

2.2 折半插入排序的算法步骤

??折半插入排序是对直接插入排序的一种简单改进。

??直接插入的算法步骤是：当第i-1趟需要将第i个元素插入前面的 0 ~ i-1 个元素序列中时，总是需要从 i-1 个元素开始，逐个比较每个元素，直到找到它的位置。这样就没有利用到前面 0 ~ i-1 个元素已经有序的这个特性，所以折半插入排序就对这个问题进行了改进。

??对于折半插入排序而言，当需要插入第 i 个元素时，它不会逐个进行比较每个元素，而是：

（1）计算 0 ~ i-1 索引的中间点，也就是用 i 索引处的元素和 (0 + i-1) / 2 索引处的元素进行比较，如果 i 索引处的元素值大，就直接在 (0 + i-1)/2 ~ i-1 半个范围内进行搜索；反之在0~ (0+i-1)/2 这半个范围内进行搜索，即折半；

（2）在一半的范围内搜索时，按照（1）的方法不断进行折半查找，这样就可以将搜索范围缩小到1/2、1/4、1/8…，从而快速的确定插入位置。

2.3 折半插入排序的代码

C++代码实现：

class Solution {public: vector sortArray(vector& nums) { binInsertSort(nums); return nums; } int binSearch(vector &nums, int target, int low, int high) { while ( low target ) { high = mid – 1; } else { low = mid + 1; } } return low; } void binInsertSort(vector &nums) { for (auto i=1; i j; –k) { nums[k] = nums[k-1]; } nums[j] = cur; } }}; 2.4 折半插入排序的复杂度分析

??折半插入排序减少了关键字的比较次数，但是记录的移动次数不变，其时间复杂度与直接插入排序相同。

时间复杂度：

最优时间复杂度：O(n)

最差时间复杂度：O(n^2)

平均时间复杂度：O(n^2)空间复杂度：O(1) 2.5 折半插入排序的稳定性分析

??折半插入排序是稳定排序算法。

3. 希尔排序 3.1 希尔排序的思想

（1）希尔排序（shell sort）这个排序方法又称为缩小增量排序，是1959年jadwdm提出来的。该方法的基本思想是：设待排序元素序列有n个元素，首先取一个整数increment（dhmgsjx）作为间隔将全部元素分为increment个子序列，所有距离为increment的元素放在同一个子序列中，在每一个子序列中分别实行直接插入排序。然后缩小间隔increment，重复上述子序列划分和排序工作。直到最后取increment=1，将所有元素放在同一个子序列中排序为止。

（2）由于开始时，increment的取值较大，每个子序列中的元素较少，排序速度较快，到排序后期increment取值逐渐变小，子序列中元素个数逐渐增多，但由于前面工作的基础，大多数元素已经基本有序，所以排序速度仍然很快。

（3）增量increment的取法有各种方案。最初shell提出取increment=n/2向下取整，increment=increment/2向下取整，直到increment=1。但由于直到最后一步，在奇数位置的元素才会与偶数位置的元素进行比较，这样使用这个序列的效率会很低。后来Knuth提出取increment=n/3向下取整+1。还有人提出都取奇数为好，也有人提出increment互质为好。应用不同的序列会使希尔排序算法的性能有很大的差异。

3.2 希尔排序的算法步骤

??选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；

??按增量序列个数 k，对序列进行 k 趟排序；

??每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 活动：慈云数据爆款香港服务器，CTG+CN2高速带宽、快速稳定、平均延迟10+ms 速度快，免备案，每月仅需19元！！ 点击查看1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

3.3 希尔排序的代码

C++代码实现：

class Solution {public: vector sortArray(vector& nums) { shellSort(nums); return nums; } void shellSort(vector& nums) { int increment = nums.size(); do { increment = increment / 3 + 1; // decrease increment for (int i=increment; i = 0 && nums[j] > cur ) { nums[j+increment] = nums[j]; j -= increment; } nums[j+increment] = cur; } } while (increment > 1); }}; 3.4 希尔排序的复杂度分析 时间复杂度：

最优时间复杂度：O(n)

最差时间复杂度：O(n^2)

平均时间复杂度：O(nlogn)空间复杂度：O(1) 3.5 希尔排序的稳定性分析

??希尔排序算法是不稳定算法。因为相同大小的元素会划分到不同子序列，有的子序列中该元素会调整，有的可能不调整，此时相对顺序发生变换，所以希尔排序算法是不稳定的算法。

26513228

《顺序排列算法，简单选择排序算法解》来自互联网同行内容，若有侵权，请联系我们删除！