冒泡排序在最坏的情况下的比较次数为什么是n(n-1)/2?

第一个for循环里的-1可以去了,但是会多循环计算一次,虽然不会影响结果
因为冒泡排序是两两交换,所以,在执行xue[j]=xue[j+1]时,如果第二个for循环的j没有-1,会超出索引报错
-i,是因为每次交换都把没有交换的字符里的最大字符的换到后面去了,所以,每次需要交换位置的字符越来越少,
不-i不影响结果,因为换到后面的都是比较过后排好序的,再计算排序结果还是不变,但是却多了没必要的循环和计算,所以-i性能会更好

意料之中.单看程序,不实际跑几遍是很难完全理解的.
void main prbub(p,n)
int n;double p[];
{int m,k,j,i;
double d;
k=0;m=n-1;
while (k=j;j--) //从m开始往前,直到j
if(p[i-1]>p[i]) //如果顺序不对
{d=p[i];p[i]=p[i+1];p[i+1]=d;k=i;} //两个数字对换位置
}
return;
}
1、排序方法
将被排序的记录数组R[1..n]垂直排列,每个记录R看作是重量为R.key的气泡.根据轻气泡不能在重气泡之下的原则,从下往上扫描数组R：凡扫描到违反本原则的轻气泡,就使其向上"飘浮".如此反复进行,直到最后任何两个气泡都是轻者在上,重者在下为止.
（1）初始
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

什么语言的

选A了

百度一下 我数学也不是很厉害，或者找个数学老师来问问？嘻嘻！不要扁我哦！

最坏是n2 最好是n 。最好情况是本来顺序就是好的，就不用执行交换元素的循环，就只有一层外面的循环所以是O（n）。

第一趟 57 ,78 ,80 ,27 ,32 ,90 ,45 ,100
第二趟 57 ,78 ,27 ,32 ,80 ,45 ,90 ,100
第三趟 57 ,27 ,32 ,78 ,45 ,80 ,90 ,100
第四趟 27 ,32 ,57 ,45 ,78 ,80 ,90 ,100

1.选择排序：不稳定,时间复杂度 O(n^2)
选择排序的基本思想是对待排序的记录序列进行n-1遍的处理,第i遍处理是将L[i..n]中最小者与L[i]交换位置.这样,经过i遍处理之后,前i个记录的位置已经是正确的了.
2.插入排序：稳定,时间复杂度 O(n^2)
插入排序的基本思想是,经过i-1遍处理后,L[1..i-1]己排好序.第i遍处理仅将L[i]插入L[1..i-1]的适当位置,使得L[1..i] 又是排好序的序列.要达到这个目的,我们可以用顺序比较的方法.首先比较L[i]和L[i-1],如果L[i-1]≤ L[i],则L[1..i]已排好序,第i遍处理就结束了；否则交换L[i]与L[i-1]的位置,继续比较L[i-1]和L[i-2],直到找到某一个位置j(1≤j≤i-1),使得L[j] ≤L[j+1]时为止.图1演示了对4个元素进行插入排序的过程,共需要(a),(b),(c)三次插入.
3.冒泡排序：稳定,时间复杂度 O(n^2)
冒泡排序方法是最简单的排序方法.这种方法的基本思想是,将待排序的元素看作是竖着排列的“气泡”,较小的元素比较轻,从而要往上浮.在冒泡排序算法中我们要对这个“气泡”序列处理若干遍.所谓一遍处理,就是自底向上检查一遍这个序列,并时刻注意两个相邻的元素的顺序是否正确.如果发现两个相邻元素的顺序不对,即“轻”的元素在下面,就交换它们的位置.显然,处理一遍之后,“最轻”的元素就浮到了最高位置；处理二遍之后,“次轻”的元素就浮到了次高位置.在作第二遍处理时,由于最高位置上的元素已是“最轻”元素,所以不必检查.一般地,第i遍处理时,不必检查第i高位置以上的元素,因为经过前面i-1遍的处理,它们已正确地排好序.
4.堆排序：不稳定,时间复杂度 O(nlog n)
堆排序是一种树形选择排序,在排序过程中,将A[n]看成是完全二叉树的顺序存储结构,利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素.
5.归并排序：稳定,时间复杂度 O(nlog n)
设有两个有序（升序）序列存储在同一数组中相邻的位置上,不妨设为A[l..m],A[m+1..h],将它们归并为一个有序数列,并存储在A[l..h].
6.快速排序：不稳定,时间复杂度 最理想 O(nlogn) 最差时间O(n^2)
快速排序是对冒泡排序的一种本质改进.它的基本思想是通过一趟扫描后,使得排序序列的长度能大幅度地减少.在冒泡排序中,一次扫描只能确保最大数值的数移到正确位置,而待排序序列的长度可能只减少1.快速排序通过一趟扫描,就能确保某个数（以它为基准点吧）的左边各数都比它小,右边各数都比它大.然后又用同样的方法处理它左右两边的数,直到基准点的左右只有一个元素为止.

