数据结构之插入排序和希尔排序实例讲解
程序员文章站
2022-10-26 10:53:46
一、插入排序
<1>介绍:插入排序(insertion sort)的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相...
一、插入排序
<1>介绍:插入排序(insertion sort)的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到o(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。
<2>思路:
①从第一个元素依次进行以下操作:对于当前元素可以认为当前元素之前的部分已经有序;取出当前位置的下一个元素作为要排序的值,在已经排序的元素序列中从后向前扫描,如果该元素(已排序)大于新元素,将该元素移到下一位置;直到找到已排序的元素小于或者等于新元素的位置,将新元素插入到该位置中;
②分别把下标从0到数组元素个数-1的元素作为end,进行以上操作;每次循环的目的就是为了将当前tmp值放置在之前序列中该放的位置上,使得当前部分序列有序。
<3>实现:
void insertsort(int* arr, int sz) { for (int i = 0; i < sz - 1; i++) { int end = i; int tmp = arr[end + 1]; while (end >= 0) { if (arr[end] > tmp) { arr[end + 1] = arr[end]; end--; } else break; } arr[end + 1] = tmp; } }
<4>图示过程:
二、希尔排序
<1>介绍:希尔排序,也称递减增量排序算法,是插入排序的一种高速而稳定的改进版本。
希尔排序是基于插入排序的以下两点性质而提出改进方法的:
1、插入排序在对几乎已经排好序的数据操作时, 效率高, 即可以达到线性排序的效率;
2、但插入排序一般来说是低效的, 因为插入排序每次只能将数据移动一位。
<2>思路及排序效果:
①:先将整个待排元素序列分割成若干个子序列(由相隔某个“增量”的元素组成的)分别进行直接插入排序;
②:然后依次缩减增量再进行排序,待整个序列中的元素基本有序(增量足够小)时,再对全体元素进行一次直接插入排序。
大致思路和插入排序相同,区别在于希尔排序可以给定一个gap值,也就是间隔,可以预先先将间隔gap的序列对应有序,再不断缩小gap值,到最后一趟依次比较。
<3>实现:
void shellsort(int* arr, int sz) { int gap = 3; while (gap > 1) { gap = gap / 3 + 1; for (int i = 0; i < sz - gap; i++) { int end = i; int tmp = arr[end + gap]; while (end >= 0) { if (tmp < arr[end]) { arr[end + gap] = arr[end]; end -= gap; } else break; } arr[end + gap] = tmp; } }
<4>图示过程:
上一篇: 稀饭热量到底高不高,吃稀饭有什么好处呢?
下一篇: 什么是孕妇瑜伽 孕妇练瑜伽的好处有哪些