快速排序最好情况是什么

快速排序方法的最坏最好情况是什么,简要分析说明理由.~

最好的情况是枢纽元选取得当，每次都能均匀的划分序列。 时间复杂度O(nlogn)最坏情况是枢纽元为最大或者最小数字，那么所有数都划分到一个序列去了 时间复杂度为O(n^2)
快速排序（Quicksort）是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。
它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

因为 排序有很多种 根据不同种类排序的算法 可计算出它们的复杂度
下面有篇文章 希望对你有帮助

借问一下 你也是学软件工程的么

常用的排序算法（包括冒泡排序，选择排序，插入排序，希尔排序，快速排序)
关键词： 排序

排序算法在程序中会用到很多，这里介绍几种常见的排序方法以及比较

冒泡排序：对一个队列里的数据，挨个进行轮询和交换，每次轮询出一个当前最大或者最小的值放在队尾，然后继续下次轮询，轮询长度-1，就跟冒泡一样，所以称为冒泡排序，运算时间复杂度N平方

选择排序：对一个队列里的数据，选出当前最大或者最小的值，然后将他与队首的数据交换，然后从第二个开始，进行相同的操作，运算时间复杂度N平方，但由于他不像冒泡一样需要不停的交换位置，所以会比冒泡快一些

插入排序：对一个队列里的数据，从第二个开始，与此位置之前的数据进行比较，形成局部有序的队列，循环此操作，直到队尾，运算时间复杂度依然为N平方，但他由于保证了局部的有序性，所以比较的次数会更少一些，相对前两种会更快

希尔排序：其实就是用步长控制的插入排序，希尔排序通过加大插入排序中元素之间的间隔，并在这些有间隔的元素中进行插入排序，从而让数据项可以大幅度移动，这样的方式可以使每次移动之后的数据离他们在最终序列中的位置相差不大，保证数据的基本有序，大大提升了排序速度，运算时间复杂度N*logN

快速排序：对一个队列，以他队尾的数据为基准值，先划分成两块数据，一块都大于这个值，一块小于这个值，然后对这两块进行同样的操作，这是最快的排序方法，运算时间复杂度N*logN

下面是代码：

public static void sort(int[] a)
{
long time1,time2;
int c;
time1=System.currentTimeMillis();
// /*冒泡排序*/
// for(int i=a.length-1;i>1;i--)
// {
// for(int j=0;j<i;j++)
// {
//
// if(a[j]<a[j+1])
// {
// c=a[j];
// a[j]=a[j+1];
// a[j+1]=c;
// }
// }
// }
// /*选择排序*/
// int pos=0;
// for(int i=0;i<a.length-2;i++)
// {
// for(int j=i;j<a.length-1;j++)
// {
// if(a[pos]<a[j+1])
// pos=j+1;
// }
// c=a[i];
// a[i]=a[pos];
// a[pos]=c;
// pos=i+1;
// }
// /*插入排序*/
// for(int i=1;i<a.length;i++)
// {
// c=a[i];
// int m=i-1;
// while(m>=0&&a[m]<c)
// {
// a[m+1]=a[m];
// m--;
// }
// a[m+1]=c;
// }
// /*希尔排序*/
// int h=1;
// int m=0;
// while(3*h+1<a.length)
// h=3*h+1;
// while(h>0)
// {
// for(int i=h;i<a.length;i++)
// {
// c=a[i];
// m=i-h;
// while(m>=0&&a[m]<c)
// {
// a[m+h]=a[m];
// m-=h;
// }
// a[m+h]=c;
//
// }
// h=(h-1)/3;
// }
/*快速排序*/
provide(a,0,a.length-1);
time2=System.currentTimeMillis();
System.out.println("time:"+(time2-time1));
}
/*递归调用划分*/
public static void provide(int[] a,int left,int right)
{
try
{
if(right<=left)
return;
else
{
/*设置基准点*/
int prov=a[right];
/*取得划分中断点*/
int par=partitionIt(a,left,right,prov);
/*对划分后的两边再次划分*/
provide(a,left,par-1);
provide(a,par+1,right);

}
}
catch(Exception e)
{
System.out.println("eer:"+left+"."+right);
}
}
/*划分算法*/
public static int partitionIt(int[] a,int left,int right,int prov)
{
/*设置左右端点的指针*/
int leftP=left-1;
int rightP=right;
int c;//用于交换的中间变量
/*当左右指针未相遇时继续操作*/
while(leftP<rightP)
{
/*当左指针的数据小于基准值时跳出*/
while(leftPprov)
;
/*当右指针的数据大于基准值时跳出*/
while(rightP>leftP&&a[--rightP]<prov)
;
/*左右指针都停下时交换数据*/
c=a[leftP];
a[leftP]=a[rightP];
a[rightP]=c;
}
/*划分结束，将基准点与指针的相遇点交换*/
c=a[rightP];
a[rightP]=a[right];
a[right]=c;
return leftP;
}

