交易网站建设计划书,linux服务器比windows服务器 运行wordpress,珠海网站建设多少钱,淘宝店群软件定制开发排序种类排序特性代码背景 基于插入的排序直接插入排序原理代码 折半查找排序2路查找排序希尔排序(shell) 缩小增量排序原理代码 基于交换的排序冒泡排序原理代码 快速排序#xff08;重要!#xff09;原理我的思考 代码 基于选择的排序#xff08;简单#xff09;选择排序… 排序种类排序特性代码背景 基于插入的排序直接插入排序原理代码 折半查找排序2路查找排序希尔排序(shell) 缩小增量排序原理代码 基于交换的排序冒泡排序原理代码 快速排序重要!原理我的思考 代码 基于选择的排序简单选择排序原理代码 堆排序原理思考 代码 其他排序归并排序2路归并原理思考 代码 基于统计的排序 总结 本文是我学习排序算法的笔记包含了知识点归纳、我对算法的思考、我的代码 如有误欢迎指出 本文使用语言C 排序种类
基于插入直接插入排序算法、希尔排序算法 基于交换冒泡排序算法、快速排序算法 基于选择简单选择排序算法、堆排序算法 其他归并排序、基于计数的排序 基于计数的排序无代码
排序特性
是否就地排序是内部排序还是外部排序(外部排序就是用到外存了如果排序的数据能一次放到内存中直接在内存排序不涉及与外存交互就是内部排序)稳定排序还是不稳定排序稳定排序就是“”的数据相对位置不用变化时间复杂度
文末有特性总结
代码背景 所有代码都用下方全局数组和main函数作测试 /*测试样例
20
23523 51345 1345314 9876 8765 2345 4 3 8 7
5 4 2349 1 54 29 53 98 275946382 305
*/
#include iostream
using namespace std;
int nums[105];
int n;
int main()
{//数组初始化cin n;for (int i 1; i n; i){cin nums[i];}//任何一个排序算法的函数调用一次//排序后展示for (int i 1; i n; i){cout nums[i] ;}cout endl;
}基于插入的排序
直接插入排序 特性就地、稳定看插入位置如何选择、O( n 2 n^2 n2) 原理
以数组第一个元素为有序区后面都算无序每一次有序区长度增加1将加入的元素顺序插入有序区中完成排序
代码
void straightInsertSort()
{int new_insert; //新插入数的值int insert_index; //新插入数的应该插入的位置for (int i 2; i n; i) //i表示有序区长度{new_insert nums[i]; //插入有序区的元素值insert_index i; //避免完全不需要插入导致insert_index 0 for (int j 1; j i; j){if(new_insert nums[j]) //找到需要插入的位置{insert_index j;break;}}for (int j i; j insert_index; j--)//从插入位置到有序区末尾整体向右滑动{nums[j] nums[j-1];}nums[insert_index] new_insert;}
}折半查找排序
查找需要插入位置时使用二分查找的方式优化效果很一bamn因为查找到之后的插入操作仍然是O(n) 特性就地、稳定看插入位置如何选择、O( n 2 n^2 n2) 2路查找排序
优化插入操作的时间复杂度用循环数组减少一半插入时间这样会让排序变成非就地的然而还是O(N)效果依旧一bamn 特性就地、稳定看插入位置如何选择、O( n 2 n^2 n2) 希尔排序(shell) 缩小增量排序
会发现数据量少且基本有序时插入排序效率很高 特性就地、不稳定因为进行了跳跃的插入排序时间复杂度最坏时间复杂度O( n 2 n^2 n2)) 原理
那么将数组切分成多个小段依次插入排序这个时候每一段的数据量就很少然后依次将每一段拼起来拼起来的时候就是基本有序的情况
Q如何分段分组 A分d组就以d为增量先分n/2组排序减少到n/4组直到1组(取n/2就是希尔增量)
会发现希尔排序的作用就体现在数据量多时要将小的值插入左边可以很快地跳着插入因为每一组很小但其实在原数组上又很远如果是直接插入排序的话要挪一整条数据但是分组后只用挪一点点数据
Q那我怎么对每一个跳着连接的组排序比较方便 A以d为排序时插入的增量每插入完一次可以直接给另一个组进行插入就可以一个for循环给每个组都排序了
这时也会发现其实分组、排序过程中的组数都没必要算了只需要遍历增量就行
代码 void shellSort()
{int d n/2;int new_ins; //新插入的值while(d0){for (int i 1d; i n; i){new_ins nums[i];int j;for ( j i-d ; j 0 ; j- d)//从右往左找插入的位置刚好适合 基本有序 的情况下进行直接插入排序{if(nums[j] new_ins)nums[jd] nums[j];//后移elsebreak;}nums[jd] new_ins; //插入}d/2;//缩小增量}
}基于交换的排序
冒泡排序 特性就地、稳定、O( n 2 n^2 n2) 原理
每一次依次比较相邻元素把最大的值往最后交换
代码
优化本次循环完全排序好的情况
#include iostream
using namespace std;
int nums[105];
int n;void bubbleSort()
{bool sorted true;int tmp;for (int i 1; i n; i){sorted true; //优化已经完全排好序的情况那已经局部排序好的情况呢for (int j 1; j n - i; j){if (nums[j] nums[j 1])//交换{tmp nums[j];nums[j] nums[j 1];nums[j 1] tmp;sorted false;}}if (sorted)break;}
}优化局尾部已经排序好的情况确定出已经有序部分和⽆序部分的边界
void bubbleSort()
{int unSortedCnt n; //未排序的头部的长度乱序区长度int tmpUnSortedCnt n;int tmp;while (unSortedCnt 1) //未排序长度为1时即完全排好序了{for (int j 1; j unSortedCnt; j){if (nums[j] nums[j 1]) //交换{tmp nums[j];nums[j] nums[j 1];nums[j 1] tmp;tmpUnSortedCnt j; //更新最后一次更新时就表示当前j到n都是有序的}}if (tmpUnSortedCnt unSortedCnt)//没有更新说明已经完全排好序break;unSortedCnt tmpUnSortedCnt;}
}快速排序重要! 特性就地不稳定O(nlogn) 这里时间复杂度我的理解
每一层递归的时间复杂度O(n)
如果某时刻遍历到第 x x x 层此时数组被拆成 2 x 2^x 2x 份无论 2 x 2^x 2x 多大这一层需要进行的比较即类似下面代码中arr[i] x的判断都是n遍
即要走完数组内每一个元素其实不完全准确第 x x x 层的基准值到第 ( x 1 ) (x1) (x1)层的时候就不需要进行比较了
递归的趟数对应时间复杂度O(logn)原因参考下面我的思考
关于不稳定性 数组中出现3个相等值可能发生位置变化
原理
选一个基准 x x x 作“中点”把小于 x x x 的放 x x x 左边大于 x x x 的放右边依次继续在左右进行这个操作这个操作完成后基准 x x x 的位置就已经确定了这个基准 x x x 就是“已排序”状态了直到完成排序 实现 以左边为基准在尾部往头找比基准小的数在头部往尾部找比基准大的数依次交换
这个排序包含了递归的思想所以这会是个递归函数 举例 下面是定位一次基准值的步骤 最终得到 我的思考
快速排序思想里最核心的就是这个基准分界带来的倍增作用因为每一次把一个基准值定位成功都会让下一次时间复杂度为 O ( n ) O(n) O(n) 的一趟遍历定位基准值的数量翻倍注意但是如果这个基准值是当前区间的最值的话就不会翻倍
如上面的例子第一遍遍历确认了 30 30 30 的位置那么下一次遍历就会确认出 20 20 20 和 60 60 60 两个数所以遍历整个数组的趟数是 O ( l o g n ) O(logn) O(logn) 的这是清清楚楚一目了然的
可以看出快速排序的优秀之处就是作为一个基于交换的排序交换的时候会有位置互换这个过程就能产生“信息”比如基准值左边的值一定就在基准值左边那么左边遍历完会有一个定位结果右边就也一定会在耗时为 O ( n ) O(n) O(n) 的定位操作的过程中(就是选择的过程)让下一次同样的一次遍历通过交换定位出的基准位置得到的信息得到更多的定位结果以此提高效率
代码
/* 调用方式 quickSort(nums,1,n);
*/
void quickSort(int arr[],int l,int r)
{if(lr){int i l;int j r;int x arr[l];//为了避免每次交换需要用个tmp我选择每次和x比较最后再将x赋值到定位好的点while(ij){while( ij arr[j] x)j--;//从右往左找比x小的值if(ij) arr[i]arr[j];//需要判断一下避免已经ji了然后i导致jiwhile( ij arr[i] x)i;//从左往右找比x大的值if(ij) arr[j--]arr[i];}//最后还需要覆盖中间的基准值arr[i]x;quickSort(arr,l,i-1);quickSort(arr,i1,r);}
}基于选择的排序
简单选择排序 特性就地不稳定O( n 2 n^2 n2) 不稳定性来源于交换时是跳跃的比如{3,3,1}第一个3会跑到结尾
原理
每一次在待排序区中找最小的放到最左边依次直到待排序区长度为0
代码
void selectionSort()
{int min_p,tmp;for (int i 1; i n; i){min_pi;for (int j i1; j n; j){if(nums[j]nums[min_p]) min_pj;}tmp nums[i];nums[i] nums[min_p];nums[min_p] tmp;}
}堆排序 特性就地不稳定O(nlogn) 不稳定性显然堆的调整的跳跃性会让重复数据相对位置发生改变
原理
堆可以实现用 O ( l o g n ) O(logn) O(logn) 的时间复杂度调整出最小值来优化简单选择排序的效率
参考 大顶堆、小顶堆 这一篇可知用调整堆内子树的方式依次找最小值在第一次找到最小值用 O ( n l o g n ) O(nlogn) O(nlogn) 之后也就是堆初始化每一次找最小值只需要完成一次堆调整的操作 O ( l o g n ) O(logn) O(logn)执行剩下的 n − 1 n-1 n−1 次 原理 先初始化出小顶堆然后将顶列入已排序区将堆数组尾部的数组提到顶部进行 O ( l o g n ) O(logn) O(logn)的堆调整操作以此往复直到每个顶都依次进入排序区 实现 我的思路是为了排序的就地性这样操作作大顶堆把顶和数组尾部交换也就是已排序区是从数组尾部往头部生长的这个操作即完成了排序区的 fill in还完成了堆的更新下一步就可以直接开始堆调整操作了
图示最终就是从右往左依次变小就是升序了
思考
这个思路的逻辑感觉和快速排序也是有相通之处的快速排序让每次遍历排序的结果倍增而堆排序让每次选择的效率翻倍
因为选择排序要做工作是找到最值压如排序区往复
而找到最值的过程也是有“信息”的电脑记不住但我们可以用一个逻辑帮他组织出来堆排序用的就是堆的逻辑
对一个大顶堆 我们 拿去根结点 找到最值然后压入排序区然后我们替换根结点后维护大顶堆修复这个大顶堆 再次找到最值而因为大顶堆的树状结构我们找的新最大值已经在大顶堆根节点的左右手边上恭候多时了只是为了保证下一次大顶堆每一个子树也是这个准备就绪的状态需要 O ( l o g n ) O(logn) O(logn) 的维护时间因为是树每一次分支可以减少一半的判断堆的维护也就比较高效
那为什么C sort()函数优先用快速排序而不是堆排序呢
我没有做过调查研究但是可以猜测一下或许是在快速排序没有很坏的情况下操作步数大致是 n l o g n nlog{n} nlogn而堆排序因为数组自我初始化的过程就需要消耗大致 n 2 l o g n \frac{n}{2}logn 2nlogn 的步数了完了排序还要操作 n l o g n nlogn nlogn 遍可能会久一点很无脑的猜测……
代码
/// brief 维护大顶堆的函数对子树AA的子树都为大顶堆时维护A子树的大顶堆状态
/// param heap 堆数组
/// param i 子树A根节点索引
/// param n 子树A的最大索引值尾部叶子
void adjustDown(int heap[],int i,int n)
{int child_p 2 * i; //i结点在循环中是指对应调整的子树的孩子的索引int parent heap[i]; //本子树的根结点的值while (child_pn) //保证双亲是有孩子结点的叶子结点本身就是排好的堆不需要调整{if (child_p 1 n heap[child_p 1] heap[child_p]) child_p;//选中左右孩子中更小的和双亲作比较if (heap[child_p] parent){heap[child_p / 2] heap[child_p];//将孩子的值赋给父亲child_p * 2;}else{break;}}heap[child_p/2] parent;//这一步容易忘记就是赋回i结点的值当然如果每次比较完用tmp去做交换就可以不用这么麻烦我就是不想用tmp交换因为那样有三次赋值而这样写只有一次
}//堆排序代码
void heapSort()
{//初始化大顶堆for (int i n/2; i 0; i--){adjustDown(nums,i,n);}int tmp;for (int i 1; i n; i)//在in-1并开始循环时已排序区的长度为n-2循环结束时已排序区长n-1那头部也算是排好了无需in再循环一遍{//头部和尾部交换大顶堆的顶压如尾部已排序区tmp nums[1];nums[1]nums[n-i1];nums[n-i1]tmp;//维护头部未排序区的大顶堆此时只有根节点的树需要维护其他的已经在初始化时维护好了adjustDown(nums,1,n-i);}
}其他排序
归并排序2路归并 特性非就地稳定O(nlogn) 稳定性上因为没有跳跃的比较交换不会越过重复数据
原理 原理 我倾向不以先拆再合并的方式去理解他就是先以每一个单独的值作为已排好的数组然后两两相邻的合并排序最后合并成一个显然就是合并 O ( n l o g n ) O(nlogn) O(nlogn) 趟 实现 代码肯定还是从总数n出发所以拆分2份递归下去直到长度为1然后返回得到的2份合并即可本句搭配代码注释食用最佳
思考
先不说这个算法怎么做的问一个问题给你两个有序数组把他俩放一起排序要多久 O ( n m ) O(nm) O(nm) 两个指针怼着两个数组的头然后遍历就行了这就是归并排序的招式
所以就是线性复杂度的两两合并让已排序数组的长度翻倍达到的高效所以我认为功劳最大的是两已排序数组合并的线性时间复杂度而不是这个二分合并我也不知道咋叫但学过二分查找的应该看得懂吧_的思路是这个线性时间复杂度给了归并排序用二分思想的底气
但是但是这个有序数组合并的过程是需要开辟新的数组空间的原因如下 假设两数组为A、B假设在原数组 n u m s nums nums中A在左B在右AB相邻 A [ i ] B [ j ] A[i]B[j] A[i]B[j]并不能简单地将两者交换因为 B [ j ] B[j] B[j]到 A A A里面是有序的但是 A [ i ] A[i] A[i]到B里面就不一定了为了提高时间效率保证线性时间复杂度需要开辟新的内存空间
代码
/* 调用方式mergeSort(nums,1,n);
*/
void mergeSort(int nums[],int l,int r)
{if(lr) return; //直到长度为1然后返回int mid l(r-l)/2; //拆分2份mergeSort(nums,l,mid); //递归下去mergeSort(nums,mid1,r); //得到的2份合并即可int p1 l;int p2 mid1;int tmpNums[105]; //临时数组与原数组等长int i 1;while(p1mid p2r){if(nums[p1]nums[p2])tmpNums[i]nums[p2];elsetmpNums[i]nums[p1];}while(p1mid) tmpNums[i]nums[p1];while(p2r) tmpNums[i]nums[p2];i 1;for (int j l; j r; j)//记得把临时表赋值回原表{nums[j] tmpNums[i];}
}基于统计的排序
1. 计数排序 非就地不稳定可以优化为稳定的时间复杂度O(nb)b是count数组的长度但空间复杂度可能会很大因为用于计数的数组长度可能过大还可能导致时间复杂度大 原理
记录最小、最大值再记录从最小到最大值的所有数据的出现次数存在count数组中count数组依次从小到大输出对应次数的值完成排序 优化为稳定排序
用一个index数组作count的前缀和数组意义是 i i i 这个值对应于排序好之后的最大索引从原数组尾部遍历到头遇到一个值检索对应index数组的 “最大索引” 这就是他应该呆的实际位置然后对应index数组的 “最大索引” − 1 - 1 −1 即可
2. 桶排序 非就地稳定性、时间复杂度取决于桶内排序效率 原理
用数组内的值的范围分类如每100一类或每10一类这样就可以通过 n u m s [ i ] / 10 nums[i]/10 nums[i]/10来分类装在一个容器里容器内再用之前的那些各种排序最后合并
3. 基数排序 非就地稳定时间复杂度 O ( d × ( n b ) ) O(d\times(nb)) O(d×(nb))d是最大位数b是count数组长度10进制b10 原理以十进制为例
求出原数组的最高位最低位将所有数据补齐填充0到最高位从最低位开始直到最高位每一次对整个数组根据当前位数字进行稳定版本的计数排序即可这样相当于用不同位进行有优先级的排序优先级高位的数字 低位的数字 原来处于数组的顺序 总结
算法就地性稳定性时间复杂度直接插入OOO( n 2 n^2 n2)希尔排序OX最坏O( n 2 n^2 n2)冒泡排序OOO( n 2 n^2 n2)快速排序OXO( n l o g n nlogn nlogn)简单选择排序OXO( n 2 n^2 n2)堆排序OXO( n l o g n nlogn nlogn)归并排序XOO( n l o g n nlogn nlogn)计数排序XXO(nb)桶排序X取决于桶内排序取决于桶内排序基数排序XO O ( d × ( n b ) ) O(d\times(nb)) O(d×(nb))
