广州网站建设正规公司,余江网站建设,交互设计师主要是做什么的呢,苏州纳米加工平台文章目录 八大排序算法(含时间复杂度、空间复杂度、算法稳定性)1、#xff08;直接#xff09;插入排序1.1、算法思想1.2、排序过程图解1.3、排序代码 2、希尔排序3、冒泡排序3.1、算法思想3.2、排序过程图解3.3、排序代码 4、#xff08;简单#xff09;选择排序4.1、算法… 文章目录 八大排序算法(含时间复杂度、空间复杂度、算法稳定性)1、直接插入排序1.1、算法思想1.2、排序过程图解1.3、排序代码 2、希尔排序3、冒泡排序3.1、算法思想3.2、排序过程图解3.3、排序代码 4、简单选择排序4.1、算法思想4.2、排序过程图解4.3、排序代码 5、堆排序6、快速排序7、归并排序8、计数排序8.1、算法思想8.2、排序过程图解8.3、排序代码 八大排序算法(含时间复杂度、空间复杂度、算法稳定性) 下列算法默认都是对数组进行升序 1、直接插入排序
1.1、算法思想 插入排序是一种简单直观的排序算法它的工作原理是通过构建有序序列对于未排序数据在已排序序列中从后向前扫描找到相应位置并插入。 插入排序的具体步骤如下 从第一个元素开始该元素可以认为已经被排序取出下一个元素在已经排序的元素序列中从后向前扫描如果该元素已排序大于新元素将该元素移到下一位置重复步骤3直到找到已排序的元素小于或者等于新元素的位置将新元素插入到该位置后重复步骤2~5。 1.2、排序过程图解 从第一个元素开始该元素可以认为已经被排序取出下一个元素并记录到临时变量tmp中在已经排序的元素序列中从后向前扫描end--如果该元素已排序大于新元素将该元素移到下一位置如果该元素小于等于新元素则直接在这个元素的后面把新元素放进来。 这里仅演示部分过程其他过程自行考虑和上述过程类似。 1.3、排序代码 end指向当前要插入元素的前一个位置end1指向当前要插入元素的位置tmp保存当前要插入的元素在已经排序的元素序列中从后向前扫描找到比新元素小的元素的时候因为有序这个位置前面的元素比这个元素更小直接把新元素插入到这个位置的后面。 //插入排序
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 (tmp arr[end]) {arr[end 1] arr[end];} else {break;}--end;}arr[end 1] tmp;}
}时间复杂度计算 最坏时间复杂度数组元素原本是降序现要求使其升序。那么每个元素需要移动或者比较的次数为: 第一个元素0次第二个元素1次第三个元素2次…第n个元素n-1次 总次数0123...n-1 n*(n-1)/2次 所以最坏时间复杂度为O(n^2)。 最好时间复杂度考虑数组原本是升序那么所有元素需要移动或者比较的总次数为011...1 n-1。所以最好时间复杂度为O(n)。 平均时间复杂度O(n^2) ---- 算法不太行。 空间复杂度计算由于没有开辟额外空间来辅助数组排序故空间复杂度为O(1)。 算法稳定性稳定因为对于值相同的元素后插入的时候不会插到相同元素的前面tmp arr[end]会break即不插入。 2、希尔排序
希尔排序详解 3、冒泡排序
3.1、算法思想
冒泡排序是通过对相邻元素的比较和位置交换使得每次遍历都可以得到剩余元素中的最大值将其放入有序序列中最终的位置然后下一趟排序的时候就不用去比较这个已经确定了的元素。在冒泡排序中会依次比较相邻元素的值若发现逆序则交换使值较大的元素逐渐从前移向后部就如同水底下的气泡一样逐渐向上冒。 3.2、排序过程图解 每趟排序可以把一个元素”冒“到最终位置上下一趟排序就可以少排序一个元素。 这里仅演示部分过程其他过程自行考虑和上述过程类似。 3.3、排序代码 指针i控制每趟需要少排序的元素个数即已经有i个元素已经在最终位置上指针j用来比较相邻元素的大小若相邻元素是降序则交换这两个元素。 这里定义了一个flag用来标记每趟排序是否有交换如果有交换就需要继续下一趟排序没有交换则说明数组已经有序那么就不用继续下一趟排序 void Swap(int *a, int *b) {int tmp *a;*a *b;*b tmp;
}//冒泡排序
void BubbleSort(int *arr, int n) {for (int i 0; i n; i) {int flag 0;for (int j 0; j n - 1 - i; j) {if (arr[j 1] arr[j]) {flag 1;Swap(arr[j], arr[j 1]);}}if (flag 0) {break;}}
}时间复杂度计算 最坏时间复杂度考虑数组原本是降序现在要求其升序。那么每个元素需要移动或者比较的次数为: 第一趟排序n-1次第二趟排序n-2次第三趟排序n-3次…第n趟排序1次 总次数n-1n-2n-3...1 n*(n-1)/2次 所以最坏时间复杂度为O(n^2)。 最好时间复杂度考虑数组原本是升序。那么所有元素需要移动或者比较的次数为 若不使用flag比较次数为n-1n-2n-3...1 n*(n-1)/2次。 使用flag比较次数为n-1次。 平均时间复杂度O(n^2) — 算法不太行。 空间复杂度计算由于没有开辟额外空间来辅助数组排序故空间复杂度为O(1)。 算法稳定性稳定因为对于值相同的元素每一趟排序的时候不会交换arr[j 1] arr[j]才交换。 4、简单选择排序
4.1、算法思想
选择排序是一种简单直观的排序算法。它的工作原理如下优化后的选择排序–每次都能确定当前未排序序列的最小元素和最大元素的最终位置 在未排序序列中找到最小元素和最大元素最小元素存放到排序序列的起始位置最大元素存放到排序序列的末尾位置。再从剩余未排序元素中继续寻找最小元素和最大元素然后最小元素放到前面已排序序列的末尾最大元素放到后面已排序序列的前面。以此类推直到所有元素均排序完毕。 这里动画排序是每次选出一个最小值。我们讲的算法更优哈哈 4.2、排序过程图解 在未排序序列中找到最小元素和最大元素最小元素存放到排序序列的起始位置最大元素存放到排序序列的末尾位置。 再从剩余未排序元素中继续寻找最小元素和最大元素然后最小元素放到前面已排序序列的末尾最大元素放到后面已排序序列的前面。 这里仅演示部分过程其他过程自行考虑和上述过程类似。 以此类推直到所有元素均排序完毕。 4.3、排序代码 使用mini和maxi分别记录当前未排序的最小值下标和最大值下标在未排序的序列中找出最小值和最大值然后分别交换到当前未排序的起始位置和末尾位置。需要注意的是如果当前未排序的序列中最大值刚好在未排序序列的起始位置那么就需要记录好这个最大值与当前未排序的序列中的最小值交换后的位置不记录的话那么当前maxi指向的值不一定是最大值 //选择排序
void SelectSort(int *arr, int n) {int mini 0;int maxi 0;int start 0;int end n - 1;while (start end) {for (int i start 1; i end; i) {if (arr[i] arr[maxi]) {maxi i;}if (arr[i] arr[mini]) {mini i;}}Swap(arr[mini], arr[start]);//注意此时如果start刚好是最大值的话就会把最大值换走了也就是本来最大值在 0 位置交换后换到其他位置了所以判断一下if (start maxi) {maxi mini;//找到最大值的下标}Swap(arr[maxi], arr[end]);//向中间靠拢start;--end;}
}时间复杂度计算对于选择排序排序来说没有什么最坏时间复杂度和最好时间复杂度因为不管原数组起始是升序还是降序元素之间的比较次数都是一样的 确定了2个元素的最终位置n-1确定了4个元素的最终位置n-1n-3确定了6个元素的最终位置n-1n-3n-5…确定了n个元素的最终位置nn-3n-5...1 n*(n1)/4 ---大约所以时间复杂度为O(n^2)。 空间复杂度计算由于没有开辟额外空间来辅助数组排序故空间复杂度为O(1)。 算法稳定性不稳定考虑序列122排序后序列为122我们发现2的相对位置发生了变化所以是不稳定的排序算法。 5、堆排序
堆排序详解 6、快速排序
快速排序递归方法和非递归方法详解 7、归并排序
快速排序递归方法和非递归方法详解 8、计数排序
8.1、算法思想 计数排序就是使用一个临时数组来记录这个原数组的元素对应这个临时数组下标出现的次数然后再对这个临时数组从0开始往后按下标出现的次数遍历。 优化对于原数组最小值较大的情况我们可以使用对这个临时数组进行重定位。 重定位相当于计算机组成原理里面的将逻辑地址转化为物理地址的过程比如序列110,110,111,120,125,122,115,118,112,118其实它的范围就是在110~125区间长度为16如果我们按照这个序列的最大值来建立数组那么需要长度为126的数组但是这个数组的前110个空间都是0也就是并没有用上浪费了。但是如果创建一个长度为16的数组下标为0~15原数组每个元素减110这个110是这个原数组的最小值是不是就可以匹配这个序列的范围了呢 那么问题是之后遍历这个临时数组只能得到0~15的下标并不是我们要的110~125其实在遍历这个临时数组的时候可以继续使用重定位把这个0~15的下标重定位到110~125每个下标都加110这个110是这个原数组的最小值 8.2、排序过程图解 先找到原数组的最大值和最小值然后就可以确定临时数组的长度然后初始化这个临时数组全0。 然后依次遍历原数组根据重定位将原数组的元素减去最小值去对应临时数组的下标并对这个下标里的元素1。 遍历这个临时数组对每个下标进行遍历按下标对应的元素值看需要对此下标遍历几次需要重定位回去—加上原数组的最小值。 8.3、排序代码 用min和max记录原数组的最小值和最大值确定临时数组的长度(max-min1)然后对临时数组count进行初始化接下来就是把原数组里的元素重定位为临时数组的下标元素值减原数组的最小值并对此下标对应的元素1一直到遍历完原数组。 遍历这个临时数组count对每个下标进行遍历按下标对应的元素值看需要对此下标遍历几次需要重定位回去—加上原数组的最小值。 注意这里不能找最大最小值的下标因为在重定位回去的时候arr[j]在变也就是最小值下标不一定对应到最小值了 //计数排序
void CountSort(int *arr, int n) {//先找出数组的最大最小值int max arr[0];int min arr[0];for (int i 1; i n; i) {if (arr[i] max) {max arr[i];}if (arr[i] min) {min arr[i];}}//节省空间需要对元素重定位int capacity max - min 1;//元素大小区间//记录每个元素的出现次数int *count (int *) malloc(sizeof(int) * capacity);if (count NULL) {perror(malloc error);exit(-1);}memset(count, 0, sizeof(int) * capacity);for (int i 0; i n; i) {count[arr[i] - min];}int j 0;for (int i 0; i capacity; i) {while (count[i]--) {arr[j] i min;}}free(count);
}时间复杂度计算这里找最大值最小值花费时间n遍历临时数组花费时间k临时数组长度所以时间复杂度为O(nk)。 空间复杂度计算使用了临时数组临时数组长度为k所以空间复杂度为O(k)。 算法稳定性稳定因为它是利用一个数据的索引来记录元素出现的次数而这个数组的索引就是元素的数值。当计数排序完成后具有相同数值的元素在数组中的位置也相同因此它们的顺序保持不变。 八大排序算法整体的时间复杂度、空间复杂度、算法稳定性等看如下表格: 排序算法平均时间复杂度最好情况最坏情况空间复杂度排序方式稳定性直接插入排序O(n^2)O(n)O(n^2)O(1)内部排序稳定希尔排序O(n^1.3)O(n^1.3)O(n^1.3)O(1)内部排序不稳定冒泡排序O(n^2)O(n)O(n^2)O(1)内部排序稳定简单选择排序O(n^2)O(n^2)O(n^2)O(1)内部排序不稳定堆排序O(nlogn)O(nlogn)O(nlogn)O(1)内部排序不稳定快速排序O(nlogn)O(nlogn)O(n^2)O(logn)内部排序不稳定归并排序O(nlogn)O(nlogn)O(nlogn)O(n)外部排序稳定计数排序O(nk)O(nk)O(nk)O(k)外部排序稳定 OKOK八大排序算法就到这里。如果你对Linux和C也感兴趣的话可以看看我的主页哦。下面是我的github主页里面记录了我的学习代码和leetcode的一些题的题解有兴趣的可以看看。
Xpccccc的github主页
