c#与算法－－快速排序

核心提示： 从事.net工作两年,当初学到的数据结构算法一直没有在实际工作中用到.近日闲来无事,突发奇想要温习一下简单的数据结构算法.今日,用了一个下午的时间完成了排序中的"快速排序",以此作为入驻博客园的首篇随笔!思想向后,是否将其放到首页?最后,还是厚着脸皮,大着胆子决定放.但始终战战兢兢,心中不免忐忑.

从事.net工作两年,当初学到的数据结构算法一直没有在实际工作中用到.近日闲来无事,突发奇想要温习一下简单的数据结构算法.今日,用了一个下午的时间完成了排序中的"快速排序",以此作为入驻博客园的首篇随笔!思想向后,是否将其放到首页?最后,还是厚着脸皮,大着胆子决定放.但始终战战兢兢,心中不免忐忑.虽然内容很简单,但确实我是在用心写,希望它能够被人看到.好了,闲话少叙,在下已做好挨骂准备!如果管理员觉得此文不妥,就请随意处置吧,呵呵.

快速排序 是采用递归的方式对待排序的数列进行若干次的操作,每次操作使得被操作的数列部分以某个元素为分界值分成两部分,一部分小于该分界值,另一部分大于该分界值.该分界值一般被称为"枢轴".

以数列 14,11,25,37,9,28 为例,详细描述执行一趟快速排序的算法:

1,选择待排序数列的枢轴,一般以数列的首元素作为枢轴.此数列中,我们选择首元素14作为枢轴,nPivot = 14.

2,设定两个指针 i 和 j ,分别指向数列的首元素和尾元素. i 指向首元素14, j 指向尾元素28.示意图如下:

　　　　　　

3,向前移动尾指针 j ,使其指向从数列尾部算起首个小于枢轴(即14)的元素,并将该元素置换到头指针 i 指向的位置._nArray[i] =_nArray[j].示意图如下:

首次执行该操作时 i 指针指向处的值实际上就是枢轴的值,此处的操作可以理解为 i 指针指向处的值已在之前被置换到枢轴中,此时, i 指向处已经是一个空位,在此时用找到的小于枢轴的元素填在此处.