程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> .NET網頁編程 >> C# >> 關於C# >> C#快速排序類

C#快速排序類

編輯:關於C#

快速排序的基本思想是基於分治策略的。對於輸入的子序列ap..ar,如果規模足夠小則直接進行排序,否則分三步處理:

分解(Divide):將輸入的序列ap..ar劃分成兩個非空子序列ap..aq和aq+1..ar,使ap..aq中任一元素的值不大於aq+1..ar中任一元素的值。

遞歸求解(Conquer):通過遞歸對p..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;
}

}
}

來源:http://www.cnblogs.com/tanghuawei/archive/2006/10/19/533711.html

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved