从事net工作两年当初学到的数据结构算法一直没有在实际工作中用到近日闲来无事突发奇想要温习一下简单的数据结构算法今日用了一个下午的时间完成了排序中的快速排序以此作为入驻博客园的首篇随笔!思想向后是否将其放到首页?最后还是厚着脸皮大着胆子决定放但始终战战兢兢心中不免忐忑虽然内容很简单但确实我是在用心写希望它能够被人看到好了闲话少叙在下已做好挨骂准备!如果管理员觉得此文不妥就请随意处置吧呵呵
快速排序 是采用递归的方式对待排序的数列进行若干次的操作每次操作使得被操作的数列部分以某个元素为分界值分成两部分一部分小于该分界值另一部分大于该分界值该分界值一般被称为枢轴
以数列 为例详细描述执行一趟快速排序的算法:
选择待排序数列的枢轴一般以数列的首元素作为枢轴此数列中我们选择首元素作为枢轴nPivot =
设定两个指针 i 和 j 分别指向数列的首元素和尾元素 i 指向首元素 j 指向尾元素示意图如下:
向前移动尾指针 j 使其指向从数列尾部算起首个小于枢轴(即)的元素并将该元素置换到头指针 i 指向的位置_nArray[i] =_nArray[j]示意图如下:
首次执行该操作时 i 指针指向处的值实际上就是枢轴的值此处的操作可以理解为 i 指针指向处的值已在之前被置换到枢轴中此时 i 指向处已经是一个空位在此时用找到的小于枢轴的元素填在此处
向后移动头指针 i 使其指向从数列头部算起首个大于枢轴(即)的元素并将该元素置换到尾指针 j 指向的位置_nArray[j] =_nArray[i]示意图如下:
此处同样可以理解为 j 指针指向处的值已在上一步操作中置换了出去 j 处已是一个空位
如此重复执行步骤和步骤直至 i==j 时结束该循环
退出了该循环后 i 与 j 必定指向同一位置在该位置的前部元素其值均小于枢轴而在该位置的后部元素其值均大于枢轴显而易见此时 i 和 j 同时指向的位置就应该是枢轴的新家_nArray[i]=nPivot如下图:
至此一趟排序结束待排序数列的首元素将该数列分成了比其小和比其大的两部分如下图:
接着我们对这一大一小两部分子数列执行相同的排序操作
如此递归直至对整个数列完成排序操作
以下是c#实现代码:
using System;
public class Sort
{
public class Quick_Sort
{
private static int QuickSort_Once(int[] _pnArray int _pnLow int _pnHigh)
{
int nPivot = _pnArray[_pnLow]; //将首元素作为枢轴
int i = _pnLow j = _pnHigh;
while (i < j)
{
//从右到左寻找首个小于nPivot的元素
while (_pnArray[j] >= nPivot && i<j) j;
//执行到此j已指向从右端起首个小于nPivot的元素
//执行替换
_pnArray[i] = _pnArray[j];
//从左到右寻找首个大于nPivot的元素
while (_pnArray[i] <= nPivot && i<j) i++;
//执行到此i已指向从左端起首个大于nPivot的元素
//执行替换
_pnArray[j] = _pnArray[i];
}
//推出while循环执行至此必定是i=j的情况
//i(或j)指向的即是枢轴的位置定位该趟排序的枢轴并将该位置返回
_pnArray[i] = nPivot;
return i;
}
private static void QuickSort(int[] _pnArray int _pnLow int _pnHigh)
{
if (_pnLow >= _pnHigh) return;
int _nPivotIndex = QuickSort_Once(_pnArray _pnLow _pnHigh);
//对枢轴的左端进行排序
QuickSort(_pnArray _pnLow _nPivotIndex);
//对枢轴的右端进行排序
QuickSort(_pnArray _nPivotIndex + _pnHigh);
}
public static void Main()
{
ConsoleWriteLine(请输入待排序数列(以分割):);
string _s = ConsoleReadLine();
string[] _sArray = _sSplit(ToCharArray());
int _nLength = _sArrayLength;
int[] _nArray = new int[_nLength];
for (int i = ; i < _nLength; i++)
{
_nArray[i] = ConvertToInt(_sArray[i]);
}
QuickSort(_nArray _nLength);
ConsoleWriteLine(排序后的数列为:);
foreach (int _n in _nArray)
{
ConsoleWriteLine(_nToString());
}
}
}
}