几种排序的时间复杂度,可以参考一下

D
冒泡排序算法的运作如下：（从后往前）
比较相邻的元素.如果第一个比第二个大,就交换他们两个.
对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对.在这一点,最后的元素应该会是最大的数.
针对所有的元素重复以上的步骤,除了最后一个.
持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较.

我啰嗦两句，从头讲起。冒泡排序是一种用时间换空间的排序方法，最坏情况是把顺序的排列变成逆序，或者把逆序的数列变成顺序。在这种情况下，每一次比较都需要进行交换运算。举个例子来说，一个数列 5 4 3 2 1 进行冒泡升序排列，第一次大循环从第一个数（5）开始到倒数第二个数（2）结束，比较过程：先比较5和4，4比5小，交换位置变成4 5 3 2 1；比较5和3，3比5小，交换位置变成4 3 5 2 1……最后比较5和1，1比5小，交换位置变成4 3 2 1 5。这时候共进行了4次比较交换运算，最后1个数变成了数列最大数。
第二次大循环从第一个数（4）开始到倒数第三个数（2）结束。进行3次比较交换运算。
……
所以总的比较次数为 4 + 3 + 2 + 1 = 10次
对于n位的数列则有比较次数为 (n-1) + (n-2) + ... + 1 = n * (n - 1) / 2，这就得到了最大的比较次数
而O(N^2)表示的是复杂度的数量级。举个例子来说，如果n = 10000，那么 n(n-1)/2 = (n^2 - n) / 2 = (100000000 - 10000) / 2，相对10^8来说，10000小的可以忽略不计了，所以总计算次数约为0.5 * N^2。用O(N^2)就表示了其数量级（忽略前面系数0.5）。
打了那么多字应该解释的比较清楚了吧，什么地方看不明白再问吧

(46,56,38,40,79,84)

选择排序的算法中,其比较次数与初始数据集顺序无关.
因为它固定是N-1轮外循环,用于选N-1次最小值（升序排序）,每一轮必须要比较（N-i）次,才能在（N+1-i）个数中选 出最小元素.

