网站推广主要怎么做哈尔滨市香坊区建设局网站

当前位置： 首页 > news >正文

网站推广主要怎么做,哈尔滨市香坊区建设局网站,江西专业网站建设,如何做百万格子网站文章目录 一、排序的相关概念二、排序类型三、排序算法实现插入排序1.直接插入排序2.希尔排序 选择排序3.简单选择排序4.堆排序 交换排序5.冒泡排序6.快速排序递归实现非递归实现 7.归并排序递归实现非递归实现 8.计数排序 四、总结 一、排序的相关概念 排序#xff1a;根据数… 文章目录 一、排序的相关概念二、排序类型三、排序算法实现插入排序1.直接插入排序2.希尔排序 选择排序3.简单选择排序4.堆排序 交换排序5.冒泡排序6.快速排序递归实现非递归实现 7.归并排序递归实现非递归实现 8.计数排序 四、总结 一、排序的相关概念 排序根据数据中关键字的大小来进行升序或者降序排列。比如按照英文字母顺序排序按照商品价格或者销量来排序等。 稳定性如果存在两个或多个相同的数据若经过排序后它们的相对次序保持不变则称这种排序算法是稳定的否则就是不稳定的。 内部排序数据元素全部放在内存中的排序。 外部排序数据元素太多不能同时放在内存中根据排序过程的要求不能在内外存之间移动数据的排序。 本篇介绍的是内部排序。 二、排序类型 三、排序算法实现 可用各种排序算法跑这个OJ—排序OJ链接 插入排序 1.直接插入排序 基本思想将待排序的元素逐个插入到一个已经排好序的有序序列中直到所有元素插入完为止得到一个新的有序序列 。 初始序列是无序的怎么将待排元素插入有序序列呢 第一个元素本身可以看做一个有序序列所以从第二个元素开始从后往前遍历比较插入前面已经排好的有序序列中。将大于该元素的所有元素位置向后挪动一位在比较的过程中边比较边挪动。 以升序为例
可以发现假设待排序的序列长度为n插入排序需要进行n-1趟。 时间复杂度O(N2)。趟数为n-1每趟待排序元素需要在前面的有序序列中从后往前比较挪动数据。 最好情况O(N)有序判断一次直接break出来总共n-1趟每趟不用挪动数据量级为。 最坏情况O(N2)逆序每趟都头插次数123…N-1所以时间复杂度量级是。 元素集合越接近有序直接插入排序算法的效率越高。 空间复杂度O(1)。 没有使用额外空间。 稳定性稳定。 如果是大于等于某个位置的元素则在其后面插入相对位置不变。 //插入排序 稳定 时间复杂度O(N^2) 空间复杂度O(1) void InsertSort(int* a, int n) {for (int i 1; i n; i){int end i - 1;//有序序列的末尾位置int x a[i];//待排序元素//将x插入到[0, end]区间中并保持有序while (end 0){if (x a[end]){a[end 1] a[end];//往后挪一个位置end–;}else{break;}}//while循环结束有两种情况://1.end -1也即x比前面所有数都小;//2.x a[end] 这两种都是在end后面插入a[end 1] x;} }2.希尔排序 希尔排序法又称缩小增量法。是对插入排序的优化方案效率比直接插入排序要高。 基本思想将待排序列以间隔gap划分为gap个不同的组对同组内的元素进行直接插入排序然后缩小gap重复上述分组和排序直到gap1也就是直接插入排序就会得到一个有序序列。 gap取多少合适 gap初始值一般取n / 2每趟排序完gap / 2直到gap1即直接插入排序此时序列接近有序直接插入效率O(N)。gap也可以每次 ÷ 3只要保证gap最后一次能取到1。 排升序gap越大大的数更快到后面小的数更快到前面但是越不接近有序gap越小越接近有序gap1时就是直接插入排序。 时间复杂度平均为O(N1.3)。希尔排序的时间复杂度至今还没有精确的分析结果经过大量的实验推出n在某个特定范围内希尔排序的比较和移动次数约为N1.3。 空间复杂度O(1)。 没有使用额外空间。 稳定性不稳定。 希尔排序是分组排序的且每个组内的数据不连续无法保证相同数据的相对位置不被改变。比如上图中紫色4和橙色4在第一趟排序后相对位置就发生了变化所以希尔排序是不稳定排序。 //希尔排序 不稳定 效率比直接插入排序高 void ShellSort(int* a, int n) {//gap 1 预排序//gap 1 直接插入排序int gap n;while (gap 1){//gap gap / 3 1;//也可以,除3后别忘了1否则gap为2时除3结果为0gap / 2;for (int i gap; i n; i){int end i - gap;int tmp a[i];//将x插入到[0, end]区间中保持有序while (end 0){if (tmp a[end]){a[end gap] a[end];//往后挪一个位置方便x插入end - gap;}else{break;}}a[end gap] tmp;}} }选择排序 3.简单选择排序 基本思想每次从剩下的待排序列中标记最小最大值的下标位置遍历完后存放到未排序列的起始位置也是已排好的序列的下一个位置直到全部待排序的数据排完。 实际上我们每趟可以选出两个值一个最大值一个最小值然后分别与序列的起始和末尾元素交换。这样排序的趟数可以减少一半但比较和交换的次数会×2整体效率没有太大变化。 时间复杂度O(N2)。一共选择n趟每趟与n-1个数进行比较如果是每次同时选出最大值和最小值一共需要n/2趟每趟比较2×(n-1)次量级都是O(N2)。 选择排序没有最好情况和最坏情况不管有序还是逆序都需要进行O(N2)次比较。所以选择排序的性能很差。因为不管是有序还是逆序选择排序的效率都是最差的O(N2)。 空间复杂度O(1)。 没有使用额外空间。 稳定性不稳定。 因为每次是将待排序列的起始位置与序列中最小值或最大值进行交换只保证了最小值的稳定性但起始位置的稳定性可能会被破坏。如果同时找出最大值并交换例如图中一样最小值表示的元素的稳定性也可能会被破坏比如上图中第二趟排序4的相对位置就发生了变化 //选择排序 不稳定 时间复杂度O(N^2) 空间复杂度O(1) void SelectSort(int* a, int n) {int l 0, r n - 1;while (l r){int minPos l, maxPos l;//标记最小值和最大值的下标for (int i l 1; i r; i){if (a[i] a[minPos])minPos i;if (a[i] a[maxPos])maxPos i;}//C语言没有库函数交换函数需要自己写Swap(a[l], a[minPos]);//如果最大值maxPos与左边界l重合在l与minPos交换后最大值转移到了minPos位置if (l maxPos)maxPos minPos;Swap(a[r], a[maxPos]);l;r–;} }4.堆排序 堆排序在数据结构——堆中已经详细讲过了这里可能讲的没有那么细致。想详细了解堆的具体原理和使用可以看看这篇博客。 堆排序是利用数据结构堆Heap的特性所设计的一种算法是选择排序的一种。它是通过堆来选择数据。 基本思想 依次将将堆顶的数据与堆尾的数据交换然后向下调整成堆重复上述步骤直到数据完全有序。比如一个大根堆我们取出堆顶元素最大数与最后一个数交换交换后的最大数不看作在堆里面那么堆顶元素的左右子树仍满足堆的性质堆的结构并没有被破坏然后堆顶元素向下调整成堆即可选出第二大的数以此类推到最后一个元素就可以成功实现堆排序了。 升序建大堆 降序建小堆 时间复杂度O(N*logN)。向下调整建堆的时间复杂度为O(N)过程在数据结构堆篇堆顶元素一共进行n-1次交换每次交换后向下调整为O(logN)所以最大量级是O(N*logN)。 堆排序也没有最好情况和最坏情况堆排序不受初始序列顺序的影响有序或者逆序时间复杂度都是O(NlogN)。 空间复杂度O(1)。 没有使用额外空间。 稳定性不稳定。 建堆时数据的相对顺序就可能被改变在选数时堆顶与堆尾数据交换也可能导致稳定性被破坏。 //C语言没有库函数交换函数需要自己写 void Swap(int x, int* y) {int tmp *x;*x *y;y tmp; } //堆排序向下调整排升序建大堆 void AdjustDown(int a, int n, int parent) {int child 2 * parent 1;//先赋值左孩子while (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 2 * parent 1;}else{break;}} }//堆排序 不稳定 时间复杂度O(NlogN) void HeapSort(int a, int n) {//倒着调整从最后一个非叶子结点开始向下调整建堆 效率O(N)for (int i (n - 2) / 2; i 0; i–){AdjustDown(a, n, i);}//O(NlogN)int end n - 1;//堆的有效长度while (end 0){Swap(a[0], a[end]);//堆顶与堆尾元素交换AdjustDown(a, end, 0);//堆顶再向下调整范围[1,end]end–;} }交换排序 5.冒泡排序 基本思想从前往后遍历序列每相邻两个数比较大小前一个比后一个大就交换直到将最大元素交换到末尾位置继续从前往后遍历重复上述操作直到所有元素有序。 冒泡排序和选择排序一样都非常容易理解也不上图演示了画图太费时间一切都在代码中。 时间复杂度O(N2)。一共n趟每趟比较交换次数递减总共比较123…n-1次量级为O(N2)。 最好情况O(N) 有序情况下只用进行一趟比较flag标记就退出循环。 最坏情况O(N2)每趟都进行交换。 空间复杂度O(1)。 没有使用额外空间。 稳定性稳定。 前后两个元素相同则不用交换相对位置没有改变。 //冒泡(交换)排序 稳定 时间复杂度O(N^2) void BubbleSort(int a, int n) {for (int i 0; i n; i){bool flag false;//判断是否交换过for (int j 0; j n - 1 - i; j){if (a[j] a[j 1]){Swap(a[j], a[j 1]);flag true;}}if (flag false)//一趟下来没有交换说明已经有序{break;}} }6.快速排序 快速排序整体的综合性能和使用场景都是比较好的这也是大多数人使用快排的原因。 快速排序算法应该算是排序算法中的重点了。 快速排序是一种二叉树结构的交换排序方法。 基本思想任取待排序的序列中的某元素作为key值按照key值将待排序集合分割成两个子序列左子序列中所有元素均小于key右子序列中所有元素均大于key然后最左右子序列重复该过程直到所有元素有序。 快速排序的过程与二叉树的前序遍历相似因此可以采用递归的方式。但在某些极端情况下可能会出现栈溢出因此有时也会使用非递归的形式实现。 递归实现 快速排序的细节问题有很多区间问题、key值的选取、交换细节等等这些细节不注意很容易会造成超时(无限循环)、排序出错等问题。因此也衍生了很多版本hoare版本、挖坑法、前后指针版本等还有一些优化key值选取的方法例如“三数取中法”这些代码有些地方不是那么容易理解并且冗长有的版本在排序OJ会跑不过。 上述所有版本这里不再总结其他博主有更详细的介绍。下面介绍一种AcWing上大佬总结的快排模板非常厉害代码简洁易懂在排序OJ也能跑过。 思路 我们选取一个key值使用双指针i和j分别从区间左右两边往中间走将key的数换到右区间将key的数换到左边界当ij时j或i的左边区间都key右边区间都key然后再递归左区间和右区间按照此方法排序。 void QuickSort(int* a, int l, int r) {//递归的终止情况if (l r) return;//最好不选左右端点作key,否则有序或逆序情况下效率很差int key a[(l r) / 2];int i l - 1, j r 1;while (i j){while (a[i] key);//左边找大while (a[–j] key);//右边找小if (i j)Swap(a[i], a[j]);}QuickSort(a, l, j);QuickSort(a, j 1 , r); }下面需要证明两个问题无限循环和无限递归的边界问题。 key的取值会影响后面递归的区间下面四种写法都是正确的。 上面代码是右边第一种写法。 我们先分析递归区间的取法 再来分析key的取法 虽然下面这两种区间划分都可以但具体哪种要看key的取法 这四种写法取一种即可 但建议写左边两种因为key取到边界的话有序或逆序情况下效率很差。 总结 1.key取a[l]或者a[(lr)/2]递归区间为QuickSort(a,l,j)和QuickSort(a,j1,r); 2.key取a[r]或者a[(lr1)/2]递归区间为QuickSort(a,l,i-1)和QuickSort(a,i,r); 3.key不建议取边界最好从中间选取否则有序或者逆序情况下效率很差。 时间复杂度O(N*logN)。时间复杂度每层的操作次数×树的深度nlogn 最好情况O(NlogN) 有序只判断不进行交换。 最坏情况O(N2)并非逆序每次划分key都是最小(最大)的。 空间复杂度O(logN)。 递归的栈帧开销。 稳定性不稳定。 快排前后交换数据会导致相对位置 发生改变。 非递归实现 快排的递归过程是将大区间划分为两个小区间这两个小区间再分别划分成两个更小区间直到递归到边界条件结束然后回退到上一层。 所以快排的非递归可以借助队列或者栈的方式来实现。 队列的话可以参考二叉树的层序遍历。 思路先取队头区间排序处理再将队头的左右子区间入队再取队头区间再将左右区间入队重复直到队列为空。 下面介绍快排非递归采用栈的实现方法。类似二叉树的前序遍历。 思路每次取栈顶区间进行快排的单趟排序然后将该区间的左右子区间入栈再取栈顶区间处理重复直到栈空。 //非递归快排 void QuickSortNonRe(int a, int left, int right) {ST st;STInit(st);STPush(st, left);//左端点入栈STPush(st, right);//右端点入栈while (!STEmpty(st)){//注意顺序和入栈顺序相反int r STTop(st);STPop(st);int l STTop(st);STPop(st);//单趟排序int key a[(l r) / 2];int i l - 1, j r 1;while (i j){while (a[i] key);//左边找大while (a[–j] key);//右边找小if (i j)Swap(a[i], a[j]);}//分为[l, j]和[j 1, r]区间if (l j)//l j 说明该区间只有一个值无需入栈{STPush(st, l);STPush(st, j);}if (j 1 r){STPush(st, j 1);STPush(st, r);}}STDestroy(st); }7.归并排序 递归实现 归并排序的递归实现属于分治算法分治算法都有三步 1.分成子问题 2.递归处理子问题 3.子问题合并。 归并排序是不断将区间分解成子区间一分二二分四…直到每个区间只有一个元素然后开始向上合并有序区间分而治之。实现过程与二叉树的后序遍历类似先递归再合并处理元素。 时间复杂度O(N*logN)。与快排一样时间复杂度每层的操作次数×树的深度nlogn 归并排序不受初始数据顺序的影响不管有序还是无序时间复杂度都是O(N*logN)。因为每次都递归到最小区间开始合并区间。 空间复杂度O(N)。 需要额外开辟数组空间。 稳定性稳定。 归并过程左右区间有两个数相同时先从左区间取数据。 //归并排序 稳定 时间复杂度O(NlogN) 空间复杂度O(N) void Merge(int a, int l, int r, int* tmp)//tmp临时存放合并好的数据 {//递归的终止情况if (l r)return;//第一步分成子问题int mid (l r) / 2;//第二步递归处理子问题Merge(a, l, mid, tmp);Merge(a, mid 1, r, tmp);//第三步合并子问题将[l, mid]和[mid 1, r]区间归并int i l, j mid 1;int k 0;while (i mid j r){if (a[i] a[j])//可见稳定性tmp[k] a[i];elsetmp[k] a[j];}//左区间剩余while (i mid)tmp[k] a[i];//右区间剩余while (j r)tmp[k] a[j];//将归并好的tmp数组的内容交给数组a的[l,r]区间memcpy(a l, tmp, sizeof(int) * k);// k r - l 1//i l, k 0;//while (i r)// a[i] tmp[k]; }//归并排序 void MergeSort(int* a, int n) {int* tmp (int*)malloc(sizeof(int) * n);if (NULL tmp){perror(malloc);return;}Merge(a, 0, n - 1, tmp);free(tmp); }非递归实现 归并排序的非递归是可以直接从最小区间开始合并的所以省去了递归划分子区间的过程使用一个gap值来实现区间的跨度gap从1开始每循环一次乘2,区间的跨度从1到2再到4…以2的指数增长。如果数据个数不满足2n个则左右区间可能会发生越界这就是需要处理的细节问题。 修正区间边界左区间的左端点一定不会越界不用考虑当左区间的右端点越界或者右区间的左端点越界则后面的元素有序不再合并等待下一轮。 否则如果右区间的右端点越界则使右端点n-1进行修正。
//非递归 void MergeSortNonRe(int* a, int n) {int* tmp (int*)malloc(sizeof(int) * n);if (NULL tmp){perror(malloc);return;}int gap 1;while (gap n){for (int i 0; i n; i 2 * gap){int left1 i, right1 i gap - 1;int left2 i gap, right2 i 2 * gap - 1;if (right1 n || left2 n)//不再归并{break;}if (right2 n)//第二区间右端点越界{right2 n - 1;}//合并子区间int k i;while (left1 right1 left2 right2){if (a[left1] a[left2])tmp[k] a[left1];elsetmp[k] a[left2];}while (left1 right1)tmp[k] a[left1];while (left2 right2)tmp[k] a[left2];//合并一次拷贝一次memcpy(a i, tmp i, sizeof(int) * (right2 - i));}gap * 2;}free(tmp); }8.计数排序 前面七种排序算法都属于比较排序而计数排序是一种非比较排序。并不是通过两个数相比来进行排序的。 计数排序本质就是用数组存储一个映射关系把它的位置保存起来然后再遍历原先的数组从位置数组中把它拿出来进行排序。 基本思想统计相同元素出现次数然后根据统计的结果将序列回收到原来的序列中。 遍历一边序列元素每出现一次就将以该元素为下标的数组的值1类似哈希表。 但是如果序列中只有几个数但这几个数并不算很小例如{100, 100,101}我们就需要开辟101个空间来存储会造成空间的大量浪费。所以对此可以进行优化利用序列中最大值和最小值的差值来开辟空间。这样只需开辟2个整型空间即可。 时间复杂度O(Nrange)。只需要遍历几遍数组。 归并排序不受初始数据顺序的影响不管有序还是无序时间复杂度都是O(NlogN)。因为每次都递归到最小区间开始合并区间。 空间复杂度O(range)。 需要额外开辟空间。range最大值-最小值1 稳定性不稳定。 没有进行数据交换本质上是修改了原始数据。 计数排序在数据范围集中时效率很高但是适用范围及场景有限。 //计数排序 时间复杂度O(Nrange) 空间复杂度O(range) void CountSort(int a, int n) {//第一遍找出最大值和最小值int maxVal a[0], minVal a[0];for (int i 1; i n; i){if (a[i] maxVal)maxVal a[i];if (a[i] minVal)minVal a[i];}//开辟数组空间int range maxVal - minVal 1;//calloc自动初始化为0int* count (int*)calloc(sizeof(int), range);if (NULL count){perror(malloc);return;}//第二遍计数for (int i 0; i n; i)count[a[i] - minVal];//排序int i 0;for (int x minVal; x maxVal; x){while (count[x - minVal]– 0)a[i] x;}free(count); }四、总结 对这八种算法进行性能测试随机生成10万个数据统计排序所消耗时间如下 可以看出三种基本排序插入排序、选择排序、冒泡排序所花费的时间明显更多。它们的时间效率都是O(N2)但是它们的效率却有明显差别。 插入排序最快选择排序扫描一遍数组只需要换两次位置而冒泡排序需要不断交换相邻的元素。因此选择排序在大型数据集中的性能比冒泡排序更好。 剩下五种排序算法跟它们不是一个量级数据量太小看不出明显差别我们单独用100万个数据来测试这五种排序算法的性能。 计数排序最快但是计数排序的使用场景也有限本质是拿空间换时间而且当空间效率O(range)O(nlog(n))的时候其效率反而不如基于比较的排序所以计数排序不归在常见的排序算法中。 剩下四种常见算法中希尔排序、堆排序、归并排序是相差不大的快速排序是比较突出的要比其余算法除了计数排序都快快速排序整体的综合性能和使用场景都是比较好的。 排序算法复杂度及稳定度分析 排序方法时间复杂度空间复杂度稳定性平均情况最好情况最坏情况插入排序插入排序O(n²)O(n)O(n²)O(1)稳定希尔排序平均 O(n1.3)O(1)不稳定选择排序选择排序O(n²)O(n²)O(n²)O(1)不稳定堆排序O(nlogn)O(nlogn)O(nlogn)O(1)不稳定交换排序冒泡排序O(n²)O(n)O(n²)O(1)稳定快速排序O(nlogn)O(nlogn)O(n²)O(nlogn)不稳定归并排序O(nlogn)O(nlogn)O(nlogn)O(n)稳定计数排序O(nrange)O(nrange)O(nrange)O(range)不稳定 快速排序一般情况时排序速度最块但是不稳定当有序时反而不好 归并排序效率非常不错在数据规模较大的情况下比希尔排序和堆排序要好 堆排序适合Tok-K问题例找出一千万个数中最小的前一百个数 算法的时间复杂度与初始序列初态无关的算法有选择排序、堆排序、归并排序。 完整代码八大排序算法