Question

我想写一个用C++编写快速排序的程序，是从大到小排的，请知道尽快写给我啊，谢谢哦。。。。。。

Answer 1

/*
快排么。网上一搜就一堆了。算法只是一种思想或说成一种方法而已，并非就C语言。其它语言也一样
快排也有点像二路归并：从一个无序的序列中随机取出一个值q做为支点,然后把大于q的放到一边，小于q的放到q的另一边,然后再以q为分界点，分别对q的两边
进行排序（快排时直接再对q两边重新取支点，整理，再取支点，...直到支点两旁都有序。也就是支点两旁只有一个数时）
*/
#include <stdio.h>
#include <stdlib.h>
int Qsort(int p[],int beg,int end)
{
if(beg+1>=end)return 0;//退出递归
int low,hight,q;
low=beg;
hight=end;
q=p[low];//q为支点，其实q可以为随机数。但相应以下程序就要改了
while(1){
while(low<hight && p[hight]>q)hight--;
if(low>=hight)break;
p[low++]=p[hight];
while(low<hight && p[low]<q)low++;
p[hight++]=p[low];
}
p[low]=q;
Qsort(p,beg,low-1);
Qsort(p,low+1,end);
}
int main()
{
int i,a[]={1,32,6,4,54,654,6,6,2,76,76,7,66,5,544,334,34,78};
Qsort(a,0,sizeof(a)/4-1);
for(i=0;i<sizeof(a)/4;i++)printf(" %d ",a[i]);
system("pause");
return 0;
}
快速排序的优势和支点元素的选择有关系。
所选支点元素每次递归后都在最前面或最后面。这样情况就会最差了。
我们知道一般的排序。（如冒泡。。）在一个数组p[m,n]中排序。都是确定最大或最小，而确定最大值（最小值）要经过n-m-1次比较。
而整个过程就差不多是(n-m-1)!次比较。
快排中：一次比较可以确定支点元素的位置。若p[m,q,n](q为支点元素）。当然确定第一个元素也是要比较（n-m-1)次。但第二个，第三个（第二层）就是(q-m-1)和(n-q-1)次比较。
明显q的值若为m或n，快排就没有什么优势了

看了LS的回答，还是我水平最高嘛……喔厚厚厚……希望采纳！鞠躬……

Answer 2

冒泡法，比较简单。原理是一次将最小的数放到未排序队列的末尾。

int s[10]; //存放原始数据
int tmp;

for (int i = 0; i < 10; i++)
for (int j = 0; j < 10 - i - 1; j++)
{
if (s[j] < s[j + 1])
{
tmp = s[j];
s[j] = s[j + 1];
s[j + 1] = tmp;
}
}

Answer 3

这是我刚刚自己写的，顺便共享一下，希望对你有帮助哦
#include <iostream>
using namespace std;
int Exchange(int a,int b)
{
return a>b?a:b;
}
int Partition(int A[],int p,int r)
{
int x,i,j,temp;
x=A[r];
i=p-1;
for(j=p;j<r;j++)
if(A[j]>=x)//确定从大到小排列
{
i++;
temp=A[i];//交换A[i]与A[j]
A[i]=A[j];
A[j]=temp;
}
temp=A[i+1];//交换A[i+1]与A[r](主元)
A[i+1]=A[r];
A[r]=temp;
return i+1;
}
void Quiksort(int A[],int p,int r)
{
int q;
if(p<r)
{
q=Partition(A,p,r);
Quiksort(A,p,q-1);
Quiksort(A,q+1,r);
}
}
int main()
{
int A[10]={2,8,7,1,3,5,6,4};
int i;
Quiksort(A,0,7);
for(i=0;i<8;i++)
cout<<A[i]<<" ";
cout<<endl;
getchar();
return 0;
}

Answer 4

题目：输入三个整数x,y,z，请把这三个数由小到大输出。
1.程序分析：我们想办法把最小的数放到x上，先将x与y进行比较，如果x>y则将x与y的值进行交换， 然后再用x与z进行比较，如果x>z则将x与z的值进行交换，这样能使x最小。
2.程序源代码：
main()
{
int x,y,z,t;
scanf("%d%d%d",&x,&y,&z);
if (x>y)
{t=x;x=y;y=t;} /*交换x,y的值*/
if(x>z)
{t=z;z=x;x=t;}/*交换x,z的值*/
if(y>z)
{t=y;y=z;z=t;}/*交换z,y的值*/
printf("small to big: %d %d %d\n",x,y,z);
}

Answer 5

#include <conio.h>
#include <iostream.h>
const int N=5;
int a[]={3,1,2,5,4};
void QuickSort(int a[],int num);
//---------------------------------------------------------------------------

#pragma argsused
int _tmain(int argc, _TCHAR* argv[])
{
QuickSort(a,N);
for(int i=0;i<N;i++)
{
cout<<a[i];
}
getch();
return 0;
}
void QuickSort(int a[],int num)
{
if(num<=0)
return;
int small[N];
int big[N];
int k=0,j=0;
for(int i=1;i<num;i++)
{
if(a[i]<a[0])
{
small[k]=a[i];
k++;
}
else
{
big[j]=a[i];
j++;
}
}
QuickSort(small,k);
QuickSort(big,j);
a[k]=a[0];
for(int i=0;i<k;i++)
{
a[i]=small[i];
}
for(int i=0;i<j;i++)
{
a[k+i+1]=big[i];
}
}
快速排序，我自己写的，算法复杂度较低