成华区建设局网站wordpress对比

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

成华区建设局网站,wordpress对比,国家年报个体户工商营业执照,深圳建站公司开发费用数据结构初阶我们需要了解掌握的几种排序算法(除了直接选择排序#xff0c;这个原因我们后面介绍的时候会解释)如下#xff1a; 其中的堆排序与冒泡排序我们在之前的文章中已经详细介绍过并对堆排序进行了一定的复杂度分析#xff0c;所以这里我们不再过多介绍。 一#x…        数据结构初阶我们需要了解掌握的几种排序算法(除了直接选择排序这个原因我们后面介绍的时候会解释)如下 其中的堆排序与冒泡排序我们在之前的文章中已经详细介绍过并对堆排序进行了一定的复杂度分析所以这里我们不再过多介绍。 一插入排序  1.1直接插入排序  1.1.1概念及实现代码  直接插入排序是⼀种简单的插⼊排序法其基本思想是把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到⼀个新的有序序列 。 就像我们玩扑克牌一样当我们将发给我们的牌拿到我们自己手中进行排序一样当插⼊第 i(i1) 个元素时前⾯的 array[0],array[1],…,array[i-1] 已经排好序此时用array[i] 的排序码与 array[i-1],array[i-2],… 的排序码顺序进行比较找到插入位置即将 array[i] 插入原来位置上的元素顺序后移。实现代码如下 void InsertSort(int* arr, int n) {for (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;} } 从实现代码中我们不难看出 直接插入的思想为先将前两个元素排好再一个一个的往后进行如果后面数据比我们上一次排好的数据的末尾数据大时让末尾数据后移再与末尾数据的前一个数据进行比较直到找到小于的数据为止。插入的方法思想可以类比下我们顺序表中的头插法。 1.1.2复杂度的计算  空间复杂度由于未创建辅助空间所以为O(1)。时间复杂度从代码中我们可以得知最好情况下为O(N)(数组本身即为顺序)最坏的情况下(即数组逆序的情况下)为O(N^2)。所以直接插入的时间复杂度为O(N^2)。 1.2希尔排序 1.1.1概念及实现代码  希尔排序是对直接插入排序的改良再原有的排序方式上加入预排序以达到减小时间复杂度的目的实现代码如下 void ShellSort(int* arr, int n) {int gap n;while (gap 1){gap gap / 3 1;for (int i 0; i n - gap; i){int end i;int 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为1时数组已经基本有序但我们不能直接设gapn/3比如我们的数组有效元素个数为9个分三次之后为0但我们需要让它的最后一次为一所以我们的gap每次循环都设置为除三加以从而确保最后进入循环的gap值为一。 1.1.2复杂度的简要计算 空间复杂度与直接插入一致为O(1)。而时间复杂度对于外层(预排序)我们可以联想树一直三分其实时间复杂度就为树的深度hlogn。所以外层的时间复杂度为logn。对于内层的时间复杂度博主智商有限难以推出因为它的gap能够取得的值太多了从而导致内层的复杂度难以计算所以我们直接给出希尔排序的粗略时间复杂度的估算O(N^1.3)。需要详细推理过程的读者可以自行上网搜寻。 二选择排序 这一部分我们不细讲堆排序上篇文章已经详细介绍过直接选择排序给出代码我们即可理解其思想 void SelectSort(int* arr, int n) {int begin 0;int end n - 1;while (begin end){int max begin;int min begin;for(int i begin;i end;i){if (arr[max] arr[i]){max i;}if (arr[min] arr[i]){min i;}}if (max begin){max min;}Swap(arr[min], arr[begin]);Swap(arr[max], arr[end]);begin;end–;} } 它的思想是逐步的将数据向中间集拢第一遍找数组中的最大(小)值并将最大(小)值分别放到头尾接着让头尾–。再次重复第一次的操作最后直到没有数据为止。  可见直接选择排序无论是最好的情况顺序还是最坏的情况逆序他的时间复杂度均为O(N^2)。在实际学习与生产过程中都不可能使用这也是我们简略介绍的原因。 三快速排序  快速排序是Hoare于1962年提出的⼀种⼆叉树结构的交换排序方法其基本思想为任取待排序元素序列中的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均子于基准值右子序列中所有元素均⼤于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止。 其实快速排序最主要的思想即为基准值无限的二分去寻找基准值与我们前面学习的二叉树非常类似。所以它的递归版本基础框架为(key为我们每次寻找到的基准值)   void QuickSort(int* arr, int left, int right) {if (left right){return;}int key _QuickSort3(arr, left, right);QuickSort(arr, left, key - 1);QuickSort(arr, key 1, right); } 3.1hoare版本快排 hoare版本的思想为开始设首数据为基准值同时设左右指针左边先找比基准值大的数据找到停下右边找比基准值小的数据停下后于左指针的数据交换循环下去直到左指针的对应数组下标小于右指针截止。实现代码如下 int _QuickSort1(int* arr, int left, int right) {int key left;left;while (left right){while (left right arr[left] arr[key]){left;}while (left right arr[right] arr[key]){right–;}if (left right){Swap(arr[left], arr[right–]);}}Swap(arr[right], arr[key]);return right; } 为什么leftright时还要进入循环是因为每次我们交换完后right–,left。万一此时它们正好重合此处数据若小于或大于基准值都会导致最终基准值的落脚点错误。 3.2挖坑版本快排 创建左右指针。首先从右向左找出比基准小的数据找到后立即放入左边坑中当前位置变为新的坑然后从左向右找出比基准⼤的数据找到后立即放⼊右边坑中当前位置变为新的坑结束循环后将最开始存储的分界值放⼊当前的坑中返回当前坑下标即分界值下标。实现代码如下 int _QuickSort2(int* arr, int left, int right) {int key arr[left];int hole left;while (left right){while (left right arr[right] key){–right;}Swap(arr[hole], arr[right]);hole right;while (left right arr[left] key){left;}Swap(arr[hole], arr[left]);hole left;}arr[hole] key;return hole; } 这里我们不需要去考虑left与right的相等的情况因为我们最终基准值的位置与hole相关所以不会影响我们基准值的落脚点正确。 3.3lomuto前后指针版本 创建前后指针从左往右找比基准值小的进行交换使得小的都排在基准值的左边。实现代码如下 int _QuickSort3(int* arr, int left, int right) {int key left;int slow left;int fast left 1;while (fast right){if (arr[fast] arr[key] slow ! fast){Swap(arr[fast], arr[slow]);}fast;}Swap(arr[slow], arr[key]);return slow; } 3.4非递归版本的快排框架  由于每次我们的快排对基准值的寻找都需要上一次的基准值给出首尾位置这里我们就可以借助我们之前学习到的堆的知识来进行首尾位置的记录 void Swap(int* x, int* y) {int tmp *x;*x *y;y tmp; }void STInit(Stack ps) {assert(ps);ps-top ps-capacity 0;ps-arr NULL; }void DestoryST(Stack* ps) {assert(ps);assert(ps-arr);free(ps-arr);ps-capacity ps-top 0; }void STpush(Stack* ps, STDataType x) {assert(ps);if (ps-top ps-capacity){int exchange ps-capacity 0 ? 4 : ps-capacity * 2;STDataType* new (STDataType*)realloc(ps-arr, sizeof(STDataType) * exchange);if (new NULL){perror(new:);exit(1);}ps-arr new;ps-capacity exchange;}ps-arr[ps-top] x; }void STDelt(Stack* ps) {assert(ps);assert(!EmptyST(ps));–ps-top; }STDataType EleSTop(Stack* ps) {assert(ps !EmptyST(ps));return ps-arr[ps-top - 1]; }int EmptyST(Stack* ps) {assert(ps);return (ps-top 0); } void QuickSortNone(int* arr, int left, int right) {Stack st;STInit(st);STpush(st, right);STpush(st, left);while (!EmptyST(st)){int begin EleSTop(st);STDelt(st);int end EleSTop(st);STDelt(st);int meet _QuickSort3(arr, begin, end);if (begin meet - 1){STpush(st, meet-1);STpush(st, begin);}if (end meet 1){STpush(st, end);STpush(st, meet1);}}DestoryST(st); } 这里我们使用之前文章所给出的堆的实现方法来实现我们的非递归版本的快排的基本架构这样及做到了减少时间复杂度又减少了空间复杂度。 3.5复杂度的计算 快速排序由于是以二叉树的方式进行栈的创建与销毁所以其空间复杂度为logn时间复杂度则与我们之前的向下建堆的时间复杂度一致为O(NlogN)。 四归并排序 归并排序MERGE-SORT是建立在归并操作上的⼀种有效的排序算法,该算法是采用分治法Divide and Conquer的⼀个非常典型的应用。将已有序的子序列合并得到完全有序的序列。即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成⼀个有序表称为⼆路归并。 归并排序核心步骤 初始数组: 初始未排序数组是 [10, 6, 7, 1, 3, 9, 4, 2]。 分解阶段自顶向下: 数组被递归地分解成更小的子数组直到每个子数组包含一个元素。第一次分解[10, 6, 7, 1] 和 [3, 9, 4, 2]。第二次分解 [10, 6, 7, 1] 分解为 [10, 6] 和 [7, 1]。[3, 9, 4, 2] 分解为 [3, 9] 和 [4, 2]。第三次分解 [10, 6] 分解为 [10] 和 [6]。[7, 1] 分解为 [7] 和 [1]。[3, 9] 分解为 [3] 和 [9]。[4, 2] 分解为 [4] 和 [2]。 合并阶段自底向上: 分解到最小子数组后开始两两合并并在合并过程中进行排序。第一次合并 [10] 和 [6] 合并为 [6, 10]。[7] 和 [1] 合并为 [1, 7]。[3] 和 [9] 合并为 [3, 9]。[4] 和 [2] 合并为 [2, 4]。第二次合并 [6, 10] 和 [1, 7] 合并为 [1, 6, 7, 10]。[3, 9] 和 [2, 4] 合并为 [2, 3, 4, 9]。第三次合并 [1, 6, 7, 10] 和 [2, 3, 4, 9] 合并为 [1, 2, 3, 4, 6, 7, 9, 10] 图示如下 实现归并排序的代码如下 void _MergeSort(int* arr, int left, int right, int* tmp) {if (left right){return;}int mid (left right) / 2;_MergeSort(arr, left, mid, tmp);_MergeSort(arr, mid 1, right, tmp);int begin1 left, end1 mid;int begin2 mid 1, end2 right;int index begin1;while (begin1 end1 begin2 end2){if (arr[begin1] arr[begin2]){tmp[index] arr[begin1];}else {tmp[index] arr[begin2];}}while (begin1 end1){tmp[index] arr[begin1];}while (begin2 end2){tmp[index] arr[begin2];}for (int i left; i right; i){arr[i] tmp[i];} }void MergeSort(int* arr, int n) {int* tmp (int*)malloc(sizeof(int) * n);_MergeSort(arr, 0, n - 1, tmp);free(tmp); }五各类排序算法的时间及空间复杂度的比较 5.1对于稳定性的解释  稳定性的概念在排序算法中指的是如果两个元素在原始数组中有相同的值那么在排序完成后它们的相对顺序是否保持不变。 5.1.1稳定排序算法 一个稳定的排序算法会保持相同值的元素在原数组中的相对顺序。例如考虑以下数组 [5a, 3, 4, 5b, 2]在这里5a 和 5b 是两个相同值的元素但它们是不同的个体。 如果使用稳定的排序算法例如冒泡排序或插入排序那么排序后的数组可能是 [2, 3, 4, 5a, 5b]注意5a 仍然在 5b 之前这保持了它们在原始数组中的相对顺序。 5.1.2不稳定排序算法 一个不稳定的排序算法则不保证相同值的元素在排序后的相对顺序。例如考虑同样的数组 [5a, 3, 4, 5b, 2]如果使用不稳定的排序算法例如选择排序或快速排序那么排序后的数组可能是  [2, 3, 4, 5b, 5a]在这里5a 和 5b 的相对顺序被改变了。