quicksort.cpp

来自「在c++开发工具下实现的算法中的一个简单的快速排序算法。」· C++ 代码 · 共 71 行

#include<iostream>
#include<string>
using namespace std; 
#define MAXSIZE 20

typedef struct
{
  int key;
}Rtype;

typedef struct
{
  Rtype r[MAXSIZE+1];
  int length;
}Sqlist;


int Parttition(Sqlist &L,int low,int high)
{
  L.r[0]=L.r[low];
  int pivotkey=L.r[low].key;
  while(low<high)
{
  while(low<high && L.r[high].key>=pivotkey)
  --high;
  L.r[low]=L.r[high];
  while(low<high && L.r[high].key<=pivotkey)
  ++low;
  L.r[high]=L.r[low];
}
  L.r[low]=L.r[0];
  return low;
}

void Qsort(Sqlist &L,int low,int high)
{
  if(low<high)
  {
   int pivotloc=Parttition(L,low,high);
   Qsort(L,low,pivotloc);
   Qsort(L,pivotloc+1,high);
  }
}

void QuickSort(Sqlist &L)
{
  Qsort(L,1,L.length);
}


int main()
{
  Sqlist L;
  cout<<"请输入数列的数字的个数"<<endl;
  int k;
  cin>>k;
  cout<<"请输入一个无序的序列"<<endl;
  for(int i=1;i<=k;i++)
  {
  cin>>L.r[i].key;
  }
  L.length=k;
  QuickSort(L);
  cout<<"排列好的顺序（从小到大的顺序）是"<<endl;
  for(int i=1;i<=k;i++)
  cout<<L.r[i].key<<" ";
  cout<<endl;
  system("pause");
  return 0; 
}