阿里巴巴网站建设方案,网站做动态和静态哪个贵,美丽深圳微信公众号二维码,wordpress网站amp目录 一. 冒泡排序
1. 算法思想
2. 时间复杂度与空间复杂度
3. 代码实现
二. 选择排序
1. 算法思想
2. 时间复杂度与空间复杂度
3. 代码实现
三.插入排序
1. 直接插入排序
(1). 算法思想
(2). 时间复杂度与空间复杂度
(3). 代码实现
2. 希尔排序
(1). 算法思想
…目录 一. 冒泡排序
1. 算法思想
2. 时间复杂度与空间复杂度
3. 代码实现
二. 选择排序
1. 算法思想
2. 时间复杂度与空间复杂度
3. 代码实现
三.插入排序
1. 直接插入排序
(1). 算法思想
(2). 时间复杂度与空间复杂度
(3). 代码实现
2. 希尔排序
(1). 算法思想
(2). 代码实现
(3). 时间复杂度与空间复杂度 一. 冒泡排序
1. 算法思想
假设排升序从头开始两两比较选出最大的的值移到最后面假设下标为10再从头开始两两比较选出次大的移到下标为9的地方以此类推 2. 时间复杂度与空间复杂度
(1). 最优情况
当数据全都有序时最快。因为此时每个元素只需比较一次就可以完成整个排序过程此时时间复杂度为 O(N)
(2). 最坏情况
当数据逆序时最慢此时每一次比较都需要交换。时间复杂度为 O(N²)
(3). 平均情况
综上所述平均复杂度为 O(N²)
(4). 空间复杂度
冒泡排序只需要一个额外变量来交换元素不需要额外的数据结构来存储数据所以空间复杂度为 O(1)
3. 代码实现
void BubbleSort(int* a, int n)//冒泡排序
{int count 0;for(int j0;jn-1;j){for (int i 0; i n - j-1; i){if (a[i] a[i1] ){Swap(a[i], a[i 1]);count 1;}}if (count 0)break;}
}
二. 选择排序
1. 算法思想
假设排升序遍历数组选出最大值与排序数列的最后一个元素假设下标为10交换再从除最后一个元素即下标0~9的序列中找出次大值与下标为9的序列交换以此往复知道排序完毕
2. 时间复杂度与空间复杂度
(1). 时间复杂度
选择排序需要遍历n-1次来找到最小(或最大)元素并且在每次遍历中都需要对剩余未排序元素进行遍历以找到最小(或最大)元素因此选择排序的时间复杂度总是 O(N²)
(2) 空间复杂度
只需一个额外变量来存储找到的最大(或最小)元素的索引所以空间复杂度为 O(1)
3. 代码实现
我们实现一个优化版本同时找到最大的值与最小的值分别与头和尾交换
void SelectSort(int* a, int n)
{int begin 0, end n -1;while(beginend){int max begin, min begin;for (int i begin1; i end; i){if (a[i] a[max])max i;if (a[i] a[min])min i;}Swap(a[begin], a[max]);Swap(a[end], a[min]);begin;end--;}
}
以上代码还有一个小问题当出现下图情况时 begin所指向的值与max所指向的值交换那min指向的值就变为了原来max所指向的值此时再与end交换会发生将最大的值交换过去的情况
修改代码为
void SelectSort(int* a, int n)
{int begin 0, end n -1;while(beginend){int max begin, min begin;for (int i begin1; i end; i){if (a[i] a[max])max i;if (a[i] a[min])min i;}if (begin min){Swap(a[begin], a[max]);Swap(a[max], a[end]);}else{Swap(a[begin], a[max]);Swap(a[end], a[min]);}begin;end--;}
}
三.插入排序
1. 直接插入排序
(1). 算法思想
从第一个元素开始排序先排前一个数再排前两个数以此类推
假设排升序第一个数自然是有序的第二个数与第一个数比较如果比第一个数小就与其交换然后看第三个数此时前两个数是有序的第三个数先于第二个数比较比第二个数小就与其交换再与第一个数比较比第一个数小就与其交换如果不比第二个数小就看第四个数此时前三个数都是有序的以此类推 (2). 时间复杂度与空间复杂度
① 最好情况
在有序情况下只需遍历一遍即可时间复杂度为 O(N)
②最坏情况
在逆序情况下每一次比较都要交换时间复杂度为 O(N²)
③平均情况
综上所述平均时间复杂度为O(N²)
④空间复杂度
只需要一个额外的空间来存储当前要插入的元素空间复杂度为O(1)
(3). 代码实现
void InsertSort(int* a,int n)//直接插入排序
{for(int i0;in-1;i){int end i;int t a[i1];while (end 0){if (t a[end]){a[end1] a[end];end--;}else break;}a[end1] t;}}
2. 希尔排序
(1). 算法思想
是直接插入算法的改进版本总体操作可大致分为两步 先进行预排序 直接插入排序 直接插入排序是和距离为1的元素比较而希尔排序是和距离为gap的元素比较gap不断变小直到变为1此时即是直接插入排序
初始序列为 9 1 2 5 7 4 8 6 3 5 gap值为5进行一次预排序过程如下 预排序后序列为 当gap为2时
预排序后序列为 我们发现预排序后一定比之前更加接近有序
从时间上讲gap越大大的数可以越快的到后面去小的数可以越快的到前面去
gap越小呢预排序完就越接近有序gap1就是直接插入排序
我们就可以将gap慢慢减少直到变为1从而进行直接插入排序是尽量是最好的情况
(2). 代码实现
希尔排序的代码与直接插入排序的代码十分相似不同的地方就是gap可以通过三层循环或四层循环实现两者执行的次数实际是一样的
void ShellSort(int* a, int n)//希尔排序
{int gap n;while(gap1){gap gap/ 31;// 除3不一定会1但3是最合理的所以1保证最后一次gap一定是1 //for(int j0;jgap;j)//{for (int i 0; i n - gap; i)//一组一组的排序所以i也可以gap效率没有区别都是要走这些步数{int end i;int t a[end gap];while (end 0){if (t a[end]){a[end gap] a[end];end - gap;}elsebreak;}a[end gap] t;}//}}
}
(3). 时间复杂度与空间复杂度 希尔时间复杂度的计算需要很高的数学水平此处只做粗略解释(我不会嘿嘿) ①时间复杂度
我们假设每一次gapn/3,此时每组三个数据
最坏情况下 第一次排序消耗(12)*n/3n
下一次
gapn/3/3n/9每组9个数据
但此时由于上面的预排序不可能是最坏情况即
(12345678)*n\9
具体计算我也不会
但是最后一次gap1时(此时很接近有序)
直接插入排序消耗n
时间复杂度大致为 O(N^1.3)即N的1.3次方
②空间复杂度
由于不需要额外的空间所以空间复杂度为O(1) 这篇文章就到这里啦
(๑′ᴗ‵๑) Lᵒᵛᵉᵧₒᵤ❤
