python做网站好处,合肥科技网站建设,深圳高端网站建设报价,建网站花钱吗1. 冒泡排序
排序的过程分为多趟#xff0c;在每一趟中#xff0c;从前向后遍历数组的无序部分#xff0c;通过交换相邻两数位置的方式#xff0c;将无序元素中最大的元素移动到无序部分的末尾#xff08;第一趟中#xff0c;将最大的元素移动到数组倒数第一的位置…1. 冒泡排序
排序的过程分为多趟在每一趟中从前向后遍历数组的无序部分通过交换相邻两数位置的方式将无序元素中最大的元素移动到无序部分的末尾第一趟中将最大的元素移动到数组倒数第一的位置第二趟中将第二大的元素移动到数组倒数第二的位置以此类推。
每排一趟数组末尾的有序序列就向前增长一个元素数组前端的无序部分就减少一个元素。
优化某趟中一次交换也没有发生说明数组已有序直接结束排序。
整个排序的过程中剩余无序元素中最大的元素就像气泡一样不断“上浮”到数组末尾所以该算法被称作冒泡排序。
冒泡排序的思想很简单类似于递归 要实现整个数组n个元素的有序可以将数组分为前n-1个元素和最后一个元素。 首先确保最后一个元素有序最大然后再用相同的方式解决前n-1个元素组成的数组的有序性问题。 当然你也可以当我上面这段话是放屁因为冒泡排序的算法太过简单按上面的方式来理解确实小题大做。
但伴随着简单算法的往往是极高的开销这也使得冒泡排序没有任何的实际意义仅作教学作用。
可以说冒泡排序是最拉的排序算法接下来讲到的所有排序算法效率都至少为其的十倍以上实测结果非理论分析理论分析出的时间复杂度几乎相同
时间复杂度最坏情况元素逆序最好情况已有序
空间复杂度
//冒泡排序
void BubbleSort(int* arr, int len)
{for (int i 0; i len; i){int flag 1;for (int j 0; j len - 1 - i; j){if (arr[j] arr[j 1]){flag 0;swap(arr[j], arr[j 1]);}}if (flag)return;}
}
2. 选择排序
顾名思义就是在每趟排序中直接选出最大的元素的下标然后将其与无序部分末尾的元素进行交换同时无序部分的末尾向前缩短一个元素。
相对于冒泡排序二者的做法很像但选择排序省去了交换相邻元素的过程效率提高的关键手段更加直接。
优化在选出最大元素的同时将最小元素也选出来两端同时排序。
void SelectSort(int* arr, int len)
{int begin 0, end len - 1;while (begin end){int max begin;int min begin;for (int i begin 1; i end; i){if (arr[i] arr[min])min i;if (arr[i] arr[max])max i;}swap(arr[begin], arr[min]);swap(arr[end], arr[max]);begin;end--;}
}
但是直接进行优化之后的算法会存在一个小bug 假设在每趟排序中将最大元素和最小元素选出来之后先让最小元素交换到无序部分的前端再让最大元素交换到无序部分末尾。 那么当最大元素刚好在无序部分前端时就会发生如下的过程 1. 首元素最大元素与最小元素交换 2. 最大元素首元素此时该位置为最小元素与末尾元素交换 可以按照下面的方式解决。
//选择排序
void SelectSort(int* arr, int len)
{int begin 0, end len - 1;while (begin end){int max begin;int min begin;for (int i begin 1; i end; i){if (arr[i] arr[min])min i;if (arr[i] arr[max])max i;}swap(arr[begin], arr[min]);if (begin max)swap(arr[end], arr[min]);elseswap(arr[end], arr[max]);begin;end--;}
}
时间复杂度
空间复杂度
由于选择排序无法提前结束所以其时间复杂度为稳定的。
但是相比于冒泡排序选择排序在整体上减少了频繁交换的消耗在一般情况下效率要远好于冒泡排序。
3. 插入排序
上面的两种算法是在为某个位置选择合适的元素填入而插入排序则是在为某个元素选择合适的位置去存放也正是这一差别使其成为了这三位难兄难弟的老大哥。
为某个元素选择合适的位置必然只有在其他元素都有序的情况下才能做到或者局部有序。
尽管数组在整体上无序我们却可以将开头的一个元素看作是无序接着将第二个元素插入其中。
于是前两个元素就变得有序了我们又可以将第三个元素插入其中……以此类推数组便逐渐有序了。
插入排序就是将数组分为两个部分数组前端的有序部分开始只有一个元素和数组后半段的无序部分。然后将无序部分的元素逐个插入到有序部分。
而对于插入我们采用的办法是 从后向前遍历有序部分如果当前位置的元素比要插入的元素大则将当前位置的元素向后移动一个元素为要插入的元素腾位置如果当前位置的元素要比插入的元素小则将要插入的元素插入到当前位置的后面自己原本的位置或者是第一种情况腾出来的位置。 优化 可优化为希尔排序详见下文。
//插入排序
void InsertSort(int* arr, int len)
{for (int i 1; i len; i){int temp arr[i];int j i;while(j 0 arr[j - 1] temp){arr[j] arr[j - 1];j--;}arr[j] temp;}
}
时间复杂度最坏情况元素逆序最好情况已有序
空间复杂度
虽然看上去与冒泡排序一模一样但是其实际的消耗要小得多相比于选择排序也要更优。
4. 希尔排序 在插入排序算法中越小的元素越早插入越好越大的元素越晚插入越好。
当元素恰好逆置时算法的消耗较大几乎等价于冒泡排序。
而希尔排序就是希尔为解决插入排序痛点而设计的算法解决这一痛点的方法就是先对整个数组进行跨度较大的粗调再进行更加细致的调整只有数据量较大时希尔排序的优化才有意义否则直接使用插入排序即可。
我们发现如果较大的元素插入得较早之后就会进行大量的操作将该元素后移并且每次只移动一个元素。
如果我们能够快速地一次跳过多个元素将这些较大的元素调整到靠后的位置使得数组基本有序插入排序的时间复杂度就会无限接近于最好情况。
那么如何进行粗调呢 1. 将数组的元素分为若干组记组数为gap每一组元素的下标模上gap所得的值相同即每一组元素的下标为模gap的同余关系类似于分层抽样。 2. 对每一组的元素进行插入排序这样一来较大的元素每次向后移动的元素个数为gap粗调的效率就远高于直接插入排序。 3. 缩小gap的值重复上述过程一般做法为gapgap/311的目的是使得最后一趟排序时gap为1也就是对整个数组进行一次插入排序。 //希尔排序(插入排序优化)
void ShellSort(int* arr, int len)
{int gap len;while (gap 1){gap gap / 3 1;for (int group 0; group gap; group){for (int i group gap; i len; i gap){int temp arr[i];int j i;while (j group arr[j - gap] temp){arr[j] arr[j - gap];j - gap;}arr[j] temp;}}}
}
可以看到最内层的两层循环其实就是将插入排序中的“1”替换为了“gap”将起点从“01”改成了“group gap”。
控制group的循环就是在切换插入排序的组别。
优化如果觉得四层循环看起来很唬人的话我们也可以优化掉一层循环但效率不变
//希尔排序X(各组同时排优化掉三重循环但效率相同)
void ShellSort_X(int* arr, int len)
{int gap len;while (gap 1){gap gap / 3 1;for (int i gap; i len; i){int temp arr[i];int j i;while (j 0 arr[j - gap] temp){arr[j] arr[j - gap];j - gap;}arr[j] temp;}}
}
时间复杂度平均情况最好情况
空间复杂度
初见希尔排序的代码可能会误以为其效率极低但实际上希尔排序的效率极高甚至在数据量较大时效率高出上文介绍的算法不止一个量级百倍以上
接下来的几种算法于希尔排序同属一个量级但效率有略微差别。
其排序的过程极其复杂具有许多不可控因素不能简单地通过循环的层数来计算时间复杂度。
希尔排序的代码很难理解但是其解决问题的思想却很值得我们学习借鉴。
5. 堆排序
详见这篇文章全面详解堆-CSDN博客
6. 快速排序
详见这篇文章C语言实现快速排序算法-CSDN博客
值得一提的是快速排序正如其名快且综合实力强。
C语言中qsort函数的底层算法便是采用的快速排序算法。
7. 归并排序
归并排序MERGE-SORT是建立在归并操作上的一种有效的排序算法该算法是采用分治法Divide and Conquer的一个非常典型的应用。
将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。
若将两个有序表合并成一个有序表称为二路归并。
以二路归并为例假如一个数组从中间位置被分为了前后两个部分而这两个部分都是有序的那么我们就可以采用与合并两个有序链表相同的思路比较两个序列中的最小值将较小的那个插入到新的序列中不断重复这样的操作直到原序列中的值全部插入到新序列中。
但前提是前后两个子序列都要有序。
所以我们的首要任务是使得前后两个子序列有序而使其有序的方式依然如上。 于是我们找到的递归的思路
void _MergeSort(int* arr, int* copy, int begin, int end)
{if (begin end)return;//区间不能分为[begin,mid-1]和[mid,end]int mid (begin end) / 2;_MergeSort(arr, copy, begin, mid);_MergeSort(arr, copy, mid 1, end);//归并int begin1 begin, end1 mid;int begin2 mid 1, end2 end;int cur begin;while (begin1 end1 begin2 end2){if (arr[begin1] arr[begin2]){copy[cur] arr[begin1];}else{copy[cur] arr[begin2];}}while (begin1 end1) { copy[cur] arr[begin1]; }while (begin2 end2) { copy[cur] arr[begin2]; }memcpy(arr begin, copy begin, (end - begin 1) * sizeof(int));
}//归并排序
//时间复杂度O(n*logn)空间复杂度O(n)
void MergeSort(int* arr, int len)
{int* copy (int*)malloc(sizeof(int) * len);if (copy NULL){perror(malloc fail);return;}_MergeSort(arr, copy, 0, len - 1);free(copy);
}
和快速排序类似既然这个算法是用递归的方式实现的我们就会考虑其非递归的实现方式。
但与快速排序不同快速排序的递归方式类似于二叉树的前序遍历但是归并排序类似于后序遍历。
参考栈与递归的实现-CSDN博客会发现二叉树前序遍历的非递归实现很简单但是后序遍历的非递归实现则十分麻烦。
将递归算法转化为非递归算法除了利用栈来模拟实现也可以尝试直接利用迭代来实现。
思路就是将数组按gap个数据为一组分为多组每两个相邻的组进行插入合并随后gap变为原来的两倍再次重复以上过程直到gap大于数组长度。
当然最后一组可能分配不到gap个数据也可能只能分出奇数个组针对这些问题进行插入合并归并的代码进行了调整。
//归并排序非递归
void MergeSortNonR(int* arr, int len)
{int* copy (int*)malloc(sizeof(int) * len);if (copy NULL){perror(malloc fail);return;}for (int gap 1; gap len; gap * 2){for (int i 0; i len; i 2 * gap){int begin1 i, end1 i gap - 1;int begin2 i gap, end2 i 2 * gap - 1;//第二组都越界不归并了if (begin2 len){break;}//第二组越界部分修正并归并if (end2 len){end2 len - 1;}int cur i;while (begin1 end1 begin2 end2){if (arr[begin1] arr[begin2]){copy[cur] arr[begin1];}else{copy[cur] arr[begin2];}}while (begin1 end1) { copy[cur] arr[begin1]; }while (begin2 end2) { copy[cur] arr[begin2]; }memcpy(arr i, copy i, ((end2 - i 1) * sizeof(int)));}}free(copy);
}
时间复杂度
空间复杂度
