Open chzhiyi opened 5 years ago
参考网址
有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法，插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。 一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：
从第一个元素开始，该元素可以认为已经被排序 取出下一个元素，在已经排序的元素序列中从后向前扫描 如果该元素（已排序）大于新元素，将该元素移到下一位置 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置 将新元素插入到下一位置中 重复步骤2~5
它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素已经排序完成。 这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。 原理如下：
比较相邻的元素。如果第一个比第二个大，就交换他们两个。 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。 针对所有的元素重复以上的步骤，除了最后一个。 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。
计数排序算法没有用到元素间的比较，它利用元素的实际值来确定它们在输出数组中的位置
将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
第一步 以LSD为例，假设原来有一串数值如下所示： 73, 22, 93, 43, 55, 14, 28, 65, 39, 81 首先根据个位数的数值，在走访数值时将它们分配至编号0到9的桶子中： 0 1 81 2 22 3 73 93 43 4 14 5 55 65 6 7 8 28 9 39 第二步 接下来将这些桶子中的数值重新串接起来，成为以下的数列： 81, 22, 73, 93, 43, 14, 55, 65, 28, 39 接着再进行一次分配，这次是根据十位数来分配： 0 1 14 2 22 28 3 39 4 43 5 55 6 65 7 73 8 81 9 93 第三步 接下来将这些桶子中的数值重新串接起来，成为以下的数列： 14, 22, 28, 39, 43, 55, 65, 73, 81, 93 这时候整个数列已经排序完毕；如果排序的对象有三位数以上，则持续进行以上的动作直至最高位数为止。
以LSD为例，假设原来有一串数值如下所示： 73, 22, 93, 43, 55, 14, 28, 65, 39, 81 首先根据个位数的数值，在走访数值时将它们分配至编号0到9的桶子中： 0 1 81 2 22 3 73 93 43 4 14 5 55 65 6 7 8 28 9 39
接下来将这些桶子中的数值重新串接起来，成为以下的数列： 81, 22, 73, 93, 43, 14, 55, 65, 28, 39 接着再进行一次分配，这次是根据十位数来分配： 0 1 14 2 22 28 3 39 4 43 5 55 6 65 7 73 8 81 9 93
接下来将这些桶子中的数值重新串接起来，成为以下的数列： 14, 22, 28, 39, 43, 55, 65, 73, 81, 93 这时候整个数列已经排序完毕；如果排序的对象有三位数以上，则持续进行以上的动作直至最高位数为止。
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
如设有数列{6，202，100，301，38，8，1} 初始状态：6,202,100,301,38,8,1 第一次归并后：{6,202},{100,301},{8,38},{1}，比较次数：3； 第二次归并后：{6,100,202,301}，{1,8,38}，比较次数：4； 第三次归并后：{1,6,8,38,100,202,301},比较次数：4； 总的比较次数为：3+4+4=11；
由C. A. R. Hoare在1962年提出。基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
参考网址
插入排序
冒泡排序
选择排序
一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。
计数排序
计数排序算法没有用到元素间的比较，它利用元素的实际值来确定它们在输出数组中的位置
基数排序
将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
归并排序
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
快速排序
由C. A. R. Hoare在1962年提出。基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。