承德网站,山东省住房和城乡建设厅领导名单,淘宝店铺网站策划,电商知识基础目录
前言
插入排序
直接插入排序
插入排序的时间复杂度
希尔排序 前言 在日常生活中#xff0c;我们不经意间会遇到很多排序的场景#xff0c;比如在某宝#xff0c;某东上买东西#xff0c;我们可以自己自定义价格是由高到低还是由低到高#xff0c;再比如在王者某…目录
前言
插入排序
直接插入排序
插入排序的时间复杂度
希尔排序 前言 在日常生活中我们不经意间会遇到很多排序的场景比如在某宝某东上买东西我们可以自己自定义价格是由高到低还是由低到高再比如在王者某耀中的每个英雄的荣耀战力都是由高到低进行排序的这些场景都用到了排序但是这些场景的底层都是用一个个排序算法来实现的本期开始我们就要学习数据结构中很重要的一个知识点-------排序。 几种常见的排序 注我们今后所有的排序都默认排升序。
本期我们主要讲解插入排序。
插入排序
直接插入排序 直接插入排序在现实生活中最常见的应用其实就是斗地主时我们一般会将牌拍好序然后根据自己的打法打牌大家先仔细想想再给牌整理时我们是怎样整理的呢当我们摸到第一张牌时此时它已经有序我们摸第二张牌时就会与第一张牌做比较然后发生交换使之成为我们想要的顺序当我们摸第三张牌时我们又会与最后一张牌与倒数第二张牌进行比较交换之后使牌的顺序成为我们想要的顺序之后每摸一张牌就按照此方法进行整理最后就会得到一个有序的牌列。这就直接插入排序的一个比较常见的应用场景。在数据结构中我们怎样实现直接插入排序呢 要实现直接插入排序我们可以先将直接插入排序分解为单趟排序然后再让每趟排序组合成为整个排序。
单趟排序 单趟排序的情景我们要将一个元素插入一个有序数组之中。可以类比我们摸了一张牌还没有插入手中的牌中但是手中的牌肯定已经是一个有序的牌序列了。 单趟排序的算法思想我们令有序的数组的最后一个元素的位置为end要插入的元素为x。要将x插入一个有序数组就得先让x与end位置上的元素进行比较因为我们是排升序所以如果x比a[end]小就要把a[end]向后挪动一个位置然后将end--然后在让x与此时end位置上的元素a[end]进行比较比较的原理同上直到将x插入到合理的位置那么怎样判断这样的一趟排序已经结束了呢其实就是x比当前end位置上的元素要大这是一个结束条件还有就是x比有序数组所有的元素都要小即就是要将x放在数组的第一个元素的位置上此时end已经到了数组第一个元素位置的前一个位置之前我们称此时end-1所以综上一趟排序的结束标志就是xa[end]或者end0 单趟排序代码实现
int end size - 1;int x;while (end 0){if (a[end] x){a[end 1] a[end];end--;}else {break;}}a[end 1] x; 到了这里我们单趟排序已经搞定了但是上面我们已经说了我们把整个插入排序分为了每趟排序那么怎样将每趟排序合并成为直接插入排序呢 每趟排序的关键点在于是把一个元素插入一个有序数组之中其实对于一个数组而言无论它是否是有序还是无序的其第一个元素毋庸置疑肯定是有序的这便是关键我们可以从第一个与元素开始把第一个元素当成一个有序数组此时第二个元素就是要插入有序数组中的元素那么此时第二哥元素插入由第一个元素组成的有序数组中就可以看成是一趟排序这趟排序之后第一个元素和第二个元素就组成了一个有序数组第三个元素插入由第一个和第二个元素组成的有序数组就可以看成第二趟排序由此依次进行多趟排序那么整个数组的多趟排序就最终组成了直接插入排序。 直接插入排序完整代码
void InsertSort(int* a, int size)
{assert(a);for(int end0;endsize-1;end){ int x a[end 1];while (end 0){if (a[end] x){a[end 1] a[end];end--;}else{break;}}a[end 1] x;}
}
int main()
{int arr[] { 10,9,8,7,6,5,4,3,2,1 };InsertSort(arr, sizeof(arr) / sizeof(int));for (int i 0; i sizeof(arr) / sizeof(int); i){printf(%d , arr[i]);}return 0;}
运行截图如下 注意 排序这里比较重要的就是边界的控制对于直接插入排序而言若数组的大小为size。end的初始值就是0end的最终值就是size-2x的初始位置就是1x的最终位置就是size-1。
以上便是直接插入排序的整个过程。
插入排序的时间复杂度 最好O(N),已经有序的数组要插入的元素比end位置上的元素大只用跟end位置上的元素比较一下。 最坏O(N^2)逆序要插入的元素比有序数组的所有元素都要小跟end位置和end位置之前的所有元素都要比较一下。 稳定性稳定。 希尔排序
希尔排序其实就是插入排序的进阶版我们知道一个数组越有序直接插入排序的时间复杂度越低希尔排序其实就是为了将一个无序的数组变得有序使插入排序变得更加简单。
希尔排序如图 希尔排序的思想先设置一个gap值先把整个数组的元素分成gap组即下标差gap的为一组然后对每一组按照直接插入排序的思想进行排序每一组的排序将完成一次预排序每完成一次预排序数组会变得比之前更加有序。我们再改变gap的值多次进行预排序当gap1时就是直接插入排序此时因为经历了多次预排序整个数组已经变得有序所以此时再用直接插入排序对整个数组完成最终的排序。 希尔排序的整体代码
void ShellSort(int* a, int size)
{int gap size;while (gap 1){gap / 2;//进行一趟预排序for (int i 0; i gap; i){//进行每组排序for (int end i; end size - gap; end gap){int x a[end gap];//进行单趟排序while (end 0){if (a[end] x){a[end gap] a[end];end - gap;}else{break;}}a[end gap] x;}}}
}
int main()
{int arr[] { 10,9,2,8,6,5,4,3,11,1 };ShellSort(arr, sizeof(arr) / sizeof(int));for (int i 0; i sizeof(arr) / sizeof(int); i){printf(%d , arr[i]);}return 0;
} 运行截图如下 当然上述的方法是把三组的排序是分开的每组自己排自己的但是下面这种方法就是三种排序我们再一次排序中就全部排序完成更为简洁但是没有第一种好理解可以理解为是第一种方法的进阶版本但是这种进阶版本是我们经常使用的。
进阶版本代码如下
void ShellSort(int* a, int size)
{int gap size;while (gap 1){gap / 2;//进行一趟预排序,将多组排序在一次排序中就完成了而不是按组进行排序for (int end 0; end size - gap; end){int x a[end gap];//进行单趟排序while (end 0){if (a[end] x){a[end gap] a[end];end - gap;}else{break;}}a[end gap] x;}}
}
int main()
{int arr[] { 10,19,2,8,6,0,4,3,11,1 };ShellSort(arr, sizeof(arr) / sizeof(int));for (int i 0; i sizeof(arr) / sizeof(int); i){printf(%d , arr[i]);}return 0;
}
以上便是希尔排序的整个过程。
希尔排序的时间复杂度 希尔排序的时间复杂度为 1.最好O(N),当整个数组为有序数组时复杂度最小。排序算法的时间复杂度的天花板就是O(N) 2.最坏总共分成了gap组每组大概就是size/gap个元素如果每组都逆序那么每组的复杂度又是一个12...size/gap的等差数列平均是O(N^1.3)。 稳定性不稳定。 插入排序的内容就是这些我们需要注意的仍然是算法中边界的控制在编写代码时我们可以自己画图去控制边界这是一个很好的方法。
好了本期的内容到此结束^_^
