八大排序时间复杂度 C语言各常见排序法的时间复杂度急请简单说明？

2021-03-14

1053

C语言各常见排序法的时间复杂度急请简单说明？排序算法的复杂度为O（n^2）。插入排序是O（n^2）快速排序，快速排序不稳定。该算法的时间复杂度在最佳情况下为O（nlog2n），在最坏情况下为O（n^2

C语言各常见排序法的时间复杂度急请简单说明？

排序算法的复杂度为O（n^2）。插入排序是O（n^2）快速排序，快速排序不稳定。该算法的时间复杂度在最佳情况下为O（nlog2n），在最坏情况下为O（n^2）。堆排序算法的时间复杂度为O（nlogn）。合并排序的时间复杂度为O（nlog2n）。

快速排序方法的时间复杂度为nlogn（n×以2为底的对数）

扩展：

快速排序是对冒泡排序的改进。

快速分拣是由C.A.R.Hoare在1962年提出的。它的基本思想是用一步排序法将要排序的数据分成两个独立的部分，其中一部分的数据比另一部分的数据小。然后根据该方法对两部分数据进行快速排序，整个排序过程可以递归进行，从而使整个数据成为一个有序的序列。

各种排序方法的时间复杂度如下：