c++快速排序算法代码

Question

最好是带空格和解释的，或者是可以借鉴的网址也行

Answer 1

1．将i 和j分别指向待排序区域的最左侧记录和最右侧记录的位置；
2．重复下述过程，直到i=j
2.1右侧扫描，直到记录j的关键码小于基准记录的关键码；
2.2 如果i<j，则将r[j]与r[i]交换，并将i++；
2.3左侧扫描，直到记录i的关键码大于基准记录的关键码；
2.4 如果i<j，则将r[i]与r[j]交换，并将j--；
3．退出循环，说明i和j指向了基准记录所在位置，返回该位置；
void QuickSort(int r[ ], int first, int end)
{
if (first<end) { //递归结束
pivot=Partition(r, first, end); //一次划分
QuickSort(r, first, pivot-1); //递归地对左侧子序列进行快速排序
QuickSort(r, pivot+1, end); //递归地对右侧子序列进行快速排序
}
}

int Partition(int r[ ], int first, int end)
{
i=first; j=end; //初始化
while (i<j)
{
while (i<j && r[i]<= r[j]) j--； //右侧扫描
if (i<j) {
r[i]←→r[j]; //将较小记录交换到前面
i++;
}
while (i<j && r[i]<= r[j]) i++； //左侧扫描
if (i<j) {
r[j]←→r[i]; //将较大记录交换到后面
j--;
}
}
retutn i; //i为轴值记录的最终位置
}

Answer 2

//常见的排序算法
//创建日期：2011年4月22

#include <iostream>

using namespace std;

#define MAX_OF_ARRAY 10 //待排序的数组最大数值

int iTemp = 0;
int iTimes = 0;

//交换数据
void Change(int *a, int *b)
{
iTemp = *a;
*a = *b;
*b = iTemp;
iTimes++;
}

//打印数据
void Print(int *arrays)
{
for(int i = 0; i < MAX_OF_ARRAY; i++)
{
cout << *arrays << " ";
arrays++;
}
cout << endl;
cout << "总共交换次数：" << iTimes << endl;
}

/******************************************/
//插入法排序InsertSort(int *arrays)
/******************************************/
void InsertSort(int *arrays)
{
int itemp;
for(int i = 0; i < MAX_OF_ARRAY; i++)
{
itemp = i;
for(int j = i - 1; arrays[itemp] > arrays[j] && j >= 0; itemp-- && j--)
Change(&arrays[itemp], &arrays[j]);
}
}

/******************************************/
//选择排序SelectSort(int *arrays)
/******************************************/
void SelectSort(int *arrays)
{
for(int i = 0; i < MAX_OF_ARRAY; i++)
{
int IMAX = i;
for(int j = i + 1; j < MAX_OF_ARRAY; j++)
{
if(arrays[j] > arrays[IMAX])
IMAX = j;
}
if(IMAX != i)
{
Change(&arrays[IMAX], &arrays[i]);
}
}
}

/******************************************/
//冒泡排序法BubbleSort(int *arrays)
/******************************************/
void BubbleSort(int *arrays)
{
int BUBBLE = 0;
while(BUBBLE == 0)
{
BUBBLE = 1;
for(int i = 0; i < MAX_OF_ARRAY - 1; i++)
{
if(arrays[i] < arrays[i + 1])
{
Change(&arrays[i], &arrays[i + 1]);
BUBBLE = 0;
}
}
}
}
/******************************************/
//快速排序法QuickSort(int *arrays)
/******************************************/
void QuickSort(int *arrays, int arraylen)
{
if(arraylen > 1)
{
int num = 0, i = 0, j = arraylen - 1, itemp = 0;
while(i != j)
{
i = 0, j = arraylen - 1, itemp = 0;
//from back to front to search the number which is greater than the key number,then change;
for(j; j > num; j--)
{
if(arrays[num] < arrays[j])
{
Change(&arrays[num], &arrays[j]);
num = j;
break;
}
}
//from back to front to search the number which is less than the key number, then change;
for(i; i < num; i++)
{
if(arrays[num] > arrays[i])
{
Change(&arrays[num], &arrays[i]);
num = i;
break;
}
}
}
QuickSort(arrays, num);
QuickSort(arrays + num + 1, arraylen - num - 1);
}
}
/******************************************/
//堆排序法HeapSort(int *arrays)
/******************************************/
void HeapKeepMax(int *arrays, int iNode, int Length)
{
int ChildNode = 0;
//结点下移，直至大于总长度
for(int i = iNode; 2 * iNode + 2 <= Length; iNode = ChildNode)
{
ChildNode = iNode * 2 + 1;
//保持ChildNode指向子结点中的较大者
if((ChildNode + 1 < Length) && arrays[ChildNode] < arrays[ChildNode + 1])
ChildNode++;
//如果结点比子结点小，交换
if(arrays[iNode] < arrays[ChildNode])
Change(&arrays[iNode], &arrays[ChildNode]);
else
break;
}
}

