旅游网站设计方案,网站建设伍金手指下拉7,网站规划书包括哪些方面,东莞企业网站设计专业服务前言#xff1a;
常见排序方法如下#xff1a; 本篇将介绍4种排序方法#xff0c;分别为插入排序#xff0c;希尔排序#xff0c;选择排序#xff0c;堆排序#xff0c;并分别举例与讲解。
一. 插入排序
1.1 含义与动图分析
插入排序的思想是在有序区间的下一个位置…前言
常见排序方法如下 本篇将介绍4种排序方法分别为插入排序希尔排序选择排序堆排序并分别举例与讲解。
一. 插入排序
1.1 含义与动图分析
插入排序的思想是在有序区间的下一个位置插入一个新的元素之后将该新区间重新排序依次类推逐个完成整个区间的排序。
扑克整理手牌时就运用了这一思想。 动态理解 1.2 问题分析
问题
有序数组插入新元素并排序较为简单关键在于我们要排序的数组常常区间为无序那么如何使要插入元素之前的区间有序呢
分析
1.假定有序区间为[0,end]那么需要在[end1]处插入新元素。
2.因此end的最大值应该小于n-1否则end1会导致数组访问越界
3.由于最初的数组为乱序因此我们可以通过逐次增加有序区间的方式进行插入排序。
1.3 测试实现
代码示例如下
void InsertSort(int* arr, int n)
{//n-2for (int i 0; i n - 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;}
}时间复杂度分析
最坏情况数组降序排列 当我们对下标为i0in的tmp数据进行插入时会将其与前面i个数据比较i次总比较次数即123……(n-1)为O(n2)最好情况数组升序排列 当我们对下标为i0in的tmp数据进行插入时只会与其前面一个数据比较一次即总共(n-1)此为O(n)
空间复杂度O(1)
二. 希尔排序 在直接插入排序中我们发现元素越无序直接插入排序算法时间效率越低因为比较次数越多。特别是当数组为降序我们要排升序此时数组的相对无序程度达到了最大时间复杂度也到了最大。 2.1 含义与图片分析
希尔排序也称为递减增量排序算法是插入排序的一种高效率的改进版本。它通过将待排序的序列分割成若干子序列分别进行直接插入排序从而达到整个序列有序的目的。希尔排序的核心在于间隔序列的选择间隔序列通常是按某种规则递减至1的。 2.2 思路及相关结论
思路分析 1.希尔排序的核心在于对数组进行预排序值得注意的是预排序只是让数组相对有序而非达到真正的有序状态。 2.预排序的处理可以通过分组实现假设数组元素个数为n那么我们可以分为gap组每组元素就要n/gap个假设可以gap可以被n整除 3. 其排序思路与插入排序基本相同但是gap在每次排序之后需要令gap逐次减小当gap减小为1时就相当于插入排序。 2.3 测试实现
//希尔排序时间复杂度On^1.3)
void ShellSort(int* arr, int n)
{int gap n;while (gap 1){gap gap / 3 1;//保证最后一次gap一定为1for (int i 0; i n - gap; i){int end i;//n-gap-1int tmp arr[end gap];while (end 0){if (arr[end] tmp){arr[end gap] arr[end];end - gap;}else {break;}}arr[end gap] tmp;}}
}时间复杂度分析
外层循环gap每次除以2或3O(log2n) 或者O(log3n) 即O(logn)
内层循环 假设⼀共有n个数据合计gap组则每组为n/gap大致个在每组中插⼊移动的次数最坏的情况下为 S1 2 3 …… (n/gap-1)⼀共是gap组因此 总计最坏情况下移动总数为gap ∗ S
gap取值有以除3为例n/3 n/9 n/27 … 2 1 一一带入
当gap为n/3时移动总数为 n当gap为n/9时移动总数为 4n最后⼀趟数组已经已基本有序了gap1即直接插⼊排序移动次数就是n通过以上的分析可以画出这样的曲线图
因此希尔排序在最初和最后的排序的次数都为n即前⼀阶段排序次数是逐渐上升的状态当到达某⼀顶点时排序次数逐渐下降⾄n⽽该顶点的计算暂时⽆法给出具体的计算过程
内外循环综合来看外层循环总共log3n次内层循环的每次排序次数暂时无法精确计算所以其复杂度不好计算。 希尔排序时间复杂度不好计算因为 gap 的取值很多导致很难去计算因此很多书中给出的希尔排序的时间复杂度都不固定。《数据结构(C语⾔版)》—严蔚敏书中给出的时间复杂度为 总之希尔排序的时间复杂度综合来说是高于直接插入排序的范围大概是O(n1.3)~O(n2) 总结 希尔排序的时间性能优于直接插入排序的原因 在希尔排序开始时增量较大分组较多每组的记录数目少n小此时直接插入最好和最坏时间复杂度n2差距很小故各组内直接插入较快后来增量di逐渐缩小分组数逐渐减少而各组的记录数目逐渐增多但由于已经按di-1作为距离排过序使文件较接近于有序状态所以新的一趟排序过程也较快。 gap越大分组越快相对有序性越差
gap越小分组越慢相对有序性越好。
当gap1时相当于插入排序。
三. 选择排序
3.1 含义与动图分析
思路在整个数组内每次选出最大的值和最小的值分别位于末尾和开头升序情况若为降序则与之相反之后逐次缩小遍历选择空间。
动图图解 3.2 测试实现
void SelectSort(int* arr, int n)
{int begin 0;int end n - 1;while (begin end){int mini begin, maxi begin;for (int i begin 1; i end; i){if (arr[i] arr[maxi]){maxi i;}if (arr[i] arr[mini]){mini i;}}//mini begin//maxi endSwap(arr[mini], arr[begin]);Swap(arr[maxi], arr[end]);begin;--end;}}注意上述代码存在问题 在定义maxi和mini时我们都初始化为了begin处但当begin处的数据即为最大值时排序就存在了问题。 分析 mini正常完成交换之后begin处的最大值也被交换了过去那么此时end处的交换就会失败并不能完成正常功能因为maxi始终位于begin处而此时begin处的值已经变为了最小值。 改进如下 //避免maxi begini都在同一个位置begin和mini交换之后maxi数据变成了最小的数据if (maxi begin){maxi mini;}此时就可以解决最大值位于begin处的情况。
完整代码如下
void Swap(int* x, int* y)
{int tmp *x;*x *y;*y tmp;
}void SelectSort(int* arr, int n)
{int begin 0;int end n - 1;while (begin end){int mini begin, maxi begin;for (int i begin 1; i end; i){if (arr[i] arr[maxi]){maxi i;}if (arr[i] arr[mini]){mini i;}}//mini begin//maxi end//避免maxi begini都在同一个位置begin和mini交换之后maxi数据变成了最小的数据if (maxi begin){maxi mini;}Swap(arr[mini], arr[begin]);Swap(arr[maxi], arr[end]);begin;--end;}
}四. 堆排序
4.1 基本思路分析
由于堆具有相对有序的特性要么为大堆要么为小堆其相当于完成了希尔排序的预排序工作因此可以利用建堆之后再向上或向下调整来进行排序。
4.2 测试实现
排升序建大堆
分析
1.此时我们常常有一个误区认为小堆与升序类似应该建立小堆。
2. 然而在排序的时候时间消耗过于庞大因为在挪动元素时会把堆内的序列和关系打乱因此应该建大堆然后利用算法进行调整。
代码示例如下
void AdjustDown(int* a, int n, int parent)
{// 先假设左孩子小int child parent * 2 1;while (child n) // child n说明孩子不存在调整到叶子了{// 找出小的那个孩子if (child 1 n a[child 1] a[child]){child;}if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child parent * 2 1;}else{break;}}
}void HeapSort(int* a, int n)
{// 向下调整建堆 O(N)for (int i (n - 1 - 1) / 2; i 0; i--){AdjustDown(a, n, i);}// O(N*logN)int end n - 1;while (end 0){Swap(a[0], a[end]);AdjustDown(a, end, 0);--end;}
}
排降序建小堆
思路于此相同在此不做过多阐述。
代码示例如下
void AdjustDown(int* a, int n, int parent)
{// 先假设左孩子小int child parent * 2 1;while (child n) // child n说明孩子不存在调整到叶子了{// 找出小的那个孩子if (child 1 n a[child 1] a[child]){child;}if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child parent * 2 1;}else{break;}}
}void HeapSort(int* a, int n)
{// 向下调整建堆 O(N)for (int i (n - 1 - 1) / 2; i 0; i--){AdjustDown(a, n, i);}// O(N*logN)int end n - 1;while (end 0){Swap(a[0], a[end]);AdjustDown(a, end, 0);--end;}
}
小结本文主要讲解了四种排序方法下篇将会继续讲解排序的其他方式欢迎各位大佬前来斧正支持
