排序问题

来自计算思维百科
跳转至: 导航搜索

排序(Sorting)是把给定数据集合中的元素按照一定的标准来安排先后次序的过程。由于次序是人们在日常生活中频繁遇到的问题,因此排序问题在计算学科中占有一个重要的地位。计算机科学家对排序算法的研究经久不衰,目前已经提出了几十种排序算法,如插入排序、冒泡排序、选择排序、快速排序、归并排序、基数排序和希尔排序等。每种排序算法对空间的要求及其时间效率也不尽相同。这里插入排序和冒泡排序被称为简单排序,它们对空间的要求不高,但是时间效率却不稳定;而后面三种排序相对于简单排序对空间的要求稍高一点,但时间效率却能稳定在很高的水平。在实际应用中,通常需要结合具体的问题选择合适的排序算法。

例子

选择排序算法的思路非常简单。对给定的一个数据表,算法从第一个元素开始扫描整个列表,找到最小(或最大)的元素,并将其与第一个位置的元素交换。然后算法从第二个位置的元素开始扫描剩下的列表,找到次小(或次大)的元素,并将其与第二个位置的元素交换。如此循环,直到所有的元素都被排好序为止,如图1所示。

7.4.1.png
                                                                                                                                                    图1 选择排序算法过程

选择排序算法是由一个双层循环控制,算法的时间复杂度由输入规模(也就是元素个数n)决定,即C (n) = n(n-1)/2,因此,选择排序算法的时间复杂度是O (n2)。