信息学奥赛入门算法合集——排序算法

信息学奥赛入门算法合集，适合初学者参考学习：

排序算法：冒泡排序、选择排序、插入排序、希尔排序、归并排序、桶排序等。

冒泡排序（Bubble Sort），是一种较简单的排序算法。
它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素已经排序完成。

冒泡排序

选择排序（Selection Sort），每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在待排序的数列的最前，直到全部待排序的数据元素排完。

选择排序

插入排序（Insertion Sort）,当读入一个元素时，在已经排序好的序列中，搜寻它正确的位置，再放入读入的元素。但不该忽略一个重要的问题：在插入这个元素前，应当先将将它后面的所有元素后移一位，以保证插入位置的原元素不被覆盖。

插入排序

希尔排序（Shell Sort）也称为缩小增量排序，是插入排序的一种改进算法。其基本思想是将待排序序列按照一定的间隔进行分组，对每个分组内的元素进行插入排序，然后逐步缩小分组间隔，直到间隔为 1，最终完成排序。因为在排序过程中会多次进行插入排序，所以希尔排序也被看作是插入排序的一种变体。

具体实现过程如下：

1、选择一个增量序列dlta,通常为n/2,n/4,n/8等；

2、对每个增量dlta[i],按照增量取出数组中的子序列，对每个子序列进行插入排序；

3、逐步缩小增量 dlta，重复第二步，直到增量为 1，最终完成排序。

希尔排序

快速排序（Quick Sort）是一种分治的排序算法，其基本思想是通过一趟排序将待排数据分隔成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法分别对这两部分数据进行快速排序，整个排序过程可以递归进行，以此达到整个数据序列变成有序序列的目的。具体实现过程如下：

1、选择一个基准元素（通常选择第一个或者最后一个元素），将待排序数据分成小于等于基准元素的部分和大于基准元素的部分；

2、对小于等于基准元素的部分和大于基准元素的部分分别递归调用快速排序函数，直到只剩下一个元素或者没有元素。

快速排序

归并排序（Merge Sort）则是一种分治算法，其基本思想是将原始序列分成若干个子序列，每个子序列分别排序，然后再将排好序的子序列合并成一个有序序列。具体实现过程如下：

1、将待排序序列分成两个子序列；

2、对每个子序列递归调用归并排序函数，直到只剩下一个元素或者没有元素；

3、将排好序的子序列合并成一个有序序列。

归并排序

桶排序（Bucket Sort）是一种线性排序算法，它的基本思想是将待排序数据分到若干个有序的桶中，然后对每个桶中的数据进行排序，最终合并所有桶中的数据即可得到有序的结果。

桶排序