void HeapAdjust(int *arrays, int Length)
{
for(int i = (Length - 2) / 2; i >= 0; i--)
HeapKeepMax(arrays, i, Length);
Change(&arrays[0], &arrays[Length - 1]);
}

void HeapSort(int *arrays, int Length)
{
for(int i = Length; i > 1; i--)
HeapAdjust(arrays, i);
}
/******************************************/
//归并排序法MergeSort(int *arrays)
/******************************************/

void main()
{
int arrays[MAX_OF_ARRAY] = {3, 25, 35, 1, 2, 64, 33, 9, 23, 7};
// InsertSort(arrays);
// SelectSort(arrays);
// BubbleSort(arrays);
// QuickSort(arrays, MAX_OF_ARRAY);
HeapSort(arrays, MAX_OF_ARRAY);
Print(arrays);
}

Answer 3

void sort(int *a,int x,int y) 　　
{
　　int xx=x,yy=y;
　　int k=a[x];;//以第一个数为参照做比较
　　if(x>=y) return ;
　　while(xx!=yy)
　　{
　　while(xx<yy&& a[yy]>=k)
yy--;//不小于分界值的留在右边，遇到小于的停止
　　a[xx]=a[yy];
　　while(xx<yy&& a[xx]<=k)
xx++;//小于分界值的留在左边，遇到不小于的停止
　　a[yy]=a[xx];
　　}
　　a[xx]=k;
　　sort(a,x,xx-1);//递归
　　sort(a,xx+1,y);
}

Answer 4

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
using namespace std;
int n,a[100000];
void Init()
{
scanf("%d",&n);
for(int i=0;i!=n;++i) scanf("%d",&a[i]);
}
void Qsort(int l,int r)
{
int i,j,mid,t;
i=l;
j=r;
mid=a[(i+j)>>1];//选择中间元素作为基准
while(i<=j)
{
while(a[i]<mid) ++i;//找到一个在mid左边且不小于mid的元素
while(a[j]>mid) --j;//找到一个在mid右边且不大于mid的元素
if(i<=j)
{
swap(a[i],a[j]);//交换
++i;
--j;
}
}
if(i<r) Qsort(i,r);//递归
if(l<j) Qsort(l,j);//递归
}
void Print()
{
for(int i=0;i!=n;++i) printf("%d ",a[i]);
}
int main()
{
Init();//读入
Qsort(0,n-1);//快速排序
Print();//输出
return 0;
}

Answer 5

void QuickSort(int *a,int left,int right)
{
if ( left < right )
{
int i = left,t;
int j = right + 1;
int pivot = a[left];
do
{
do
{
i++;
} while ( a[i] < pivot );
do
{
j--;
} while ( a[j] > pivot );
if ( i < j )
{
t=a[i];a[i]=a[j];a[j]=t;
}
} while ( i < j );
if (left != j)
{
t=a[left];a[left]=a[j];a[j]=t;
}

QuickSort(a,left,j-1);
QuickSort(a,j+1,right);
}
}