ThinkChat2.0新版上线,更智能更精彩,支持会话、画图、阅读、搜索等,送10W Token,即刻开启你的AI之旅 广告
# 排序算法 很多计算机科学家认为排序是算法研究中的最基础问题。这里将介绍几种排序算法并给出伪代码,及其运行时间分析。 ## 1.选择排序 假设有一系列数A,首先从序列A中找出一个最小数,并把它放在第一个数的位置,原来第一个数就放在最小数的位置。接下来,从剩余的数中找出最小数,交换位置---如此下去,当执行到倒数第二个数时,序列A就排好序(升序)。 先说下伪代码:A代表数组,下标从1到它的长度A.length;方法,条件,循环用空格隔开表示一个块结构;为什么用伪代码?我们写程序时不能局限于一种语言,并且伪代码能很容易被人看懂,只要有些写代码的经验的人呢就能看懂。 ~~~ choose_sort(A) 代价 次数 n=A.length c1 1 for i=1 to n-1 c2 n min = A[i] c3 n-1 m=1 c4 n-1 for j=i+1 to n c5 (2+n)(n-1)/2 if A[j]<min c6 n(n-1)/2 min=A[i] c7 m=j c8 temp=A[i] c9 n-1 A[i]=min c10 n-1 A[m]=temp c11 n-1 ~~~ 接下来,分析算法的运行时间: 对于一台特定的机器,算法中的每一步花费的时间都是一定。我们主要考虑每一步的执行次数。 如上所示,某些步骤的运行次数一定。对于长度为n的序列,如果序列刚好升序排好了,那么c7,c8的次数均为0; 如果序列刚好是降序排好了,那么c7,c8的次数均为你(n-1)/2,但这里我们只考虑最坏情况,这样就能使我们的运行时间更具说服力 总代价:(c5+c6+c7+c8)*n^2/2+(c2+c3+c4+c9+c9+c10+c11+c5-c6/2-c7/2-c8/2)*n+c1-(3/2)*c5-c3-c4,即a*n^2+b*n+c 由于对于一台机器代价一定,于是a,b,c是确定的,所以运行时间只有输入规模n所确定;当n很大很大时以至于n^2的系数,和低阶的项对于结果影响不大,就可以舍弃a和低阶项 因此,改算法的运行时间只有n^2决定,表示为O(n^2) ## 2.插入排序 一个已排好序的序列,我们可以把一个数插入到某个位置,使其序列升序排列。 一系列的数,我们可以以第一个数开始插入排序,因为一个数根本不用考虑排序问题 ~~~ insert_sort(A) n=A.length for i=2 to n for j=i-1 to 1 if A[j+1]<A[j] temp=A[j] A[j]=A[j+1] A[j+1]=temp ~~~ 时间复杂度为O(n^2) ## 3.冒泡排序 。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。 ~~~ bubble_sort(A) n=A.length a=true while a a=false for i=1 to n-1 if A[i]>A[I+1] a=true temp=A[i+1] A[i+1]=A[i] A[i]=temp 时间复杂度为O(n^2) ~~~ ## 4.归并排序 这里先介绍下分治法:就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。 将一系列数进行分割,每一次分割为原来的一半,直到分割后的部分只有一个数或没有为止;最后分割后形成的每一部分均可视为一个排好的序列,可以把这些小序列排序 怎么把两个排序好的序列,合并为一个排序好的序列?把两个序列的最小数进行比较,每一次取出最小数,直到两个序列中不存在数 ~~~ merge_sort(A,p,r) if p<r q=Floor(p+r)/2 向下取整 merge_sort(A,p,q) merge_sort(A,q+1,r) merge(A,p,q,r) merge(A,p,q,r) n1=q-p+1 n2=r-p new arrays L[n1+1]andR[n2+1] for i=1 to n1 L[i]=A[p+i-1] for j=1 to n2 R[j]=A[q+j] L[n1+1]=∞ R[n2+1]=∞ i=1 j=1 for k=p to r if L[i]<=R[j] A[k]=L[i] i=i+1 else A[k]=R[j] j=j+1 ~~~ 归并排序想要算出它的时间较困难,但是不是无法计算时间复杂度为O(n*log2(n)) 通过上面四种算法的比较,发现1 2 3 的时间复杂度相同,利用函数的性质,4的时间明显优于其他三种 排序的算法还有很多,比如堆排序,快速排序,以后再一一分析