【编程的最低境界】
插入排序容易理解,就是一趟遍历一次尚未排序的元素插入到已经排序的序列中,如此进行一次则可以将一个元素放到已排序序列中,从第二个元素开始循环N-1次(N为元素个数)即可得到一个全部有序的序列。此算法的复杂度是O(N^2),因为一个元素最多需要与其他元素交换的次数是n-1次,而一般是小于这个数的,然后外循环算一个n,则得到其复杂度不超过N^2.在样本数N小的情况下,插入排序是十分迅速的。
void insertSort(int a[],int size){ int j = 0; int i = 0; for(i=1;i0 && a[j]
swap 函数是交换两个参数的值。可以看到从i=1(数组中的第二个元素)开始,我们就从i往前查找,如果有比a[j]大的,则a[j]作为小的,要往前排。这样就可以将a[j]插入到有序序列中,同时插入后依然保持有序数列特性,同时i往后移动一步,继续排序后面的元素。
可见这个排序的思想是非常直观的,写代码的时候只要记住,两个循环,把元素i往前面排,一路交换下去,就能得到有序序列了。我想任何CS的同学都能够在三分钟之内写出这几行代码来吧,这是编程的最低境界,没得说必须熟练。
冒泡排序的思想是,就像一个气泡往上浮起,自然相同体积的水要和气泡进行空间交换,而排序的主要步骤是,一趟循环,将相邻两个元素进行比较,大的往下沉,小的往上浮(即交换),这样每一趟的最后,最大的一个肯定是在最底下了。如此经过N趟,则会形成一个从小到大的序列。
【归并排序】
归并排序的思想源于将两组东西合并起来,大家玩扑克牌的时候经常需要将两叠牌进行排序,于是左手抽一张牌,右手抽一张牌,那个小,先出哪张,如果左手的出了,就再用左手抽一张牌,再看看左右手的牌,出小的,如果是右手的出了,右手抽牌,比较。。。按照这种思想,到最后一定会是按从小到大的顺序出牌的。下面给出代码:
//-----------------------mergesort------------------------------------------------void mergeSort(int a[],int left,int right){ if(left&a[mid]&&pr<=&a[right]) //copy right part into b[] { b[offset++] = *pr++; } else if(pr>&a[right]&&pl<=&a[mid]) //copy left part into b[] { b[offset++] = *pl++; } else { if(*pl<*pr) b[offset++] = *pl++; else b[offset++] = *pr++; } } copy(a,b,left,right,size); //copy b[] back to a[] from left to right }void copy(int a[],int b[],int left,int right,int size){ int *pa = &a[left]; //destination int *pb = &b[0]; //source int tmpoffset=0; while(tmpoffset
归并排序有一个缺点就是需要另外一个O(N)的空间消耗,最终得到的结果需要复制回去原来的数组中去。归并排序的算法复杂度是O(NlgN)的,画一棵树会比较容易理解其涵义。因为我们对数组进行分半,然后最后肯定是有lgN,然后递归下去,最后进行了lgN次的分半,然后归并的过程是用了N的时间,故而最终时间复杂度是O(NlgN). 归并非常有趣的一点就是用到了递归,先对数组进行分半,然后递归对左半边进行归并排序,对右半边进行排序,最后合并起来。这样的方法启发我们,要善于在处理数据中抽象出特征方法,这就是分治的思想,而且使用了递归的思想,用同一种办法化大为小,然后利用程序调用的无形的“栈”一层层地返回合并的结果。话说系统子程序调用的无形的“栈”还有反转字符串的作用。不信可以看下面的代码:
#include "stdio.h"void Print(void);int main(){ printf("please input string and end with # \n"); Print(); getchar();}void Print(void){ char a; scanf("%c",&a); if(a != '#') Print(); printf("%c",a);}
进入主函数,调用print,输入数据,再调用自身,输入数据,直到最后一层调用,输出最新输入数据,返回上层,输出倒数第二数据,这样一层层地返回,就将字符串反转过来了。就像用了一个栈一样,不断地压入数据,再一一弹出,得到反转顺序的序列。当然,这是别的话题了。下面接着看快速排序。
【快速排序】
快速排序,那是相当地快。那是因为它在平均的情况下复杂度是O(NlgN),虽然最坏情况下是O(N^2)的,但毕竟那是最坏情况(序列已经有序),一般来说很少出现这样的情况,为了避免partition的不均匀,故而采用随机化的qsort是很不错的主意。这样作为partition的依据一般是随机选择的,故而依照概率不会发生每次都只将序列分为一个为1,另外一个是N-1个元素(这是很糟糕的)。还是来看看代码吧:
void qSort(int a[],int p,int r){ if(px) //j从尾部递减,如果大于则往前移 ; if(i>=j) //这里停止partition,跳出到括号外 break; swap(a[i],a[j]); } a[p] = a[j]; a[j] =x; //基准元素必定在中间 return j;}
由代码可以知道,核心部分是partition,在数组的头尾设两个指针,前指针往后移动,后指针往前移动。在排序过程中,默认i所指位置之前的元素都小于或等于x(x为基准元素),而j所指之后的元素皆大于等于x。这样两个while(a[i++]<=x && i<r)和while(a[j--]>x)就不难理解了。重要的在后面,要是有元素不满足这个断言,那么就要将这两个元素互换了。一是大于x的,一个是小于x的,刚好进行互换,如果i和j交叉了,说明排序完成了,需要将基准元素插到它改到的位置(两组数据的中间)。这样就大功告成了! 当然也可以换一种写法,不从尾部开始,而是两个指针都从数组首部开始,一直往后移动。
void partition(int a[],int p,int r){ int x = a[r]; //尾部元素做为分组依据 int i = p-1; for(int j=p;j
swap(a[i],a[j]); //将a[j]进行挪动到小于或等于x的部分
} } return i+1; //返回数组的中间位置}原理上是一样的,只不过简化了代码,j查找的是小于等于x的最靠左的元素,找到之后则将现在所指的小于等于x的最靠右的元素的下一个位置进行交换,等于扩充了小于等于x的部分,到最后将会把基准元素与i+1位置的元素交换,返回的是数组的中间i+1位置。
【堆排序】
bibo写到这里已经筋疲力尽了,想必读者看到这里也是倾注了很大的耐心。对于那些代码,最好的办法就是自己敲一遍,然后跟着单步运行一次,慢慢地也就了解其中的思想,也熟练了一些技巧了。算法是一种技巧,搭载的是数学的思想,再经过实践者的手,变成可以用的工具。
言归正传,堆——分为最大堆,最小堆,指的是堆的树结构中,位于根节点的元素是最大的还是最小的。最大堆,其根节点就是这棵树的最大值。而堆排序就是要利用这个特性,来实现每次都找出一个“最大”或“最小”元素来,放到树外面。其实由于堆是一颗完全二叉树,故而它能够存储在一个数组里面(做回忆状:数据结构课程里关于完全二叉树的存储,的确是可以存放到一个数组里面的)。而那些出了堆的元素,恰好能放回去数组中的某个位置,于是等全部元素都选过一遍之后,该数组就会呈现出一个有序状态。
假设有这样一个样本存储在只有三个节点的堆里面:
3 ,1 ,2
其中0号位置的3,就是堆的根,好了,第一次查找,3出堆,通过整形2成为了根,1为2的孩子。这样腾出一个空间给3,这样3就在数组的最后了。
同理,2出堆到位置1,结果1成为了堆根。现在的数组状态是: 1 2 3
此时数组状态是:1,2,3 (没骗人,真的是有序的)
安装这个方法同样也能定义出一个最小堆,得到有序序列 : 3,2,1。
这就是堆排序的思想,下面是代码:
//-----------------------------------------------------------------------void heapSort(int a[],int size){ int heapSize = size; //heapSize was init to be the length of the array buildMaxHeap(a,heapSize); //build a heap on a[] for(int i=heapSize;i>0;i--) { swap(a[0],a[i]); //swap the root of tree with the final element ,get out of the heap heapSize --; maxHeapify(a,0,heapSize); //重新整队,保持最大堆的性质 }}void buildMaxHeap(int a[],int size){ int heapSize = size; //initial the heapSize as the length of array a for(int k=(size-1)/2;k>=0;k--) //从不是叶子节点开始,一直往根上刨 { maxHeapify(a,k,heapSize); //进行建堆,就是让所有节点都符合堆的定义 ——根节点都要比子节点大 }}void maxHeapify(int a[],int i,int heapSize){ int left =( i<<1)+1; //left child int right = (i<<1) +2; //right chlid position int largest =i; //mark the position of the largest element in array if(left <=heapSize && a[left] > a[i]) largest = left; else largest = i; if(right <= heapSize && a[right] > a[largest]) largest = right; if(largest != i) //说明有节点比根节点大,根节点需要下移 { swap(a[i],a[largest]);//swap 之后都要整队 maxHeapify(a,largest,heapSize); //递归调用,防止子节点亦违反规则 }}
一开始的堆,不是说是就是的,而是要通过建堆操作来实现的。现在我们建一个最大堆,根据最小堆的定义,我们只需要保证根是最小的就行了,当然因为二叉树的递归结构,能够保证最上面的根是整个堆中最大的(哥们要的东西有了保障)。
buildMaxHeap就是建立最大堆,这里需要说明的是存储在数组中的二叉完全树有两个和巧妙的特性,之所以巧妙,是因为可以轻易计算出哪个是根的左孩子,那个是根的右孩子,也能计算出最后一个非叶子节点,然后方便从非叶子节点做maxHeapify。
如果你的数组是从0号开始存堆的,那么假设i为某个节点,那么i*2 + 1就左孩子所在位置,i*2 +2 乃右孩子所在位置,举个例子,0号的左孩子是1,右孩子是2。1号的左孩子是3,右孩子是4。可以画个图更加直观一点。
好了,接下来就研究一下,怎样进行整堆吧,以为这是关键。看代码可知,查找该树中的最大值,然后将最大的作为堆的根。如此递归下去,这样每个带孩子的节点都将符合最大堆的定义。代码还是要好好研究一番的,如果思考十分钟,应该都能写出来吧。
【排序之后】
排序算法有很多,能徒手写出来,在算法上就已经进了一阶了。学习了排序之后,将会有更加复杂和困难的问题等待着我们,比如动态规划和贪心算法、回溯等等。我居然有耐心写完这一整篇了,那么也更加有信心去写接下来的高级算法。排序之后,我们需要的是重温一下学习的分治和递归思想,同时也动手练习(经验教训告诉我们,程序员是练出来的),接下来就是畅游算法的奇妙世界了。