/*
算法思想简单描述：
堆排序是一种树形选择排序,是对直接选择排序的有效改进.
堆的定义如下：具有n个元素的序列（h1,h2,...,hn),当且仅当
满足（hi>=h2i,hi>=2i+1）或（hi

1.确定块来历不明的元素;
2块来历不明的元素.由于冒泡排序算法的条款,设置一个标志,标志记录行程排序记录交换,以确定当前的排序区域是否有自然的和有序的.冒泡排序这个问题,用最少的时间.
记录时,一直键的初始值增量有序,快速排序,因为每个选定的中间元件是最小的,它被分成左,右两个区域是空的,以及其他比原来的面积的至少一种元素,只有在旅途中的元素比较的数量小于1,所以总的时间消耗是O（N ^ 2）,所以这个问题的快速排序方法最耗费时间的.
[答案]冒泡排序,快速排序.
3.成叠的S1,S2拿出一叠
入队的时候,在
尾出队入堆栈S1,如果栈S2不为空,然后出来.
否则11到的堆栈S1,堆栈,和11进入堆栈S2,然后出来.
否则,错误
判处空间,以确定是否两个堆栈同时空气

选择排序.
选择排序的算法原理是：第一趟从n个待排关键字中找出最小的关键字放到第一个位置,如果要找到最小关键字则必须所有元素都进行比较,所以第一趟要比较n-1次；第二趟从剩下的n-1的元素中再通过n-2次的比较找出最小的元素…………以此类推,不管初始有没有序,它都一共要进行n-1趟排序共n(n-1)/2次比较,时间复杂度始终是O（n平方）
至于其他的,拿插入排序举例：插入排序的基本思想是每次将一个待排的记录按其关键字大小插入到前面已经排好序的子序列中.试想,如果已经排好序的子序列是123,待排记录为45,插入4时,只要和3比较一次就知道排在3后面,对5排序时只要与4比较一次就知道该排在4后面,共比较2次.如果已经排好序的子序列是234,待排记录为15,插入1时,它要从后往前依次比较3次才能找到自己的位置,同样对5排序时只要与4比较一次,共比较4次.由上例可知,插入排序会随着初始数据集的顺序不同而比较次数不同.
BTW,基数排序不是基于关键字比较的排序算法.
纯手打,望采纳,不清楚还可共同探讨.

要想了解算法,请看下面 冒泡排序 1、排序方法 将被排序的记录数组R[1..n]垂直排列,每个记录R看作是重量为R.key的气泡.根据轻气泡不能在重气泡之下的原则,从下往上扫描数组R：凡扫描到违反本原则的轻气泡,就使其向上"飘浮".如此反复进行,直到最后任何两个气泡都是轻者在上,重者在下为止.（1）初始 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

进行冒泡排序,理论上来说,最小的比较次数是 0次,可以是直接排好序的序列.
但是,程序并不会像人一样,一眼看出来,所以它的走一趟,如果在这一趟中没有发生任何交换,它知道这个序列是排好序的,也就是n-1次,不过这个要在代码中判断,如果不加入判断的话,它还是一直比较下去,直到结束.

（1）非递减,（2）0

最坏情况下比较次数最少的为D）堆排序：
A）冒泡排序 需要比较O(n^2)次（n(n - 1)/2次）,即序列逆序的情况
B）简单选择排序,无论是否最坏都需要O(n^2)次（n(n - 1)/2次）
C）直接插入排序,最坏情况需要比较O(n^2)次（n(n - 1)/2次）
D）堆排序,无论是否最坏比较O(nlog2n)次
E）快速排序,最坏情况退化为冒泡排序,需要比较O(n^2)次（n(n - 1)/2次）

int a[]={33,76,26,88,15,92,37,49},i,j.k;
for(i=0;i

LZ在瞎扯
假设有序列（123,3244,45,【123】）
排序后为（45,123,123,3244）
如果第一个123在排序后还在第二个【123】之前,即
45 123 【123】 3244
则算法是稳定的
否则
45 【123】 123 3244
即为不稳定

找排序的区别,一定要动手（用笔,不是电脑）去执行代码,不用问你也可以看出代码怎么排的,而且你自己对这问题的理解也更加深刻,问人的话说不定哪天你又忘了,说不定还把两种给搞反了.我下面手写给你解释一下代码,你动手去画一下.
为了方便思考,数组零位置我没用
选择排序(从小到大,每次将a[i]到a[n]中最小的值找到,并放到a[i]处)
for(i=1;i

最坏情况下：直接选择排序：每次都要执行交换,总移动次数为（n-1)次交换 O(n)
冒泡排序：每比较一次都要进行一次交换 ,移动次数为 3n(n-1)/2 O(n2)
直接插入排序：n2/4 O(n2)
堆排序： O(nlog2n）
所以,应该选D

排序方法 最坏时间复杂度 最好时间复杂度 平均时间复杂度
直接插入 O(n2) O(n) O(n2)
简单选择 O(n2) O(n2) O(n2)
起泡排序 O(n2) O(n) O(n2)
快速排序 O(n2) O(nlog2n) O(nlog2n)
堆排序 O(nlog2n) O(nlog2n) O(nlog2n)
归并排序 O(nlog2n) O(nlog2n) O(nlog2n)
所以选d

堆排序

23,57,71,30,13,28,35,26,34,12,87
23,57,30,13,28,35,26,34,12,71,87
23,30,13,28,35,26,34,12,57,71,87
23,13,28,30,26,34,12,35,57,71,87
13,23,28,26,30,12,34,35,57,71,87
13,23,26,28,12,30,34,35,57,71,87
13,23,26,12,28,30,34,35,57,71,87
13,23,12,26,28,30,34,35,57,71,87
13,12,23,26,28,30,34,35,57,71,87
12,13,23,26,28,30,34,35,57,71,87

change=FLASE;
A[j]>A[j+1]

出这个题的人弱智.
冒泡可以从左到右遍历,也可以从右到左遍历.这个想怎么实现都可以,出题人说选c就是从右到左的遍历结果,a是从左到右的遍历结果.题目又没说采用什么方式,如果这是考试题目的话,这样出题就是弱智.除非这个教材上的习题,他的冒泡流程在正文讲的,这样才可以.