c语言，快速排序，在最坏条件下需要比较的次数为多少
n*3
你可以用冒泡排序法自己试一试
目的：按要求从大到小或从小到大排序。
基本思路：对尚未排序的各元素从头到尾依次依次比较相邻的两个元素是否逆序（与欲排顺序相反），若逆序就交换这两元素，经过第一轮比较排序后便可把最大（或最小）的元素排好，然后再用同样的方法把剩下的元素逐个进行比较，就得到了你所要的顺序。可以看出如果有 n 个元素，那么一共要进行 n-1 轮比较，第 i 轮要进行 j=n-i 次比较。（如：有5个元素，则要进行5-1轮比较。第3轮则要进行5-3次比较）
下面以C语言为例子给大家一个明确的表示：
#include
void main()
{
int a[10];
int i,j,t;
printf("输入10个整数：
");
for( i = 0; i < 10; i ++ )
scanf("%d",&a[ i ]); //依次输入10个整数
for( j = 0; j < 9; j ++ ) //进行9轮排序 即n－1次
{
for( i = 0; i < 9-j; i ++) //每轮进行n－1－j 次比较，最多n－1－j 次交换
if( a[ i ] > a[ i + 1 ] )
{
t = a[ i ] ;
a[ i ] = a[ i + 1 ]; //小的沉底，大的上浮
a[ i + 1 ] = t;
}
}
printf("排序结果:");
for( i = 0; i < 10; i ++ ) //依次输出排序结果
printf("%d",a[ i ]);
printf("
");
}
我想的话（1）和（2）一个从小到大，一个从大到小，排序的次数最少吧
（3）和（4）的话（4）要的次数更多吧
C(n) = (n-1) + (n-2) + ... + 1 = n(n-1)/2
最坏的情况下，快速排序的时间复杂度为O(n^2)
假设有n个数，n(n+1)/2次
...则选用堆排序,若初始记录无序则最好选用快速排序。这是为什么?_百 ...
1，堆排序的性能：时间复杂度总是Nlogn(N) 的。2，快速排序不属于原地排序，由于程序中使用了递归，需要递归调用栈的支持，而栈的长度取决于递归调用的深度。在平均情况下，需要O(logn) 的栈空间；最坏情况下，栈空间可达O(n) 。1 ）划分元素的选取是影响时间性能的关键。2 ）输入数据次序越乱，...
C语言快速排序代码
prvotloc=partions(l,low,high); \/\/将第一次排序的结果作为枢轴 qsort(l,low,prvotloc-1); \/\/递归调用排序 由low 到prvotloc-1 qsort(l,prvotloc+1,high); \/\/递归调用排序 由 prvotloc+1到 high } } void quicksort(int l[],int n){ qsort(l,1,n); \/\/第一个作为枢轴 ，从...
C语言中说的按字典顺序是什么意思?
就是说，将多个字符串的同一位置的字符按照26个字母的顺序进行比对。a最小，z最大。a < b；aa < ab； 因为第二位置上，前面字符串是a，后面字符串是b，所以是小于关系，以此类推。C语言排序算法：快速排序：1、假设我们给一个int数组进行排序，数组中数字初始序列为int a[9]={3,6,5,9,7...
Pascal语言快速排序
Qsort(l, r: Longint);var i, j, mid, t: Longint;begin i := l;j := r;Mid := a[(i + j) div 2];repeat while a[i] < Mid do inc(i);while a[j] > Mid do dec(j);if i <= j then begin t := i;i := j;j := t;inc(i);dec(j);end;until i > j;...
c语言生成50个随机数,对随机数进行快速排序。
楼下的几个回答我怎么看也不是快速排序，所以我做了一个用快速排序法排序的程序 include<stdio.h> include<stdlib.h> include define LEN 50 \/\/快速排序(升)void quicksup(int *arr,int low,int high){ int temp,l,r;if(low<high){ l=low;r=high;temp=arr[low];while(low<high){ whil...
用C语言快速排序法编程按从大到小输出下面十个数(24,2,8,32,87,45...
QuickSort(low,Low-1,array); \/*对基准点左边的数再执行快速排序*\/ QuickSort(Low+1,high,array); \/*对基准点右边的数再执行快速排序*\/ } } void main() { int array[]={24,2,8,32,87,45,16,2,12,40};int i=9;QuickSort(0,9,array);for(;i>=0;i--)printf("%d "...
C语言找出一个数组中出现次数最多的那个元素
include<stdio.h> int main(){ int n,i,j,k,t,m,a[25];while(scanf("%d",&n)!=EOF){ for(i=0;i<n;i++)scanf("%d",&a[i]);for(i=0;i<n-1;i++){ for(j=i+1;j<n;j++){ if(a[i]>a[j]){ t=a[i];a[i]=a[j];a[j]=t;\/\/先进行排序，按从小到大的...
二级C语言排序技术2
（1）交换类排序法 交换类排序法是指借助数据元素之间的互相交换进行排序的一种方法。冒泡排序法与快速排序法都属于交换类排序方法。冒泡排序法是一种最简单的交换类排序方法，它是通过相邻数据元素的交换逐步将线性表变成有序。假设线性表的长度为n，则在最坏情况下，冒泡排序需要经过n\/2遍的从前往后的...
c语言编程找 第二个大的数 怎么弄
呵呵。这是一个很经典的算法。你百度一下找第K小或者第K大的数。去看看。我分析下思路：2轮冒泡，可以找出第二大数。2轮循环。也可以找出第二大的。你要到公司面试，要讲效率的话。可以看看我写的下面这个代码 这是用快速排序，夹逼原则来锁定要找的第K大的元素 void swape(int *p1,int *p2...
为什么Lisp语言如此先进
所以,为什么上个世纪50年代的编程语言,到现在还没有过时?简单说,因为这种语言本质上不是一种技术,而是数学。数学是不会过时的。你不 应该把Lisp语言与50年代的硬件联系在一起,而是应该把它与快速排序(Quicksort)算法进行类比。这种算法是1960年提出的,至今仍然是最 快的通用排序方法。 三、 Fortran语言也是上个世...
阿婷丙氧： 快速排序最坏的情况是初始序列已经有序,第1趟排序经过n-1次比较后,将第1个元素仍然定在原来的位置上,并得到一个长度为n-1的子序列;第2趟排序经过n-2次比较后,将第2个元素确定在它原来的位置上,又得到一个长度为n-2的子序列;以此类推,最终总的比较次数:C(n) = (n-1) + (n-2) + ... + 1 = n(n-1)/2 最坏的情况下,快速排序的时间复杂度为O(n^2)
泾阳县18550612145： C语言堆排序最坏的情况下比较次数最多要多少次? - ？
阿婷丙氧： O(n1og2n) 在最坏情况下,冒泡排序所需要的比较次数为n(n-1)//2;简单插入排序所需要的比较次数为n(n-1)/2;希尔排序所需要盼的比较次数为0(n1.5);堆排序所需要的比较次数为0(nlog2n).
泾阳县18550612145： C语言:编写一个程序用冒泡排序实现升序排列 - ？
阿婷丙氧： 1、首先打开一个空白的C语言文件,首先先定义一组待排序的数列以及各个变量,接着就是用来处理排序的逻辑: 2、冒泡排序的逻辑是一组数从第一个数值开始,如果相邻两个数的排列顺序与期望不同,则将两个数的位置进行交换,重复这样的过程直到最后一个数不需要交换则排序完成,如果有N个数需要排序,则需要进行(N-1)趟的比较: 3、最后编译运行程序,观察最终排序的结果,可以看到数字被从小到大的排列好了,以上就是C语言冒泡排序实现的过程:
泾阳县18550612145： C语言中冒泡排序在最坏情况下的比较次数是什么 - ？
阿婷丙氧： 比较次数是固定的,交换次数会有最好情况和最坏情况
泾阳县18550612145： C语言冒泡排序. - ？
阿婷丙氧： #include<stdio.h> void main() { int a[10]; int i,j,t; printf(＂input 10 numbers:\n＂); for(i=0;i<10;i++) scanf(＂%d＂,&a[i]); for(j=0;j<9;j++) /*进行9次循环 实现9趟比较*/ for(i=0;i<9-j;i++) /*在每一趟中进行9-j次比较*/ if(a[i]>a[i+1]) /*相邻两个数比较,想...
泾阳县18550612145： 最坏情况下,冒泡排序的时间复杂度为…c语言 - ？
阿婷丙氧： 假设数组长度为n,对于冒泡排序的最坏情况是逆向有序,复杂度为 n - 1 + n - 2 + n - 3 + ... + 2 + 1 = (n-1)(n-1+1)/2= n(n-1)/2
泾阳县18550612145： 请教C语言中这四种排序的比较次数!!!! - ？
阿婷丙氧： 1. 快速排序.使用分而治之的递归算法,最坏情况是当选取的中枢元把元素都分到一起,即O(n^2) 2. 冒泡排序.每一趟都要把较大的元素向右“冒泡”,最坏情况是O(n^2) 3. 直接插入排序.每一趟都要把当前轮的元素插到适应的位置,最坏情况就是与排序的方向相反,即O(n^2) 4. 堆排序.先建堆,再每次从堆中pop最顶的元素,最坏情况是O(nlog n)
泾阳县18550612145： C语言排序, - ？
阿婷丙氧： 第一个数和下面的数比 = n-1 次 第二个数和下面的比 =n-2 次 第三个数和下面的比 =n-3 次 ........ 最后第二个和最后一个比 =1 次 次数都加起来就行了 1+2 +3+........+(n-1)
