淮安市城市建设档案馆网站,科技通信网站模板下载,深圳高端企业官方网站建设,万网云虚拟主机上传网站目录
前言#xff1a;
直接插入排序
直接插入排序代码实现
直接插入排序特性总结
希尔排序
希尔排序代码实现
希尔排序特性总结
直接选择排序
直接选择排序代码实现
直接选择排序特性总结
堆排序
堆的向下调整算法
建堆
堆排序代码实现
堆排序特性总结 前言
直接插入排序
直接插入排序代码实现
直接插入排序特性总结
希尔排序
希尔排序代码实现
希尔排序特性总结
直接选择排序
直接选择排序代码实现
直接选择排序特性总结
堆排序
堆的向下调整算法
建堆
堆排序代码实现
堆排序特性总结 前言 排序即使得一串记录按照其中某个或某些关键字的大小递增或递减的排列起来的操作 排序分为内部排序和外部排序稳定排序和非稳定排序 内部排序数据元素全部放在内存中的排序 外部排序数据元素太多不能同时存储于内存中根据排序过程的要求不能在内外存之间移动数据的排序 稳定性假定在待排序的序列中如果元素a位于元素b前面,且ab,经过某种排序方法进行排序之后元素a依然位于元素b前面那么这种排序方法就是稳定的否则就是不稳定的 衡量一个排序方法的好坏可以根据时间复杂度与空间复杂度稳定性等综合考虑 常见的排序算法 本篇主要详细介绍前四种排序均以升序为例
直接插入排序
直接插入排序的基本思想 对于一个长度为n的数组a,当插入第 i (i1)个元素时前面的a[0],a[1],......,a[i-1]已经有序此时只需将a[i]元素与a[i-1],a[i-2],.....的元素进行比较找到插入位置先将原来位置上的元素依次向后移动然后在插入位置插入元素a[i]; 具体步骤如下 将待排序的序列分为有序区和无序区初始时有序区只有一个元素即序列的第一个元素无序区包括除第一个元素外的所有元素从无序区中取出第一个元素将其插入到有序区中的适当位置使之成为新的有序区重复步骤2直到无序区中的所有元素都插入到有序区中 单个数据必然有序所以将元素3划分为有序区其他元素均位于无序区假设有序区最后一个元素下标为end为防止移动过程中插入元素被覆盖,用tmp保存插入元素的数值 寻找插入位置将tmp与数组有序区尾元素a[end]进行比较若a[end]tmp,先将有序区尾元素向后移动一位然后通过控制end即end每次自减1,向左查找下一位按此循环直至a[end]tmp出现或者end -1; 此时单趟排序已完成end继续回到有序区的尾元素的位置进行下一趟排序若a[end]tmp,直接插入到end的下一位置即a[end1]tmp; ....... 直接插入排序代码实现
void InsertSort(int* a, int n)
{//先写单趟再写整体;for (int i 0; i n-1 ; i){int end i;int tmp a[end 1];while (end 0){if (tmp a[end]){//向后挪动一位a[end 1] a[end];end--;}else{//考虑极端情况当插入的数值小于有序区数组每个元素不断向前挪动过程中直至end-1;//出现插入的数值大于a[end];break;}}a[end 1] tmp;}
} 直接插入排序特性总结
1.时间复杂度 最好情况就是全部有序此时只需遍历一次最好的时间复杂度为O(n) 最坏情况全部逆序内层每次遍历已排序部分最坏时间复杂度为O(n^2) 综上因此直接插入排序的平均时间复杂度为O(n^2) 2. 空间复杂度 额外开辟的空间为常数个所以空间复杂度为O(1) 3.算法稳定性 稳定性指相同元素的前后顺序是否改变当插入元素小于a[end]时插入到比它大的数前面所以直接插入排序是稳定的 希尔排序 希尔排序的基本思想 希尔排序是一种改进的插入排序算法其基本思想是将待排序的序列按照一定的间隔(gap)分成若干个子序列通过插入排序对大间隔的子序列进行排序使得整个序列基本有序然后逐步缩小间隔重复上述操作直到间隔gap为1最后对整个序列进行直接插入排序每次排序让数组接近有序的过程叫做预排序最后一次排序为直接插入排序 1. 取间隔gap3对下述序列进行分组该序列被分成3组每组之间都是以3的等差数列 2. 对每一组进行插入排序得到如下数组 3.缩小间隔取间隔gap2对数组进行分组数组被分成2份每组之间都是2的等差数列; 4. 对每一组进行插入排序得到如下数组 5.缩小间隔取间隔gap1对数组进行分组数组相当于没有分组进行插入排序当gap1时为直接插入排序 如何选择希尔增量gap? 最初Shell提出的增量是 gap [n / 2]每一次排序完让增量减少一半gap [ gap / 2]直到gap 1时排序变成了直接插入排序后来Knuth提出的gap [gap / 3] 1每次排序让增量成为原来的三分之一加一是防止gap 3时gap [gap / 3] 0的发生导致希尔增量最后不为1无法完成插入排序 上述无论哪一种主张都没有得到证明本文代码实现部分采取gap[n/2],gap[gap/2] 希尔排序代码实现
长度为n的数组间距为gap分为一组共计gap组定义遍历变量i首先遍历第一组数据i从0开始遍历i每次移动gap步由于数组尾元素下标为n-1则igapn-1,为防止数组越界访问i最后访问位置为 n-1-gap ; ...... 第一组排序代码如下 for (int i 0; i n - gap; i gap){int end i;int tmp a[end gap];while (end 0){if (tmp a[end]){a[end gap] a[end];end - gap;}else{break;}}a[end gap] tmp;}第一组排序完成外面套一层循环遍历其余组便可完成第一趟排序定义循环变量jj从0开始每次自增1一共有gap组j小于gap即可排序其他组 for (int j 0; j gap; j){for (int i j; i n - gap; i gap){int end i;int tmp a[end gap];while (end 0){if (tmp a[end]){a[end gap] a[end];end - gap;}else{break;}}a[end gap] tmp;}然后缩小增量 gap gap /2 直到gap 1继续插入排序直到排序完成
void ShellSort(int* arr, int n)
{int gap n;//预排序:分组排序,间距为gap分为一组,共计gap组;//最后进行直接插入排序即gap1;while (gap 1){gap gap / 2;//其次排序其余gap组,一次预排序完成,会进行多次预排序;for (int j 0; j gap; j){//首先排序以第一个元素为起点,间距为gap的第一组;相当于整个数组排序;for (int i j; i n - gap; i gap){//保证[0,end]有序,每个元素间隔为gap,控制[0,endgap]有序;int end i;int tmp arr[end gap];while (end 0){if (tmp arr[end]){arr[end gap] arr[end];end end - gap;}//else会出现俩种情况;//第一种为第一个元素以后且间距为gap的某个位置插入;//第二种会不断满足tmparr[end],直至end-gap;else{break;}//end-gap的位置直接将arr[endgap]tmp;arr[end gap] tmp;}}}}
}
希尔排序特性总结
1.时间复杂度
希尔排序的时间复杂度取决于增量序列的选择由于gap取值有多种方法导致希尔排序的时间复杂度并不固定一般来说希尔排序的平均时间复杂度界于 O(n)到 O(n^2)之间 最好的时间复杂度为 O(n^1.3) 2. 空间复杂度 希尔排序的空间复杂度为O(1)因为在希尔排序时是对原数组进行直接排序并没有创建其他新的数组 3.算法稳定性 希尔排序是一种非稳定的排序算法希尔排序的精髓在于按照某个增量来划分子序列实现跳跃式移动来提高排序效率而也正是这种跳跃性带来了不稳定性。如果不同子序列中有相等的数但它们不在同一子序列中可能会因为子序列内部排序而改变原有的顺序。 直接选择排序 直接选择排序的基本思想 每一次从待排序的数据元素中选出最小或最大的一个元素通过交换存放在序列的起始位置或最后一个位置直到全部待排序的数据元素排完 具体来说就是在待排序序列中首先找到最小的元素和最大的元素然后将最小的元素与序列的第一个元素交换位置最大的元素与序列的最后一个元素交换位置接着在剩下的元素中找到最小的元素与最大的元素将最小元素与序列的第二个元素交换位置最大元素与序列的倒数第二个元素交换位置以此类推直到序列中只剩一个元素为止 具体步骤如下 遍历整个序列找到最小的元素与最大的元素 将最小的元素与序列的第一个元素交换位置最大的元素与序列尾元素交换位置 序列遍历范围从第二个元素开始到倒数第二个元素遍历序列找到剩余元素中的最 小元素与最大元素 将最小的元素与序列的第二个元素交换位置最大的元素与序列倒数第二个元素交换位置 重复上述步骤直到整个列表都被排序 1. 定义变量beginend确定遍历范围[begin,end] 定义maxi,mini记录遍历范围内的最大值下标 和最小值下标最初maxi mini 指向遍历范围内的首元素当在遍历范围内查找到最大值最小值时更新maxi,mini 2. 遍历结束后查找到最大值最小值此时将最小的元素与遍历范围内的第一个元素交换位置最大的元素与遍历范围内的尾元素交换位置 3.交换完成后begin自增1end自减1确定新的遍历范围同时maxi mini 指向遍历范围内的首元素当在遍历范围内查找到最大值最小值时更新maxi,mini 4. 交换时先将遍历范围内的最小值与遍历范围的首元素交换其次将遍历范围内的最大值与遍历范围内的尾元素交换 当出现上述情况即出现 最大的位置恰好位于begin位置说明mini是和最大的交换位置这个时候max的位置就发生了变换 maxi变到了mini的位置需要 更新max的位置否则易导致错误,正确做法如下图所示 ...... 直接选择排序代码实现
//交换
void swap(int* p, int* q)
{int tmp *p;*p *q;*q tmp;
}
//选择排序
void SelectSort(int* arr, int n)
{int begin 0;int end n - 1;while (begin end){//单趟排序,将[begin,end]范围内最大与最小的数据调整于左右;int maxi begin;//最大元素的下标,假设最大元素在最左边;int mini begin;//最小元素的下标,假设最小元素在最左边;for (int i begin1; i end; i){if (arr[i]arr[maxi]){maxi i;}if (arr[i]arr[mini]){mini i;}}swap(arr[begin], arr[mini]);//如果最大元素的位置位于begin位置说明mini和最大的交换位置;//maxi的位置变化到mini的位置要更新maxi;if (maxi begin){maxi mini;}swap(arr[end], arr[maxi]);end--;begin;}
}
直接选择排序特性总结
1.时间复杂度
数据的比较次数为n-1n-2n-3......1 n*(n-1)/2数据的交换次数为n-1所以 时间复杂度为O(n^2) 2. 空间复杂度 选择排序的空间复杂度为O(1)因为在选择排序时是对原数组进行直接排序并没有创建其他新的数组 3.算法稳定性 选择排序是一种非稳定的排序算法具体参见上图红五与白五排序前后的位置 堆排序 大根堆任意父节点的数值大于等于孩子节点的数值a[i] a[2i1] a[i] a[2i2]) 对堆中的结点按层进行编号映射到数组便可得其存储结构 小根堆任意父节点的数值小于等于孩子节点的数值a[i] a[2i1] a[i] a[2i2]) 对堆中的结点按层进行编号映射到数组便可得其存储结构 结论 大堆堆顶数据的数值最大 小堆堆顶数据数值最小 堆排序是利用大堆或者小堆堆顶数据最大或最小的特性来进行排序的所以我们排序的对象必须是大堆或者小堆但给定的数据不一定是大堆或者小堆所以必须先建堆
堆的向下调整算法 建堆的核心为堆的向下调整算法堆的向下调整算法的基本思想 从根结点开始利用假设法寻找同一高度处值最小的孩子根据其左右子树为小堆还是大堆按照小堆或大堆的原则将其交换若为小堆父节点处的数值大于孩子结点出的数值则交换彼此位置若为大堆父节点处的数值小于孩子结点出的数值则交换彼此位置直至叶节点为止或出现满足其逻辑上不满足大小堆的数值为止 //堆的向下调整算法(建大堆)
void AdjustDown(int* nums, int n, int parent)
{//假设法求同一深度左右孩子最小的一个,假设左孩子为最小int child parent * 2 1;while (childn){if (child 1 n nums[child] nums[child 1]){child;}//无论左右孩子,child为最大,调整为大堆;if (nums[child] nums[parent]){swap(nums[child], nums[parent]);parent child;child 2 * parent 1;}else{break;}}
}
建堆 由于向下调整算法的使用前提是左右子树必须是大堆或者小堆从倒数第一个非叶子结点开始调整一定能够保证待排序序列的左右子树都是大堆或者小堆此时即可看作大堆又可以看作小堆根据需要进行调整即可 倒数第一个非叶子结点恰好是最后一个结点的父亲最后一个结点的下标为n-1套用公式parent(child-1)/2则该结点下标为:n-1-1) / 2 //建堆 升序建大堆降序建小堆for (int i (n - 1 - 1) / 2; i 0; i--){AdjustDown(arr, n, i);}详细图解可参考数据结构之堆-CSDN博客 堆排序的基本思想 将待排序序列构造成一个大根堆整个序列的最大值就是堆顶的根节点将堆顶元素与数组尾元素进行交换此时数组尾元素就为最大值将数组尾元素不看做堆里面的数据前n-1个数继续向下调整为堆选出次大的数和倒数第二个位置的数交换反复执行得到升序序列 堆排序代码实现
void HeapSort(int* arr, int n)
{//建堆for (int i (n - 1 - 1) / 2; i 0; i--){AdjustDown(arr, n, i);}//排序int end n - 1;while (end 0){swap(arr[0], arr[end]);AdjustDown(arr, end, 0);end--;}
}堆排序特性总结
1.时间复杂度 堆向下调整算法的时间复杂度为O(logn)堆排序由建堆与排序俩部分组成建堆的时间复杂度O(n) ; 假设节点数为n需要进行n-1次交换每次调整的时间复杂度O(logn)总的时间复杂度为(n-1)*O(logn)所以 堆排序的时间复杂度为 O(n)O(n*logn)O(n*logn) 2. 空间复杂度 堆排序的空间复杂度为O(1)因为在堆排序时是对原数组进行直接排序并没有创建其他新的数组 3.算法稳定性 堆排序是一种非稳定的排序算法堆排序时需要交换堆顶和堆尾的数据交换时两个相等的数据在序列中的相对位置就可能发生改变所以堆排序不是一个稳定排序
