快速排序的基本思想是基于分治策略的。对于输入的子序列ap..ar,如果规模足够小则直接进行排序,否则分三步处理:
分解(Divide):将输入的序列ap..ar划分成两个非空子序列ap..aq和aq+1..ar,使ap..aq中任一元素的值不大于aq+1..ar中任一元素的值。 合并(Merge):由于对分解出的两个子序列的排序是就地进行的,所以在ap..aq和aq+1..ar都排好序后不需要执行任何计算ap..ar就已排好序。 这个解决流程是符合分治法的基本步骤的。因此,快速排序法是分治法的经典应用实例之一。 using System; namespace VcQuickSort { /// <summary> /// ClassQuickSort 快速排序。 /// 范维肖 /// </summary> public class QuickSort { public QuickSort() { } private void Swap(ref int i,ref int j) //swap two integer { int t; t=i; i=j; j=t; } public void Sort(int [] list,int low,int high) { if(high<=low) { //only one element in array list //so it do not need sort return; } else if (high==low+1) { //means two elements in array list //so we just compare them if(list[low]>list[high]) { //exchange them Swap(ref list[low],ref list[high]); return; } } //more than 3 elements in the arrary list //begin QuickSort myQuickSort(list,low,high); } public void myQuickSort(int [] list,int low,int high) { if(low<high) { int pivot=Partition(list,low,high); myQuickSort(list,low,pivot-1); myQuickSort(list,pivot+1,high); } } private int Partition(int [] list,int low,int high) { //get the pivot of the arrary list int pivot; pivot=list[low]; while(low<high) { while(low<high && list[high]>=pivot) { high--; } if(low!=high) { Swap(ref list[low],ref list[high]); low++; } while(low<high && list[low]<=pivot) { low++; } if(low!=high) { Swap(ref list[low],ref list[high]); high--; } } return low; } } } |
|