排序算法是怎样的？

Answer 1

一、背景介绍

在计算机科学与数学中，排序算法（Sorting algorithm）是一种能将一串资料依照特定排序方式进行排列的一种算法。

最常用到的排序方式是数字顺序以及字典顺序。

有效的排序算法在一些算法（例如搜寻算法与合并算法）中是重要的， 如此这些算法才能得到正确解答。

排序算法也用在处理文字资料以及产生人类可读的输出结果。

基本上，排序算法的输出必须遵守下列两个原则：

1、输出结果为递增序列（递增是针对所需的排序顺序而言）；

2、输出结果是原输入的一种排列、或是重组；

虽然排序算法是一个简单的问题，但是从计算机科学发展以来，在此问题上已经有大量的研究。 更多的新算法仍在不断的被发明。

二、知识剖析

查找和排序算法是算法的入门知识，其经典思想可以用于很多算法当中。因为其实现代码较短，应用较常见。 所以在面试中经常会问到排序算法及其相关的问题。但万变不离其宗，只要熟悉了思想，灵活运用也不是难事。

一般在面试中最常考的是快速排序和冒泡排序，并且经常有面试官要求现场写出这两种排序的代码。对这两种排序的代码一定要信手拈来才行。除此之外，还有插入排序、冒泡排序、堆排序、基数排序、桶排序等。

三、常见的几种算法：

冒泡算法、选择排序、插入排序、希尔排序、归并排序、快速排序

算法的特点：

1、有限性：一个算法必须保证执行有限步之后结束。

2、确切性： 一个算法的每一步骤必须有确切的定义。

3、输入：一个算法有零个或多个输入，以刻画运算对象的初始情况，所谓零个输入是指算法本身给定了初始条件。

4、输出：一个算法有一个或多个输出。没有输出的算法毫无意义。

5、可行性：算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步，即每个计算步都可以在有限时间内完成（也称之为有效性）。