" id="b1img" alt="米课”N+1“思维建站-非官方免费技术支持,Wordpress/Zencart/Opencart建站、SEO" title="米课”N+1“思维建站-非官方免费技术支持,Wordpress/Zencart/Opencart建站、SEO">
  • " alt="米课”N+1“思维建站-非官方免费技术支持,Wordpress/Zencart/Opencart建站、SEO" title="米课”N+1“思维建站-非官方免费技术支持,Wordpress/Zencart/Opencart建站、SEO" />
  • " alt="Windows/Linux服务器运维技术支持 环境搭建、应用发布、服务器管理、虚拟化、云计算" title="Windows/Linux服务器运维技术支持 环境搭建、应用发布、服务器管理、虚拟化、云计算" />
  • " alt="高校/小型企业网络运维与建设免费技术支持,网络规划、网络优化、故障排除、网络管理" title="高校/小型企业网络运维与建设免费技术支持,网络规划、网络优化、故障排除、网络管理" />

快速排序算法

程序设计2009-12-01 itlogger阅读(781) 评论(1)

基本思想  快速排序(Quicksort)是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

快排

  算法过程

  设要排序的数组是A[0]……A[N-1],首先任意选取一个数据(通常选用第一个数据)作为关键数据,然后将所有比它小的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一趟快速排序。一趟快速排序的算法是:

  1)设置两个变量I、J,排序开始的时候:I=1,J=N-1;

  2)以第一个数组元素作为关键数据,赋值给X,即 X=A[0];

  3)从J开始向前搜索,即由后开始向前搜索(J=J-1),找到第一个小于X的值,让该值与X交换;

  4)从I开始向后搜索,即由前开始向后搜索(I=I+1),找到第一个大于X的值,让该值与X交换;

  5)重复第3、4步,直到 I=J;

  例如:待排序的数组A的值分别是:(初始关键数据:X=49)

  A[0] 、 A[1]、 A[2]、 A[3]、 A[4]、 A[5]、 A[6]:

  49 38 65 97 76 13 27

  进行第一次交换后: 27 38 65 97 76 13 49

  ( 按照算法的第三步从后面开始找)

  进行第二次交换后: 27 38 49 97 76 13 65

  ( 按照算法的第四步从前面开始找>X的值,65>49,两者交换,此时:I=3 )

  进行第三次交换后: 27 38 13 97 76 49 65

  ( 按照算法的第五步将又一次执行算法的第三步从后开始找

  进行第四次交换后: 27 38 13 49 76 97 65

  ( 按照算法的第四步从前面开始找大于X的值,97>49,两者交换,此时:J=4 )

  此时再执行第三步的时候就发现I=J,从而结束一趟快速排序,那么经过一趟快速排序之后的结果是:27 38 13 49 76 97 65,即所以大于49的数全部在49的后面,所以小于49的数全部在49的前面。

  快速排序就是递归调用此过程——在以49为中点分割这个数据序列,分别对前面一部分和后面一部分进行类似的快速排序,从而完成全部数据序列的快速排序,最后把此数据序列变成一个有序的序列,根据这种思想对于上述数组A的快速排序的全过程如图6所示:

  初始状态 {49 38 65 97 76 13 27}

  进行一次快速排序之后划分为 {27 38 13} 49 {76 97 65}

  分别对前后两部分进行快速排序 {27 38 13} 经第三步和第四步交换后变成 {13 27 38} 完成排序。

  {76 97 65} 经第三步和第四步交换后变成 {65 76 97} 完成排序。

利用快排排序一组数

变种算法  快速排序(Quicksort)有三个值得一提的变种算法,这里进行一些简要介绍:

  平衡快排(Balanced Quicksort): 每次尽可能地选择一个能够代表中值的元素作为关键数据,然后遵循普通快排的原则进行比较、替换和递归。

  外部快排(External Quicksort): 与普通快排不同的是,关键数据是一段buffer,首先将之前和之后的M/2个元素读入buffer并对该buffer中的这些元素进行排序,然后从被排序数组的开头(或者结尾)读入下一个元素,假如这个元素小于buffer中最小的元素,把它写到最开头的空位上;假如这个元素大于buffer中最大的元素,则写到最后的空位上;否则把buffer中最大或者最小的元素写入数组,并把这个元素放在buffer里。保持最大值低于这些关键数据,最小值高于这些关键数据,从而避免对已经有序的中间的数据进行重排。完成后,数组的中间空位必然空出,把这个buffer写入数组中间空位。然后递归地对外部更小的部分,循环地对其他部分进行排序。

  三路基数快排(Three-way Radix Quicksort,也称作Multikey Quicksort、Multi-key Quicksort): 结合了基数排序(radix sort,如一般的字符串比较排序就是基数排序)和快排的特点,是字符串排序中比较高效的算法。该算法被排序数组的元素具有一个特点,即multikey,如一个字符串,每个字母可以看作是一个key。算法每次在被排序数组中任意选择一个元素作为关键数据,首先仅考虑这个元素的第一个key(字母),然后把其他元素通过key的比较分成小于、等于、大于关键数据的三个部分。然后递归地基于这一个key位置对“小于”和“大于”部分进行排序,基于下一个key对“等于”部分进行排序。

[编辑本段]

 

Pascal中的快速排序源代码  常用代码1:

  procedure sort(l,r: longint);

  var i,j,x,y: longint;

  begin

  i:=l; j:=r; x:=a[(l+r) div 2];

  repeat

  while a[i]<x do inc(i);

  while x<a[j] do dec(j);

  if i<=j then

  begin

  y:=a[i]; a[i]:=a[j]; a[j]:=y;

  inc(i); dec(j);

  end;

  until i>j;

  if l<j then sort(l,j);

  if i<r then sort(i,r);

  end;

  begin

  sort(1,max);

  end;

  常用代码2:

  procedure qsort(l,r:longint);

  var

  t,x,y,p:longint;

  begin

  if l>=r then

  exit;

  x:=l;

  y:=r;

  t:=trunc(random(r-l))+l;

  p:=a[t];

  a[t]:=a[x];

  a[x]:=p;

  while x<y do

  begin

  while (x<y)and(a[y]>=p) do

  dec(y);

  if (x<y)and(a[y]<p) then

  begin

  a[x]:=a[y];

  inc(x);

  end;

  while (x<y)and(a[x]<=p) do

  inc(x);

  if (x<y)and(a[x]>p) then

  begin

  a[y]:=a[x];

  dec(y);

  end;

  end;

  a[x]:=p;

  qsort(l,x-1);

  qsort(x+1,r);

  end;

  begin

  randomize;

  qsort(1,max);

  end;

  两种常用代码,效果是一样的。

[编辑本段]

 

c++中的快速排序源代码  #include<iostream>

  using namespace std;

  void QuickSort(int *pData,int left,int right)

  {

  int i(left),j(right),middle(0),iTemp(0);

  //middle=pData[(left+right)/2];求中间值

  middle=pData[(rand()%(right-left+1))+left]; //生成大于等于left小于等于right的随机数

  do{

  while((pData[i]<middle)&&(i<right))//从左扫描大于中值的数

  i++;

  while((pData[j]>middle) && (j>left))//从右扫描小于中值的数

  j–;

  //找到了一对值,交换

  if(i<=j){

  iTemp=pData[j];

  pData[j]=pData[i];

  pData[i]=iTemp;

  i++;

  j–;

  }

  }while(i<=j);//如果两边扫描的下标交错,就停止(完成一次)

  //当左边部分有值(left<j),递归左半边

  if(left<j){

  QuickSort(pData,left,j);

  }

  //当右边部分有值(right>i),递归右半边

  if(right>i){

  QuickSort(pData,i,right);

  }

  }

  int main()

  {

  int data[]={10,9,8,7,6,5,4};

  const int count(6);

  QuickSort(data,0,count);

  for(int i(0);i!=7;++i){

  cout<<data[i]<<” “<<flush;

  }

  cout<<endl;

  return 0;

  }

[编辑本段]

 

VB中的快速排序源代码  ‘快速排序算法,对字符串数组进行排序
  Private Sub quicksort(ByRef arrValue() As String, ByVal intLx As Integer, ByVal intRx As Integer)
  ’arrValue()是待排的数组,intLx,intRx为左右边界
  Dim strValue As String
  Dim I As Integer
  Dim j As Integer
  Dim intLoop As Integer
  I = intLx
  j = intRx
  Do
  While arrValue(I) <= arrValue(j) And I < j: I = I + 1: Wend
  If I < j Then
  strValue = arrValue(I)
  arrValue(I) = arrValue(j)
  arrValue(j) = strValue

  End If
  While arrValue(I) <= arrValue(j) And I < j: j = j – 1: Wend
  If I < j Then
  strValue = arrValue(I)
  arrValue(I) = arrValue(j)
  arrValue(j) = strValue
  

  End If
  Loop Until I = j
  I = I – 1: j = j + 1
  

  If I > intLx Then
  Call quicksort(arrValue, intLx, I)
  End If
  If j < intRx Then
  Call quicksort(arrValue, j, intRx)
  End If
  End Sub

  Private Sub Form_Load()
  Dim arr(8) As String
  arr(0) = “r”
  arr(1) = “e”
  arr(2) = “a”
  arr(3) = “n”
  arr(4) = “b”
  arr(5) = “u”
  arr(6) = “c”
  arr(7) = “o”
  arr(8) = “f”
  Call quicksort(arr, 0, UBound(arr))
  End Sub

[编辑本段]

 

Java中的快速排序源代码  public class QuickSort {

  /**

  * 快速排序

  */

  public static void main(String[] args) {

  Random random=new Random();

  int[] pData=new int[10];

  for(int i=0;i<pData.length;i++){ //随机生成10个排序数

  Integer a =random.nextInt(100);

  pData[i]= a;

  System.out.print(pData[i]+” “);

  }

  System.out.println();

  int left=0;

  int right=pData.length-1;

  Sort(pData,left,right);

  for(int i=0;i<pData.length;i++){

  System.out.print(pData[i]+” “);

  }

  System.out.println();

  }

  public static int[] Sort(int[] pData, int left, int right){

  int middle,strTemp;

  int i = left;

  int j = right;

  middle = pData[(left+right)/2];

  do{

  while((pData[i]<middle) && (i<right))

  i++;

  while((pData[j]>middle) && (j>left))

  j–;

  if(i<=j){

  strTemp = pData[i];

  pData[i] = pData[j];

  pData[j] = strTemp;

  i++;

  j–;

  }

  for(int k=0;k<pData.length;k++){

  System.out.print(pData[k]+” “);

  }

  System.out.println();

  }while(i<j);//如果两边扫描的下标交错,完成一次排序

  if(left<j)

  Sort(pData,left,j); //递归调用

  if(right>i)

  Sort(pData,i,right); //递归调用

  return pData;

  }

  }

[编辑本段]

 

C#中的快速排序源代码  public static void sortQuick(int[] sortArray, int left, int right)
  {
  int l = left;

   int r = right;

   int indexData = sortArray[l];

   int index = l;

   while (l < r)
  {
  if (index == l)
  {
  while (r > l)
  {
  if (sortArray[r] >= indexData)
  {
  r–;
  }
  else
  {
  sortArray[l] = sortArray[r];
  sortArray[r] = indexData;

   index = r;

   break;
  }
  if (sortArray[r] == indexData)
  {
  index = r;

   if (r > l)
  {
  r–;
  }
  }
  }
  }
  else if (index == r)
  {
  while (l < r)
  {
  if (sortArray[l] <= indexData)
  {
  l++;
  }
  else
  {
  sortArray[r] = sortArray[l];
  sortArray[l] = indexData;

   index = l;

   break;
  }
  if (sortArray[l] == indexData)
  {
  index = l;

   if (l < r)
  {
  l++;
  }
  }
  }
  }
  }

   if (index > left)
  {
  sortQuick(sortArray, left, index – 1);
  }

   if (right > index)
  {
  sortQuick(sortArray, index + 1, right);
  }
  }

来源:百度百科

转载请注明 :IT樵客
文章地址:http://www.itlogger.com/program/974.html
标签:,
相关文章

One thought on “快速排序算法

  1. 非常不错的知识总结,我都是自己看数据结构学这些知识的,又快忘光了。

发表评论

电子邮件地址不会被公开。 必填项已用*标注