> 快速排序（c语言实现）1.起因今天在acm刷题的时候，之前的排序算法一直都是冒泡，可能九度OJ的难
快速排序（c语言实现）1.起因今天在acm刷题的时候，之前的排序算法一直都是冒泡，可能九度OJ的难
xmc0871 & &
发布时间： & &
浏览：49 & &
回复：0 & &
悬赏：0.0希赛币
快速排序（c语言实现）1.起因
　　今天在acm刷题的时候，之前的排序算法一直都是冒泡，可能九度OJ的难度题考察的都是快速排序，导致我都是死在time limited上，因此我下决心要学习一下快速排序，心得跟大家进行分享！
2.算法思想
　　快速排序采用了一种分治策略，我感觉它就是归并排序的优化，学术上称之为分治法（Divide-and-ConquerMethod）
(1)分治的基本思想：
　　将原问题分解成若干个规模更小但是结构跟原问题相似的子问题。递归的解决这些子问题，然后将这些子问题的解喝并为原问题的解
(2)快速排序的思想：
　　设当前需要排序的数组为int A[low..high]
　　在A[]中任选一个记录作为基准（pivot），以pivot为基准将数组A划分为两个小的数组A[low..pivot-1]和A[pivot+1..high],并使左边的数组元素均小于等于pivot，右边数组元素均大于等于piovt。此时，pivot处于正确的位置上，它不需要再参加后续的排序
　　递归的调用快速排序，对A[low..pivot-1]和A[pivot+1..high]进行快速排序
　　跟归并排序不同，因为每次调用快速排序，左右两个数组均已有序，因此对于快速排序来说，组合是一个空操作
3.快速排序程序实现
* Description:快速排序主流程
void quicksort(int *A, int p, int r)
if( p & r)
pivot = partition(A, p, r);
quicksort(A, p, pivot - 1);
quicksort(A, pivot+1, r);
注意：为排序整个数组，只需要在main函数中调用一个quicksort(A,begin,end)即可完成对数组的排序
划分实现：
* Description:快速排序寻找基准点
int partition(int *A, int p, int r)
int left = //从左往右扫描
int right =
//从右往左扫描
int stand = A[p]; //基准
//从区间两端向中间扫描，直到left==right为止
while(left & right)
while(left & right && A[right] &= stand)
if(left & right)
A[left ++] = A[right];
while(left & right && A[left] &= stand)
if(left &right)
A[right --] = A[left];
//基准最后的定位位置
　　4.算法分析
快速排序的主要时间消耗在划分操作上，对长度为len的数组进行划分，需要len-1次关键字的比较
（1）最坏的时间复杂度
　　最坏的情况是每次划分的基准都是当前无序区中最大（最小）的记录，划分的结果是基准左边的区间为空（基准为最小记录）或者基准右边的区间为空（基准为最大记录），划分所得的非空子区间中记录的数目仅仅比划分前的无序区元素数少一。
　　因此，快速排序最坏情况下需要做n-1次划分，第i次划分的区间长度为n-i+1,第i次所需比较的次数为n-i,故而最话情况下的时间复杂度为：T（n）= (n-1)(n)/2 = O(n*n)
（2）最好情况下的时间复杂度
　　每次划分选取的基准都是当前无序区间的中值，时间复杂度为：T（n）= 0（n*lgn）
（3）平均情况下的时间复杂度
　　平均性能，快速排序是最好的，所以我也建议在ACM刷题的时候尽量用快速排序来时间对数组的排序功能。
　　之后，我会带来一道用快速排序AC的题目
本问题标题：
本问题地址：
温馨提示：本问题已经关闭，不能解答。
暂无合适的专家
&&&&&&&&&&&&&&&
希赛网 版权所有 & &&请教c语言冒泡法升序排列20个数字遇到的问题？
这是我自己写的 &冒泡法升序排列20个数字遇到的问题& 每次已运行就提示，内存无法write是怎么回事#include &stdio.h& void main() { int i,j,a[20], for (i=1;i&=20;i++) { printf(&请输入第%d个数字:&,i); scanf(&%d&,a[i]); } for(i=1;i&=20;i++) { for(j=1;j&=20;j++) {if(a[j]&=a[j+1]) { tmp=a[j]; a[j]=a[j+1]; a[j+1]= } } } for(i=1;i&=20;i++) printf(&%d&,a[i]);}
08-12-27 &
首先,scanf里面赋值的参数要是地址而不是值,也就是你该写成&a[i] 然后就是数组下标是从0开始到元素个数减1,你定义的是20,下标就是0-19,不存在20这个下标,而你所有用的都是1-20,这是个基本概念 最后就是,冒泡排序比较次数是n-1,也就是说每一次都是那当前的数和下一数比,那么也就是到了倒数第二个和最后一个比就完成了比较,比较过程循环变量不应该出现最后一个下标,你的20个元素,应该最后是18和19比较,而你到20在比较,就溢出了 改后程序如下: #include &stdio.h& void main() { int i,j,a[20], for (i=0;i&20;i++) { printf(&请输入第%d个数字:&,i); scanf(&%d&,&a[i]); } for(i=0;i&20-1;i++) { for(j=0;j&20-1;j++) {if(a[j]&=a[j+1]) { tmp=a[j]; a[j]=a[j+1]; a[j+1]= } } } for(i=0;i&20;i++) printf(&%d&,a[i]);}
请登录后再发表评论!C语言冒泡排序法的简单程序 - 百度文库
C语言冒泡排序法的简单程序
#include &stdio.h&
#include&stdlib.h&
int a[10];
for(i=0;i&10;i++)
scanf (&%d,&,&a[i]);
for(j=0;j&=9;j++)
{ for (i=0;i&10-j;i++)
if (a[i]&a[i+1])
{ temp=a[i]; a[i]=a[i+1]; a[i+1]=} }
for(i=0;i&10;i++)
printf(&%5d,&,a[i] );
printf(&\n&);
system(&pause&);
--------------
冒泡排序的算法分析与改进
交换排序的基本思想是：两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序的记录为止。
应用交换排序基本思想的主要排序方法有：冒泡排序和快速排序。
1、排序方法
将被排序的记录数组R[1..n]垂直排列，每个记录R看作是重量为R.key的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R：凡扫描到违反本原则的轻气泡，就使其向上&飘浮&。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。
R[1..n]为无序区。
（2）第一趟扫描
从无序区底部向上依次比较相邻的两个气泡的重量，若发现轻者在下、重者在上，则交换二者的位置。即依次比较(R[n]，R[n-1])，(R[n-1]，R[n-2])，…，(R[2]，R[1])；对于每对气泡(R[j+1]，R[j])，若R[j+1].key&R[j].key，则交换R[j+1]和R[j]的内容。
第一趟扫描完毕时，&最轻&的气泡就飘浮到该区间的顶部，即关键字最小的记录被放在最高位置R[1]上。
（3）第二趟扫描
扫描R[2..n]。扫描完毕时，&次轻&的气泡飘浮到R[2]的位置上……
贡献者：lztlxh}