Question

c++排序算法相关问题

1.排序算法在实际中有什么应用？ 2.排序算法复杂度O（n）是由排序过程中的什么操作计算出来的？ 请各位答的详细些，因为要回答别人的问题！ 谢谢！

Answer 1

1.排序算法在实际中的应用当然也就是排序了。在实际应用当中比如数据统计等方面都会用到。而且对一组数据进行排序也方便了后面对数据查找的操作。要知道在一个有序数组中查找和在一个随机无序数组中的查找的时间复杂度和系统消耗是有天壤之别的。
2.算法复杂度其实是一个估计，也就是那个O(n)。首先O这个操作的定义为：如果f(n)是正整数n的一个函数，则Xn
=
O(f(n))表示存在一个正的常数M，使得当n大于等于某一个整数n0时都满足Xn小于等于M乘以f(n)。这个在算法中的实际意义就是：
比如，执行一个排序算法最多需要执行5n+7条命令（语句）：最多表示在执行过程中循环被完整的执行，也就是比如循环条件从1-n，那么这个循环最多就是可以执行n次。如果这个循环里面有5条基本语句（递增循环变量i++也包括在内），那么就是5n条语句。那么根据上面O函数的定义，这个时候Xn
=
5n
+
7。注意到当n大于等于7的时候5n+7小于等于6n，也就是说我们可以把6看成是M，n看成是f(n)，于是我们可以说，这个算法的时间复杂度是O(n)。对于其他的O(n^2),
O(n
log
n)等等都是这个道理。在计算总共执行的命令条数的时候要考虑“最坏”（从循环初始条件到循环最终条件，条件分支也要尽可能的考虑最多的情况）的可能性，然后每一条基本语句（比如一次赋值，一次比较等）都要计入