最好的情况是每次都能均匀的划分序列。
例如 4,1,3,2,6,5,7，每次使用序列的第一个元素做枢轴。比较总次数为10次，交换3次，具体如下：
第一次枢轴为4，序列划分为{2,1,3},4,{6,5,7}
比较6次（4与每个元素比较一次），交换1次（4与2交换）
第二次的两个序列枢轴分别为2和6，此时划分序列得{1},2,{3},4,{5},6,{7}
比较4次（两个序列各比较两次），交换两次（1和2,6和5）
第三次由于各个序列的元素都为1，因此排序完成得1,2,3,4,5，6,7

快排有很多种，要看首先选出来用来作为参照值的那个数是在哪个位置，有的是取最后一个，有的是随机取一个。这个最好情况说不准，但是不管怎么样，比较的次数都不会变，即使情况好，也是不用做交换操作，比较是一定要进行的。

---

沙河口区15259313737： 快速排序最好情况是什么快速排序最好情况下的比较 - ？
耿话诺佳： 最好的情况是每次都能均匀的划分序列.例如 4,1,3,2,6,5,7,每次使用序列的第一个元素做枢轴.比较总次数为10次,交换3次,具体如下:第一次枢轴为4,序列划分为{2,1,3},4,{6,5,7}比较6次(4与每个元素比较一次),交换1次(4与2交换)第二次的两个序列枢轴分别为2和6,此时划分序列得{1},2,{3},4,{5},6,{7}比较4次(两个序列各比较两次),交换两次(1和2,6和5)第三次由于各个序列的元素都为1,因此排序完成得1,2,3,4,5,6,7

沙河口区15259313737： 什么排序的速度(时间复杂度)最快? - ？
耿话诺佳： 从时间复杂度看,所有内部排序方法可以分为两类.1.插入排序 选择排序 起泡排序 其时间复杂度为O(n2);2.堆排序 快速排序 归并排序 其时间复杂度为O(nlog2n).这是就平均情况而言的,如果从最好的情况考虑, 则插入排序和起泡排序的时间复杂度最好,为O(n), 而其他算法的最好情况同平均情况大致相同.如果从最坏的情况考虑,快速排序的时间复杂度为O(n2),插入排序和起泡排序虽然同平均情况相同,但系数大约增加一倍,运行速度降低一半,而选择排序、堆排序和归并排序则影响不大.总之, 在平均情况下,快速排序最快; 在最好情况下,插入排序和起泡排序最快; 在最坏情况下,堆排序和归并排序最快.

沙河口区15259313737： 数据结构(c语言)中快速排序什么时候排序最慢,什么情况下使用快速排序? - ？
耿话诺佳： 当待排序的序列已经有序(不管是升序还是降序),此时快速排序最慢,一般当数据量很大的时候,用快速排序比较好,为了避免原来的序列有序,一般采用改进的快速排序算法,在排序之前随机交换两个元素的位置,就可以达到目的了,有一本书,叫《算法设计、分析与实现:C、C++和java》徐子珊著.可以看看,里面写了很多基本的算法

沙河口区15259313737： C 语言快速排序最好情况时间复杂度为什么是 nlog2n ?(菜鸟在线) - ？
耿话诺佳： 快速排序最好的情况是每次把上一次的数组平均分成两个子数组.设数组总数一共为n,如果把这n个数每次分成2半最后每个数组只包含一个元素,假设要分k次,则2的k次方=n,解得k=log2 n(log以2为底对n取对数).也就是说要分log2 n次,而每次都是处理n个数据.所以总的时间复杂度为O(n*log2 n).

沙河口区15259313737： 3. 对下列关键字序列用快速排序法进行排序时,速度最快的情形是: - ？
耿话诺佳： 所以说第一位的值的位置更靠中间(排序好的)、所以应该是选A、

沙河口区15259313737： 数据结构中堆排序,快速排序,归并排序排序的时间复杂度顺序快慢依次是什么? - ？
耿话诺佳： 堆排序 平均时间:O(n*logn) 最坏:O(n*logn) 快速排序 平均时间:O(n*logn) 最坏:O(n的平方) 归并排序 平均时间:O(n*logn) 最坏:O(n的平方) 排序算法没有最快情况的说法. 从平均性能来说,快速排序最佳,因为所需时间最短,但快速排序在最坏情况下的时间性能不如堆排序和归并排序.n较大时,归并排序所需时间较堆排序省,但归并排序需要的辅助存储量更大.

沙河口区15259313737： c++请指出冒泡,选择,插入,快速,基数排列所有的最好情况最坏情况. - ？
耿话诺佳： 冒泡排序最好是正序情况下,n-1次比较,不需要移动记录,最坏逆序n(n-1)/2次比较,O(n^2)次移动; 选择排序,最好移动次数为0,最大为3(n-1),无论初始排序如何,比较次数均为n(n-1)/2; 直接插入排序最好情况是非递减有序(正序),这是比较次数为n-1,不需要移动,最坏的情况为逆序比较次数为(n+2)(n-1)/2,记录移动次数达到(n+4)(n-1)/2; 快速排序若关键字基本有序或者关键字有序快速排序蜕化为冒泡排序,最坏为O(n^2).平均性能为O(nlogn); 基数排序时间复杂度O(d*n),最坏O(d(n+rd))