各种排序最坏情况下比较次数_快速排序最坏需要多少趟排序

全栈程序员-站长 • 2022年8月23日下午11:36 • 未分类 • 阅读 7

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元售后保障童叟无欺

都不知道怎么回答，各种排序说的也太多了，这里讲几种简单的吧，希望对你有帮助！
比如n个顺序存储元素进行排序，a[0]做“哨兵”（即a[0]不存数据，而是用作辅存空间使用）的情况
1 直接插入排序：比较次数 最少n-1次；最多(n-1)(n+2)/2
                            移动次数 最少0； 最多(n-1)(n+4)/2
                           使用一个辅助存储空间，是稳定的排序；

2 折半插入排序：比较次数 最少与最多同，都是n*log2n（其中2为底，下边表示同），
                移动次数 最少0，最多时间复杂度为O(n2);(n的平方，以下也如此表示)；
                使用一个辅助存储空间，是稳定的排序；

3 冒泡排序： 比较最少为：n-1次，最多时间复杂度表示为o(n2);
                      移动次数最少为0，最多时间复杂度表示为O(n2);
                        使用一个辅存空间，是稳定的排序；

4 简单选择排序： 比较次数没有多少之分，均是n(n-1)/2;
                            移动次数最少为0，最多为3(n-1);
                             使用一个辅存空间，是稳定的排序；

5 快速排序：比较和移动次数最少时间复杂度表示为O(n*log2n);
                    比较和移动次数最多的时间复杂度表示为O(n2);
                    使用的辅助存储空间最少为log2n，最多为n的平方；是不稳定的排序；

6 堆排序： 比较和移动次数没有好坏之分，都是O(n*log2n);
                  使用一个辅存空间，是不稳定的排序；

7 2-路归并排序：比较和移动次数没有好坏之分，都是O(n*log2n);
                    需要n个辅助存储空间，是稳定的排序；

另外还有很多的排序方法如 希尔排序，基数排序，2-路插入排序 等等很多的排序方法，这里就不一一列举了，希望列举的对你有帮助！！

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/172502.html原文链接：https://javaforall.net