# 排序算法 很多计算机科学家认为排序是算法研究中的最基础问题。这里将介绍几种排序算法并给出伪代码，及其运行时间分析。 ## 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的系数，和低阶的项对于结果影响不大，就可以舍弃ａ和低阶项 因此，改算法的运行时间只有ｎ^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的时间明显优于其他三种 排序的算法还有很多，比如堆排序，快速排序，以后再一一分析