个门户网站,哈尔滨网站建设工作室,商标查询官方入口,应用市场哪个好目录
排序
概念
运用
常见排序算法
插入排序
直接插入排序
思想#xff1a;
步骤#xff08;排升序#xff09;:
代码部分#xff1a;
时间复杂度#xff1a;
希尔排序
思路
步骤
gap的取法 代码部分#xff1a;
时间复杂度#xff1a;
选择排序
直接选…目录
排序
概念
运用
常见排序算法
插入排序
直接插入排序
思想
步骤排升序:
代码部分
时间复杂度
希尔排序
思路
步骤
gap的取法 代码部分
时间复杂度
选择排序
直接选择排序
排升序思路
排升序步骤
代码部分
时间复杂度
堆排序
代码部分
交换排序
冒泡排序
代码部分
快速排序递归版本
思路
hoare版本
排升序步骤
相遇问题
代码部分
挖坑法版本
排升序思路
代码部分
前后指针版本
排升序思路
代码部分
时间复杂度
快速排序非递归版本
思路
注意
编辑
代码部分(找基准值部分用的是前后指针方法)
归并排序
思路
排升序步骤
代码部分
时间复杂度
非比较排序
计数排序
思路
代码部分
时间复杂度
排序算法复杂度及稳定性分析 排序
概念
排序就是将一段记录按照其中的某个或某些关键字大小实现递增或递减的操作
运用
排序在我们的生活中运用也是极其广泛的如在购物软件中根据不同条件来筛选商品大学院校的排名……等等
常见排序算法 插入排序
直接插入排序
思想
把待排序的记录按其关键码值的大小逐个插入到⼀个已经排好序的有序序列中直到所有的记录插入完为止得到⼀个新的有序序列
这种排序算法类似于玩扑克牌就是依次将手中的牌进行排序
步骤排升序:
1、先取出第二张牌与第一张进行比较小的放前面大的放后面
2、让后面的牌再进行上面那一步
这样看起来会比较抽象举一个例子来实现就容易理解了 代码部分
void InsertSort(int* arr, int n)
{for (int i 0; i n - 1; i){int end i;int temp arr[end 1];while (end 0){if (arr[end] temp){arr[end 1] arr[end];end--;}else{break;}}arr[end 1] temp;}
}时间复杂度
直接插入排序的时间复杂度为O(N^2)但在一般情况下是不会达到N^2的只有在排序数组与要求排序方向相反时也就是逆序才会达到O(N^2)
这也就导致了一个问题在面对逆序情况下使用该排序算法效率就会大大降低
面对这种情况前人就在直接插入排序算法的基础上进行了改良也就是接下来要讲的——希尔排序
希尔排序
根据上面的直接插入排序算法我们可以知道在面对逆序数组时算法复杂度太大了O(N^2),
所以前人就在该算法基础上进行了改良
思路
先选定一个整数命名为gap通常是gapn/31将带排序数组中元素根据gap值分为多组也就是将相距gap值的元素分在同一组中然后对每一组的元素进行排序这是就完成一次排序然后gapgap/31再将数组根据gap值分为多组进行插入排序当gap1时就相当于进行直接插入排序算法。
步骤
步骤一当gap1
1、将数组根据gap分为多组
2、将相距gap值的元素进行比较
注步骤一也可以称为预排序目的是为了将数组转变为一个相对有序的情况避免直接插入排序在面对逆序数组情况时时间复杂度变大
排升序时小的元素在前面大的元素在后面
排降序时大的元素在前面小的元素在后面
步骤二当gap1
就相当于进行直接插入排序
举例可知 gap的取法
gap值的最初值取该数组的长度当它进入while循环时就先进行gapgap/1
然而为什么是对gap/3而不是除以其他值呢
如果gap除以的值过小的话比如gapgap/2就会导致分的组太少而每组内元素比较次数过多while循环次数也会增多因为gap值要不断除以2直到gap1时停止while循环
如果gap除以的值过大的话比如gapgap/8就会导致分的组过多而每组内元素比较次数较少while循环次数少
所以gap除以的值要取适中的值3则是较好的值
那为何还要加一呢
加一的目的是为防止gap整除的值为0这样可以防止gap0时直接退出循环没有排序完全 代码部分
void ShellSort(int* arr, int n)
{int gap n;while (gap 1)//gap不能等于1如果为一进入循环在gap/31中就会一直为1就会死循环{gap gap / 3 1;for (int i 0; i n - gap; i){int end i;int temp arr[end gap];while (end 0){if (arr[end] temp){arr[end gap] arr[end];end - gap;}else{break;}}arr[end gap] temp;}}}
时间复杂度
希尔排序算法的时间复杂度不好计算大概为O(N^1.3)
选择排序
直接选择排序
排升序思路
每一次循环先从待排数组中找出最大和最小值将最小值与待排数组的起始位置交换最大值与待排数组的最后一个元素交换直到所有待排数组元素排完
排升序步骤
1、设立起始位置和最后一元素下标位置begin、end然后找到最大值和最小值下标
2、将最小值和起始元素交换、最大值和末尾元素交换
3、交换后begin、end--然后进行[begin,end]区间元素的排序按照上面两步
4、直到beginend时结束排序 注当begin与maxi、end与mini重叠时会造成重复交换所以就需要将maini和mini进行交换
代码部分
void SelectSort(int* arr, int n)
{int begin 0, end n - 1;while (begin end){int mini , maxi;mini maxi begin;for (int i begin 1; i end; i){if (arr[i] arr[maxi]){maxi i;}if (arr[i] arr[mini]){mini i;}}if (begin maxi){maxi mini;}Swap(arr[begin], arr[mini]);Swap(arr[end], arr[maxi]);begin;end--;}
}
时间复杂度
直接选择排序的时间复杂度很好理解为O(N^2)因为它的效率不是很好所以实际上很少会用到
堆排序
堆排序的讲解在前面的文章已经讲解过了就不在这里过多说明有兴趣的朋友可以移步
二叉树堆的建立和应用_二叉树的应用,两种创建方式-CSDN博客
代码部分
void AdJustDown(int* arr, int parent, int n)//向下调整
{int child parent * 2 1;while (child n){//这里左右孩子的比较cc1,交换建小堆;cc1,交换建大堆//建大堆先找大孩子建小堆先找小孩子if (child 1 n arr[child] arr[child 1]){child;}//建大堆//建小堆if (arr[child] arr[parent]){Swap(arr[child], arr[parent]);parent child;child parent * 2 1;}else{break;}}
}
void HeapSort(int* arr, int n)//向下调整算法建堆:时间复杂度O(n)
{//排升序建大堆//排降序建小堆//先建堆for (int i (n - 1 - 1) / 2; i 0; i--){AdJustDown(arr, i, n);}//再排序int end n - 1;while (end 0){Swap(arr[0], arr[end]);//交换堆顶和尾结点AdJustDown(arr, 0, end);end--;}} 交换排序
冒泡排序
冒泡排序大家应该都不陌生是我们C语言学习的第一个排序算法它的时间复杂度为O(N^2),
关于它的思路步骤我就不过多说明了它在实际当中也基本不会用到它是起着一种教学作用的排序算法
代码部分
void BubbleSort(int* arr, int n)
{int i 0;for (i 0; i n - 1; i){int j 0;int flag 1;for (j 0; j n - 1 - i; j){if (arr[j] arr[j 1]){int temp arr[j];arr[j] arr[j 1];arr[j 1] temp;flag 0;}}if (flag 1)//当提前完成排序后就直接退出循环{break;}}
} 快速排序递归版本
快速排序可以说是排序算法中最重要的排序算法在实际学习和工作中运用得最多接下来我们来好好学习快速排序算法
思路
任取待排数组中某一个元素作为基准值(key)然后将基准值放到正确位置上按照基准值将数组分割成两个序列左子序列中所有元素小于基准值右子序列中所有元素大于基准值这里排升序然后再对左右子序列重复该过程直到所有元素都排列再在相对应位置上为止
hoare版本
排升序步骤
1、找基准值
起始令首元素为基准值(key)设right和leftright为末尾元素下标left为首元素下标
让left从左往右找比基准值大的值right从右往左找比基准值大的值
找到以后将left与right指向的值进行交换这个交换的前提是rightleft
而当right小于left时right所指向的值就与key进行交换这时key就回到了正确的位置
2、二分
根据key所在位置对数组进行二分将数组分为左右两个子序列然后再对左右两个子序列进行上述操作 相遇问题
1、相遇点值小于基准值 由此可知当相遇点小于基准值时left依旧减减
2、相遇点值大于基准值 由此可知当相遇点大于基准值时right依旧加加
3、当相遇点值等于基准值 这种情况看似两种都可以但是当选择了right依旧减减时就会导致面对下面这种情况时时间复杂度大大提高 这种情况便是相遇点值与基准值相同的情况在这种情况下该排序算法的时间复杂度就会大大提高无法进行高效的分割排序
其实这也是这种hoare版本快速排序在面对待排数组中重复元素过多情况下的弊端
代码部分
int Hoare_QuickSort(int* arr, int left, int right)
{int keyi left;left;while (left right){//rigth从右往左找比基准值小的值while (leftright arr[right]arr[keyi])//这里的arr[rigth]arr[keyi]只能取大于号不能加上等于号//加上的话在面对数组全相等或有序数组时时间复杂度会变大{right--;}//left从左往右找比基准值大的值while (leftright arr[left]arr[keyi])//这里的情况和rigth是一样的{left;}if (left right)//当left还未大于rigth时就进行交换{Swap(arr[left], arr[right]);}}Swap(arr[right], arr[keyi]);keyi right;return keyi;
}void QuickSort(int* arr, int left, int right)//排升序
{if (left right){return;}//找基准值int keyi Hoare_QuickSort(arr, left, right);//二分//[left,keyi-1] keyi [keyi1,right]QuickSort(arr, left, keyi - 1);QuickSort(arr, keyi 1, right);}
挖坑法版本
排升序思路
设立左右指针left、right先将基准值视为第一个坑hole
right从右往左找比基准值小的数找到以后就放入到hole的位置然后righ处就为新的坑
left从左往右找比基准值大的数找到以后就放入到hole的位置然后left处就为新的坑
当rightleft时就将保存的基准值放入到两者相遇处
就这样便完成了第一次基准值的寻找
找到以后就和hoare版本一样进行二分
注
这种方法起始的left只能指向首元素
和hoare版本不同的是当right从右往左找比基准值小的值时当遇到比基准值大的或者等于的值时继续往左找left也是一样的 代码部分
int Hole_QuickSort(int* arr, int left, int right)
{int hole left;int key arr[hole];while (left right){while (leftright arr[right]key){right--;}//找到比基准值小的值arr[hole] arr[right];hole right;while (leftright arr[left]key){left;}//找到比基准值大的值arr[hole] arr[left];hole left;}//right和left相遇arr[hole] key;return hole;
}void QuickSort(int* arr, int left, int right)//排升序
{if (left right){return;}//找基准值int keyi Hole_QuickSort(arr, left, right);//二分//[left,keyi-1] keyi [keyi1,right]QuickSort(arr, left, keyi - 1);QuickSort(arr, keyi 1, right);}
前后指针版本
排升序思路
设立两个变量pcur(用于探路来找比基准值小的值)prev(在pcur的后面)
1、当找到比基准值小的值时prevprev所指向的元素和pcur所指向的元素交换然后pcur
2、当pcur所指向的元素没有比基准值小时pcur
当pcur越界(pcurright)时就将基准值与prev所指向的元素交换就这样就实现了将比基准值小的元素放在基准值左边大的放在右边
注
有时候prev后的值正好等于pcur这个时候就不需要发生交换 代码部分
int lomuto_QuickSort(int* arr, int left, int right)
{int prev left, pcur prev 1;int keyi left;while (pcur right){if (arr[pcur] arr[keyi]prev ! pcur){Swap(arr[prev], arr[pcur]);}pcur;}Swap(arr[prev], arr[keyi]);keyi prev;return keyi;
}void QuickSort(int* arr, int left, int right)//排升序
{if (left right){return;}//找基准值int keyi lomuto_QuickSort(arr, left, right);//二分//[left,keyi-1] keyi [keyi1,right]QuickSort(arr, left, keyi - 1);QuickSort(arr, keyi 1, right);}
时间复杂度
快速排序算法的时间复杂度为O(NlogN),在特殊情况下待排数组中重复元素很多的时候会到造成时间复杂度上升为O(N^2logN),这一点要记住这与如何解决这一情况在后面的文章中会着重讲解
快速排序非递归版本
我们讲解了递归版本的快速排序那也会有非递归版本的快速排序
在非递归版本的快速排序和递归版本的快速排序有什么区别呢
非递归版本的快速排序算法需要借助数据结构栈来实现
思路
我们首先需要建立一个栈然后
1、将数组的left和right下标入栈
2、进入一个循环(结束条件栈为空)将从栈中出来的两个元素命名为begin和end
3、然后对[begin,end]这个区间来找基准值找基准值的方法在上面已经说了三种方法随便用那个都行
4、找完以后根据基准值进行二分为左右两个子序列再将左右两个子序列的首尾下标入栈再重复上面的操作
注意
1、当begin大于或等于keyi-1或者end小于或等于keyi1时不进行入栈操作也就是只有在beginkeyi-1或endkeyi1的情况下才允许入栈操作
2、每次找完基准值后还要确定一次待排区间中下标是否都入栈了首尾下标要再入一次栈入栈条件也要满足上面的条件
3、建立了栈在排完序后就需要进行销毁
如果对栈还有所不解的朋友可以移步至【数据结构初阶】栈和队列的建立_实现线性表、栈和队列(要求顺序和链式两种实现)-CSDN博客
其实非递归版快速排序就是利用栈这一数据结构来模拟实现正常快速排序中的递归过程 代码部分(找基准值部分用的是前后指针方法)
void QuickSortNonR(int* arr, int left, int right)//非递归版本
{ST st;StackInit(st);StackPush(st, right);StackPush(st, left);while (!StackEmpty(st)){int begin StackTop(st);StackPop(st);int end StackTop(st);StackPop(st);int keyi lomuto_QuickSort(arr, begin, end);if (end keyi 1){StackPush(st, end);StackPush(st, keyi1);}if (begin keyi - 1){StackPush(st, keyi - 1);StackPush(st, begin);}}StackDestroy(st);}
归并排序
思路
将待排序数组不断进行二分直到划分为一个个有序的子序列然后再将这些子序列两两合并成一个有序数组
也就是先二分再合并
排升序步骤
1、二分
对数组取中间值(mid),进行二分要保证数组最左边下标left要小于最右边下标right(leftright)
mid left(right-left)/2
根据mid分为左右两个子序列([left,mid-1][mid1,right])
直到left大于或等于right时停止二分
2、合并
将相邻有序数组两两合并为一个有序数组并将这个有序数组存储在一个临时数组(temp)中
要注意的是每次放入临时数组结束后两个数组中可能会有元素没有放入到临时数组中所以循环结束后要对两个数组进行检查再进行一次放入临时数组
3、将临时数组中元素放回原先数组中 代码部分
void _MergeSort(int* arr, int left, int right, int* temp)
{//二分if (left right){return;}int mid left (right - left) / 2;_MergeSort(arr, left, mid,temp);_MergeSort(arr, mid1, right,temp);//合并int begin1 left, end1 mid;int begin2 mid1, end2 right;int i begin1;while (begin1 end1 begin2 end2){if (arr[begin1] arr[begin2]){temp[i] arr[begin1];}else{temp[i] arr[begin2];}}//两个区间可能还有元素没有入tempwhile (begin1 end1){temp[i] arr[begin1];}while (begin2 end2){temp[i] arr[begin2];}//将temp中元素放回原数组中for (int i left; i right; i){arr[i] temp[i];}
}void MergeSort(int* arr, int n)
{int* temp (int*)malloc(sizeof(int) * n);_MergeSort(arr, 0, n - 1, temp);free(temp);
}
时间复杂度
归并排序算法时间复杂度为O(NlogN)它二分的次数为logN次合并次数为N次
非比较排序
计数排序
思路
1、 先找出数组中的最大、最小值 用最大值和最小值来求出待排数组中元素的出现次数数组大小 用一次数组来存储元素出现次数count它的大小为range max-min1 2、 遍历数组求出待排数组中各个元素出现的次数 将每个元素和最小值相减可以得出它在countg数组中的下标则该对应下标存储的值就加一 3、 根据count数组向原数组中放入元素 arr[index] i min 注
当min和max跨度很大时就会造成空间的浪费那就不适合这种算法 代码部分
void CountSort(int* arr, int n)
{//先找最大值和最小值int max arr[0], 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 range max - min 1;int* count (int*)malloc(sizeof(int) * range);if (count NULL){perror(malloc,fail!);}//初始化数组memset(count, 0, sizeof(int*) * range);//统计次数for (int i 0; i n; i){count[arr[i] - min];}//将count中出现的次数还原到原数组中int index 0;for (int i 0; i range; i){while (count[i]--){arr[index] i min;}}
}
时间复杂度 计数排序在数据范围集中时效率很高但是适用范围及场景有限 它的时间复杂度为O(Nrange) 排序算法复杂度及稳定性分析 稳定性假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录 的相对次序保持不变即在原序列中r[i]r[j]且r[i]在r[j]之前⽽在排序后的序列中r[i]仍在r[j] 之前则称这种排序算法是稳定的否则称为不稳定的。 排序方法平均情况最好情况最坏情况辅助空间稳定性冒泡排序O(N^2)O(N)O(N^2)O(1)稳定直接选择排序O(N^2)O(N^2)O(N^2)O(1)不稳定直接插入排序O(N^2)O(N)O(N^2)O(1)稳定希尔排序O(NlogN)~O(N^2)O(1.3)O(N^2)O(1)不稳定堆排序O(NlogN)O(NlogN)O(NlogN)O(1) 不稳定 归并排序O(NlogN)O(NlogN)O(NlogN)O(N)稳定快速排序O(NlogN)O(NlogN)O(N^2)O(logn)~O(N)不稳定 文章转载自： http://www.morning.cnvlog.cn.gov.cn.cnvlog.cn http://www.morning.trqzk.cn.gov.cn.trqzk.cn http://www.morning.xkqjw.cn.gov.cn.xkqjw.cn http://www.morning.zglrl.cn.gov.cn.zglrl.cn http://www.morning.zhishizf.cn.gov.cn.zhishizf.cn http://www.morning.rxlk.cn.gov.cn.rxlk.cn http://www.morning.cknsx.cn.gov.cn.cknsx.cn http://www.morning.wdlg.cn.gov.cn.wdlg.cn http://www.morning.lveyue.com.gov.cn.lveyue.com http://www.morning.pqkgb.cn.gov.cn.pqkgb.cn http://www.morning.gnghp.cn.gov.cn.gnghp.cn http://www.morning.qtsks.cn.gov.cn.qtsks.cn http://www.morning.ygwyt.cn.gov.cn.ygwyt.cn http://www.morning.lsqmb.cn.gov.cn.lsqmb.cn http://www.morning.ltxgk.cn.gov.cn.ltxgk.cn http://www.morning.qjsxf.cn.gov.cn.qjsxf.cn http://www.morning.bwzzt.cn.gov.cn.bwzzt.cn http://www.morning.nyzmm.cn.gov.cn.nyzmm.cn http://www.morning.jtqxs.cn.gov.cn.jtqxs.cn http://www.morning.rwmq.cn.gov.cn.rwmq.cn http://www.morning.rfbq.cn.gov.cn.rfbq.cn http://www.morning.cpqwb.cn.gov.cn.cpqwb.cn http://www.morning.wmnpm.cn.gov.cn.wmnpm.cn http://www.morning.jzmqk.cn.gov.cn.jzmqk.cn http://www.morning.fktlg.cn.gov.cn.fktlg.cn http://www.morning.ydgzj.cn.gov.cn.ydgzj.cn http://www.morning.qwnqt.cn.gov.cn.qwnqt.cn http://www.morning.cmfkp.cn.gov.cn.cmfkp.cn http://www.morning.pxbky.cn.gov.cn.pxbky.cn http://www.morning.bnqcm.cn.gov.cn.bnqcm.cn http://www.morning.rzcfg.cn.gov.cn.rzcfg.cn http://www.morning.nnrqg.cn.gov.cn.nnrqg.cn http://www.morning.whpsl.cn.gov.cn.whpsl.cn http://www.morning.qfbzj.cn.gov.cn.qfbzj.cn http://www.morning.wphzr.cn.gov.cn.wphzr.cn http://www.morning.mmsf.cn.gov.cn.mmsf.cn http://www.morning.ityi666.cn.gov.cn.ityi666.cn http://www.morning.pmrlt.cn.gov.cn.pmrlt.cn http://www.morning.jbpdk.cn.gov.cn.jbpdk.cn http://www.morning.stflb.cn.gov.cn.stflb.cn http://www.morning.mtsck.cn.gov.cn.mtsck.cn http://www.morning.tpnx.cn.gov.cn.tpnx.cn http://www.morning.qqbjt.cn.gov.cn.qqbjt.cn http://www.morning.wplbs.cn.gov.cn.wplbs.cn http://www.morning.xkgyh.cn.gov.cn.xkgyh.cn http://www.morning.glrzr.cn.gov.cn.glrzr.cn http://www.morning.splcc.cn.gov.cn.splcc.cn http://www.morning.pcgjj.cn.gov.cn.pcgjj.cn http://www.morning.bxbnf.cn.gov.cn.bxbnf.cn http://www.morning.xrqkm.cn.gov.cn.xrqkm.cn http://www.morning.bgdk.cn.gov.cn.bgdk.cn http://www.morning.wklrz.cn.gov.cn.wklrz.cn http://www.morning.wddmr.cn.gov.cn.wddmr.cn http://www.morning.rlwcs.cn.gov.cn.rlwcs.cn http://www.morning.tbplf.cn.gov.cn.tbplf.cn http://www.morning.jpdbj.cn.gov.cn.jpdbj.cn http://www.morning.gydth.cn.gov.cn.gydth.cn http://www.morning.cmhkt.cn.gov.cn.cmhkt.cn http://www.morning.gjxr.cn.gov.cn.gjxr.cn http://www.morning.byywt.cn.gov.cn.byywt.cn http://www.morning.xwbld.cn.gov.cn.xwbld.cn http://www.morning.cwjsz.cn.gov.cn.cwjsz.cn http://www.morning.tqpr.cn.gov.cn.tqpr.cn http://www.morning.wnjbn.cn.gov.cn.wnjbn.cn http://www.morning.fqmbt.cn.gov.cn.fqmbt.cn http://www.morning.wqnc.cn.gov.cn.wqnc.cn http://www.morning.dshkp.cn.gov.cn.dshkp.cn http://www.morning.cbynh.cn.gov.cn.cbynh.cn http://www.morning.twgzq.cn.gov.cn.twgzq.cn http://www.morning.lwhsp.cn.gov.cn.lwhsp.cn http://www.morning.byzpl.cn.gov.cn.byzpl.cn http://www.morning.dbcw.cn.gov.cn.dbcw.cn http://www.morning.fwlch.cn.gov.cn.fwlch.cn http://www.morning.sxtdh.com.gov.cn.sxtdh.com http://www.morning.nfpkx.cn.gov.cn.nfpkx.cn http://www.morning.pxwzk.cn.gov.cn.pxwzk.cn http://www.morning.whothehellami.com.gov.cn.whothehellami.com http://www.morning.srkwf.cn.gov.cn.srkwf.cn http://www.morning.qnyf.cn.gov.cn.qnyf.cn http://www.morning.zdwjg.cn.gov.cn.zdwjg.cn
