C++源码:
//program 3-3
#include<conio.h>
#include <iostream>
using namespace std;
int Partition(int r[],int low,int high)//划分函数
{
int i=low,j=high,pivot=r[low];//基准元素
while(i<j)
{
while(i<j&&r[j]>pivot) j--;//向左扫描
if(i<j)
{
swap(r[i++],r[j]);//r[i]和r[j]交换后i+1右移一位
}
while(i<j&&r[i]<=pivot) i++;//向右扫描
if(i<j)
{
swap(r[i],r[j--]);//r[i]和r[j]交换 后j-1左移一位
}
}
return i;//返回最终划分完成后基准元素所在的位置
}
int Partition2(int r[],int low,int high)//划分函数
{
int i=low,j=high,pivot=r[low];//基准元素
while(i<j)
{
while(i<j&&r[j]>pivot) j--;//向左扫描
while(i<j&&r[i]<=pivot) i++;//向右扫描
if(i<j)
{
swap(r[i++],r[j--]);//r[i]和r[j]交换
}
}
if(r[i]>pivot)
{
swap(r[i-1],r[low]);//r[i-1]和r[low]交换
return i-1;//返回最终划分完成后基准元素所在的位置
}
swap(r[i],r[low]);//r[i]和r[low]交换
return i;//返回最终划分完成后基准元素所在的位置
}
void QuickSort(int R[],int low,int high)//实现快排算法
{
int mid;
if(low<high)
{
mid=Partition2(R,low,high); //基准位置
QuickSort(R,low,mid-1);//左区间递归快排
QuickSort(R,mid+1,high);//右区间递归快排
}
}
int main()
{
int a[100];
int i,N;
cout<<"请先输入要排序的数据的个数:";
cin>>N;
cout<<"请输入要排序的数据:";
for(i=0;i<N;i++)
cin>>a[i];
cout<<endl;
QuickSort(a,0,N-1);
cout<<"排序后的序列为:"<<endl;
for(i=0;i<N;i++)
cout<<a[i]<<" " ;
cout<<endl;
getch();
return 0;
}
运行结果:
python源码:
n=int(input("请输入要排序的序列的元素个数:n="))
print("请输入这一串序列(每一个元素用换行符隔开):")
a=[]
for i in range(n):
a.append(int(input()))
low=0
high=n-1
#将该序列分解为两个子序列
def partition(a,low,high):#返回基准元素位置
i=low
j=high
pivot = a[low]
while i<j:
while i<j and a[j]>pivot:#向左扫描,一直找到<=pivot的数,将两者交换,i向后移
j-=1
if i<j:
a[i],a[j]=a[j],a[i]
i=i+1
while i<j and a[i]<=pivot:#从左向右扫描,一直找到>pivot的数,将两者交换,j向前移
i+=1
if i<j:
a[i],a[j]=a[j],a[i]
j -= 1
return i
def quicksort(a,low,high):
if low<high:
mid=partition(a,low,high)
quicksort(a,low,mid-1)
quicksort(a,mid+1,high)
partition(a,low, high)
quicksort(a,low,high)
print("排序后的序列为:",a)
运行结果: