网站建设公司招网站设计,python 网站开发 pdf,凡科建站弊端,中国最强十大央企排名引导
今天开始介绍我们在工作中经常遇到的算法--排序。排序算法有很多#xff0c;我们主要介绍以下几种#xff1a;
冒泡排序
插入排序
选择排序
归并排序
快速排序
计数排序
基数排序
桶排序
我们需要了解每一种算法的定义以及实现方式#xff0c;并且掌握如何评…引导
今天开始介绍我们在工作中经常遇到的算法--排序。排序算法有很多我们主要介绍以下几种
冒泡排序
插入排序
选择排序
归并排序
快速排序
计数排序
基数排序
桶排序
我们需要了解每一种算法的定义以及实现方式并且掌握如何评价一个排序算法。今天我们来学习冒泡排序插入排序选择排序。
如何评价排序算法
评价算法的优劣主要从以下几个方面考虑
最好情况最坏情况平均情况时间复杂度时间复杂度的系数低阶常系数都需要考虑进去是否是原地排序算法是否稳定
第一点毋庸置疑是我们主要的依判方式
第二点,我们常常在计算复杂度时会忽略低阶和常系数。这是因为当数据量很大n趋向于无穷时。但是在实际工作中我们的数据量不会这么大。所以这些低阶和常数就需要考虑进去了。
第三点原地排序就是对空间复杂度的一种描述当排序算法的空间复杂度为O(1)时我们就称为原地排序
第四点算法的稳定指的时排序之后是否会将值相同的数据对象改变位置。比如13157932,这组数据进行排序之后3(2)还会在3(1)之后吗 算法的稳定性主要是用于对一组数据进行多次排序时进行参考。比如你要将一组数据按照时间和值大小按照时间从先到后值从小到大进行排序。一般是按照时间排序在对值进行排序。但是如果在进行值排序时使用的是不稳定的算法那么就会出现问题。值相等但时间可能有错误
冒泡排序
冒泡排序原理
比较相邻的元素。如果第一个比第二个大就交换他们两个。对每一对相邻元素做同样的工作从开始第一对到结尾的最后一对。在这一点最后的元素应该会是最大的数。针对所有的元素重复以上的步骤除了最后一个。持续每次对越来越少的元素重复上面的步骤直到没有任何一对数字需要比较。 int bubblesort(int a[],int len) { int i,j0; int temp 0; for(i 0; i len ; i) { for(j 0 ; j len - i - 1 ; j) { if(a[j] a[j1]) { temp a[j]; a[j] a[j1]; a[j1] temp; } } } return 0; }
以上是一般的冒泡排序代码但是可以稍微优化一下 int bubblesort(int a[],int len) { int i,j0; int temp 0; int flag 0; for(i 0; i len ; i) { flag 0; for(j 0 ; j len - i - 1 ; j) { if(a[j] a[j1]) { flag 1; temp a[j]; a[j] a[j1]; a[j1] temp; } } if(flag 1) break; } return 0; } 该优化过的代码加了一个判断标志当某一次冒泡没有进行数据交互说明剩下的都是排好序了。故可以直接退出。
分析
时间复杂度通过代码实现我们可以知道冒泡排序的复杂度为O((1n)*n/2)。
空间复杂度由于只有一个temp的额外变量故空间复杂度为O(1),为原地排序。
稳定性:我们在判断时只要确保a[j]a[j1]为判断条件即可保证稳定性。
总结冒泡排序是原地排序并且稳定复杂度为O((1n)*n/2)的算法。
插入排序 插入排序原理比较难描述类似于我们斗地主理牌的过程原先是乱序的左边第一个作为依据依次在乱序中找第一个放到有序中。 int insertsort(int a[],int len) { // 插入排序a表示数组n表示数组大小 if (len 1) return; int i 0; for (i 1; i len; i) { int value a[i]; int j i - 1; // 查找插入的位置 for (; j 0; --j) { if (a[j] value) { a[j1] a[j]; // 数据移动 } else { break; } } a[j1] value; // 插入数据 } }
分析
复杂度通过代码可知插入排序的复杂度比较难以计算但可以确定的是O(n^2)。
空间复杂度O(1),故是原地排序
稳定性判断条件是a[j] value即可保证稳定性
总结插入排序是原地排序具有稳定性的算法。
选择排序
选择排序原理
设置最值位置标记逐轮扫描未排序部分元素最值。每一轮扫描过程中以未排序部分首部元素为基准(将位置标记设置为未排序首元素下标)与后续元素进行比较。遇到更小(或更大)的元素则将位置标记修改为其下标直至扫描完成将标记位置的元素与未排序部分首元素交换位置。至多进行n-1轮扫描序列完全有序。
其实我认为选择排序和插入排序类似它比较的操作是在无序中在无序中找到最值。插入排序是在有序中比较将新值放到合适的地方。 int selectsort(int a[],int len) { if (len 1) return 0; int i 0; int j 0; int index 0; int temp 0; for(i 0 ; i len ;i ) { for(j i ,index i; j len; j ) { if(a[index] a[j]) index j; } temp a[i]; a[i] a[index]; a[index] temp; } return 0; }
分析空间复杂度为O(1),原地排序时间复杂度为O(n^2)。稳定性不稳定。因为找到最小值之后需要于无序中的首元素交换这里会出现不稳定现象。例如
比如 58529 这样一组数据使用选择排序算法来排序的话第一次找到最小元素 2与第一个 5 交换位置那第一个 5 和中间的 5 顺序就变了所以就不稳定了。
总结选择排序是原地排序复杂度为O(n^2),不稳定的算法
归并排序
归并操作的工作原理如下
如果要排序一个数组我们先把数组从中间分成前后两部分然后对前后两部分分别排序再将排好序的两部分合并在一起这样整个数组就都有序了。
其中的问题就是如何获取两个排好序的部分当数组长度变为1是不是就已经相当于排好序了实际上不需要再排序这个时候再将长度为1的数组合并到一起就变成了长度为2的有序数组。 int merge(int a[],int left , int mid, int right) { int * arr (int *)malloc(sizeof(int)* (right-left1)); memset(arr,0,sizeof(int)*(right-left1)); int i left; int j mid1; int m 0; while(i mid j right) { if(a[i] a[j]) { arr[m] a[i]; } else { arr[m] a[j]; } } if(imid) { for(; j right ; j) arr[m] a[j]; } else { for(; i mid ; i) arr[m] a[i]; } for(i 0 ; i right - left; i) a[lefti] arr[i]; return 0; } int mergesort_separate(int a[], int start, int end) { if(start end) return 0; int i (int) ((startend)/2); mergesort_separate(a,start,i); mergesort_separate(a,i1,end); merge(a,start,i,end); } int mergesort(int a[],int len) { mergesort_separate(a,0,len-1); }
其中merge()函数是核心。需要好好品味。
分析
从归并算法的实现中我们依旧从稳定性是否是原地排序时间复杂度来分析。
稳定性我们知道merge()函数包括主要的数据搬移工作只要保证这里稳定即可。是可以满足的。所以归并排序是稳定算法。
原地排序在merge()函数中我们需要将两个有序数组合并需要用到额外的临时数组故空间复杂度是O(n),故归并排序不是原地排序
时间复杂度我们知道归并排序的时间复杂度是O(nlogn)但是至于怎么推导出来的肯定很多人都处于茫然状态。这里我就稍微推导一下看不懂没有关系。 假设数据量为n归并排序的复杂度为T(n),由于归并排序的思路是将大问题分解为小问题 再将小问题的结果合并。 故T(n) T(n/2)T(n/2)n;其中n表示将结果合并消耗的时间。 T(n) 2 *T(n/2)n 4* T(n/4)4n 8T(n/8)8n *T(n) 2^kT(n/2^k)2^k* n 当 n/2^k1时T(n) 2^k2^k*n将k带入得T(n) lognn*lognn*logn。
故归并排序的时间复杂度为O(n*logn);
快速排序
快速排序原理
如果要排序数组中下标从 p 到 r 之间的一组数据我们选择 p 到 r 之间的任意一个数据作为 pivot分区点。我们遍历 p 到 r 之间的数据将小于 pivot 的放到左边将大于 pivot 的放到右边将 pivot 放到中间。
经过这一步骤之后数组 p 到 r 之间的数据就被分成了三个部分前面 p 到 q-1 之间都是小于 pivot 的中间是 pivot后面的 q1 到 r 之间是大于 pivot 的 int sort(int a[],int start, int end) { int target a[end]; int i start; int j start; int temp 0; for(j start ; j end ; j) { if(a[j] target) { temp a[i]; a[i] a[j]; a[j] temp; i; } } temp a[i]; a[i]target; a[end] temp; return i; } int quicksort(int a[], int start, int end) { if(start end) return 0; int mid sort(a,start,end); quicksort(a,start,mid-1); quicksort(a,mid1,end); }
分析
稳定性在快速排序中需要对数组进行搬移比如6876,354,会发生不稳定。所以快速排序是不稳定。
原地排序由于交换数据时只需要一个临时变量空间复杂度为O(1),故快速排序是原地排序。
时间复杂度同归并排序同理快速排序的事件复杂度也是O(n*logn)。
注意快速排序 在大部分情况下的时间复杂度都可以做到 O(nlogn)只有在极端情况下才会退化到 O(n^2)。
问题O(n) 时间复杂度内求无序数组中的第 K 大元素
思路一般情况下我们需要先进行排序再通过下标直接访问。虽然数组的访问复杂度是O(1),但是排序较为耗时即使使用归并排序和快速排序也是O(n*logn)。 既然该题出现在这里很容易想到会用到归并排序和快速排序。比较一下两者实现的原理发现快速排序比较适合这道题。当我们sort()返回的mid等于K-1。是不是就表示a[mid],就是第K大的元素mid左边由K-1个数都比mid小。虽然不是有序但没有影响。当mid1K时说明第K大的元素在[mid1,end]之间。反之在[start,mid-1]之间。 int sort(int a[],int start, int end) { int target a[end]; int i start; int j start; int temp 0; for(j start ; j end ; j) { if(a[j] target) { temp a[i]; a[i] a[j]; a[j] temp; i; } } temp a[i]; a[i]target; a[end] temp; return i; } int findKnum(int a[], int start ,int end,int K) { int mid sort(a,start,end); int result 0; if(mid1 K ) { result a[mid]; } else if(mid1 K) { result findKnum(a,mid1,end,K); } else { result findKnum(a,start,mid-1,K); } return result; } int main() { int a[10]{1,3,5,7,4,9,10,8,6,2}; printf(%d\n,findKnum(a,0,9,6)); return 0; }
分析为什么该解法的复杂度是O(n)呢
假设复杂度为T(n),我们已知sort的复杂度是O(n),当我们第一次没有找到正确元素是我们只需在n/2个数据中进行查找。同理接下来的复杂度是n/4,n/8...直至数组长度为1及找到对应数据最坏情况。这很明显是等比数列。T(n)2n-1O(n)。
桶排序
桶排序原理核心思想是将要排序的数据分到几个有序的桶里每个桶里的数据再单独进行排序。桶内排完序之后再把每个桶里的数据按照顺序依次取出组成的序列就是有序的了。
复杂度为什么是O(n)?
如果要排序的数据有 n 个我们把它们均匀地划分到 m 个桶内每个桶里就有 kn/m 个元素。每个桶内部使用快速排序时间复杂度为 O(k * logk)。m 个桶排序的时间复杂度就是 O(m * k * logk)因为 kn/m所以整个桶排序的时间复杂度就是 O(n*log(n/m))。当桶的个数 m 接近数据个数 n 时log(n/m) 就是一个非常小的常量这个时候桶排序的时间复杂度接近 O(n)。
注意
上述的情况是桶排序最好的情况即每个桶中的数据均匀。最坏情况所有数据都集中再一个桶中的话那么复杂度就会退化到O(nlogn)我觉得桶排序的思想并不困难关键在于元素值域的划分也就是值到桶之间的映射规则。(确定规则之后就可以确定桶的数量f(max) - f(min)1)。实际上桶排序是用空间换时间来提高处理速度的。 #includestdlib.h #includestdio.h #includestring.h int sort(int a[],int start, int end) { int target a[end]; int i start; int j start; int temp 0; for(j start ; j end ; j) { if(a[j] target) { temp a[i]; a[i] a[j]; a[j] temp; i; } } temp a[i]; a[i]target; a[end] temp; return i; } int quicksort(int a[], int start, int end) { if(start end) return 0; int mid sort(a,start,end); quicksort(a,start,mid-1); quicksort(a,mid1,end); } int insertnum(int a[],int len,int num) { int i 0; while(ilen) { if(a[i]0) { a[i] num; break; } i; } return 0; } int main() { int a[20]{1,3,5,7,4,9,10,8,6,2,12,13,15,14,17,16,19,18,20,11}; //这个二位数组是我们根据数据源分析出来的 int buket[5][5] {0}; int i 0; for(i 0 ; i 20 ; i) { insertnum(buket[a[i]/5],5,a[i]); } for(i 0 ; i 5 ;i ) quicksort(buket[i],0,4); int j 0; for(i 0 ; i 5 ; i ) { for(j 0 ; j 5 ; j ) buket[i][j] 0 ? :printf(%d\n,buket[i][j]); } return 0; }
分析 由于数据源较为简单和均匀所以我选择间隔为5作为映射函数。将数据放到[0,4]5个桶中再将每个桶中的数据进行排序再一次将五个桶中的数据依次输出。 桶排序只要映射函数合理那么其复杂度是O(n),这一点我们已经介绍过了。 桶排序需要额外的内存用于桶空间复杂度是O(nm),其中m是桶的个数。 桶排序在将数据隐射到桶的过程是稳定的。但是在排序的过程中如果你选择的是快速排序就不是稳定的了如上面的例子。若选择归并排序就是稳定排序。
计数排序
计数排序和桶排序的原理类似更像是特例 当要排序的 n 个数据所处的范围并不大的时候比如最大值是 k我们就可以把数据划分成k个桶。每个桶内的数据值都是相同的省掉了桶内排序的时间。 int findmaxmin(int a[],int len, int*max ,int *min) { if(len 0) return 0; int i 0; *max a[0]; *min a[0]; for(i 0; i len ; i) { if(a[i] *max) *max a[i]; else if(a[i] *min) *min a[i]; } return 0; } int countsort(int a[],int len) { int max,min 0; findmaxmin(a,len,max,min); int *count (int *) malloc((max-min1)*sizeof(int)); memset(count,0,(max-min1)*sizeof(int)); int i 0 ; for(i 0 ; i len ; i) count[a[i]-min]; / *count* / for(i 1 ; i max-min1 ; i) count[i] count[i-1]; int *target (int * **) malloc(len**sizeof(int)); * memset(target,0,len* sizeof(int)); for(i 0 ; i len ; i) { target[--count[a[i] - min]] a[i]; } memcpy(a,target,sizeof(int)*len); free(count); free(target); } int main() { int a[20]{10,12,11,13,13,15,14,12,11,14,15,15,14,13,12,11,13,12,10,10}; countsort(a,20); int i 0; for(i 0 ; i 20 ; i ) { printf(%d\n,a[i]); } return 0; }
分析 计数排序的时间复杂度为O(n),在算法的过程中涉及到了4个循环.第一个是在数据源中找到最大最小值第二次循环是遍历数据源统计数据出现的次数第三次遍历确认数据的位置第四次遍历是进行排序。
计数排序的空间复杂度是O(nmax-min)。故不是原地排序。 计数排序在进行排序时在第四个循环中进行的。若判断条件为for(i len -1 ; i 0 ; i-- )排序就是稳定的。否则就不是稳定的。 注意计数排序只能用在数据范围不大的场景中如果数据范围 k 比要排序的数据 n 大很多就不适合用计数排序了。而且计数排序只能给非负整数排序如果要排序的数据是其他类型的要将其在不改变相对大小的情况下转化为非负整数。
基数排序
基数排序原理其原理是将整数按位数切割成不同的数字然后按每个位数分别比较。 我觉得基数排序和计数排序类似不过计数排序要求数据范围max和min的差距不要太大。但是当数据范围很大时很明显计数排序和桶排序就不能在使用了。而基数排序就是从位的角度切入到计数排序。 #includestdlib.h #includestdio.h #includestring.h int findmaxbit(int a[],int len) { if(len 0) return 0; int bit 0; int temp bit; int i 0 ; int num 0; for(i 0 ; i len ; i) { num a[i]; temp 0; while(num ! 0 ) { num/10; temp; } if(temp bit) bit temp; } return bit; } int basesort(int a[],int len) { int max,min 0; int bit findmaxbit(a,len); int *temp (int* )malloc(sizeof(int)*len); int count[10] {0}; int i 0; int j 0; int radix 1; for(j 0 ; j bit ; j) { memset(count,0,sizeof(int)*10); memset(temp,0,sizeof(int)*len); for(i 0 ; i len ; i) count[((int) a[i]/radix) %10]; for(i 1 ; i 10 ; i) count[i] count[i-1]; for(i len -1 ; i 0 ; i--) temp[--count[((int) a[i]/radix) %10]]a[i]; memcpy(a,temp,sizeof(int)len); * radix* 10; } free(temp); return 0; } int main() { int a[10]{56,123,12315,5312366,1234783,245671,123421,568421,643261,93458}; basesort(a,10); int i 0; for(i 0 ; i 10 ; i ) { printf(%d\n,a[i]); } return 0; }
分析
基数排序的时间复杂度是O(n)。
基数排序的空间复杂度是O(n),相对于前两者减少了一些所以不是原地排序。
基数排序涉及到数据的搬移和计数排序相似故基数排序也是稳定排序。 注意基数排序对要排序的数据是有要求的需要可以分割出独立的“位”来比较而且位之间有递进的关系如果 a 数据的高位比 b 数据大那剩下的低位就不用比较了。除此之外每一位的数据范围不能太大要可以用线性排序算法来排序否则基数排序的时间复杂度就无法做到 O(n) 了。
总结 本章我们接触了冒泡排序插入排序选择排序了解了其定义和代码实现 也介绍了如何评价排序算法的依据。其中冒泡排序和插入排序是稳定的选择排序是不稳定的。
冒泡排序和插入排序相比较而言其中的交换数据操作较多
冒泡 Cif(a[j] a[j1]) { flag 1; temp a[j]; a[j] a[j1]; a[j1] temp; }
插入 Cif (a[j] value) { a[j1] a[j]; // 数据移动 } else { break; }
故综上所述这三个算法的优先级插入排序冒泡排序选择排序。 归并排序和快速排序两者的时间复杂度都是O(n*logn)。但是由于归并排序并不是原地排序所以消耗内存较多。而快速排序是原地排序解决了归并排序消耗内存较多的问题。快速排序是不稳定的算法归并排序是稳定算法。 归并排序在任何情况下时间复杂度都是O(nlogn);快速排序虽然在最坏情况下的时间复杂度为O(n^2),但大部分情况下的复杂度都是O(nlogn)。 桶排序计数排序基数排序。它们的空间复杂度都是O(n),因为它们不涉及到比较操作每个元素之间比较并且利用了额外的空间得到了很高的效率。虽然这三种排序拥有很高的效率但是它们的适用情景较少对数据要求较为严苛。
桶排序要求数据均匀分布或者能够给予一个优秀的映射函数。
计数排序要求数据源中最大值和最小值的范围较小。
基数排序要求数据源是正正数并且范围不能太大。
