多数据源数据等概率分档统计插入排序算法

Multi-resource Subsection Insertion Sorting Algorithm with Equal Probability Data Segment

针对待排数据来源的多样性,提出了多数据源数据等概率分档统计插入排序算法．该算法将现代统计学的新结论、新方法应用于传统的排序算法．新的排序算法达到了时间复杂度的下界O(n),且具有更广的应用范围．实验表明,当数据量较大时(n＞1000),此算法优于其他同类算法．

Sorting is one of the most important techniques in computer science. We first proposed a one-resource subsection insertion sorting algorithm with equal probability data segment and discussed its validity. To sort the data from multiple resources, this paper proposes a multi-resource subsection insertion sorting algorithm with equal probability data segmentation. This algorithm combines traditional sorting algorithms with some new conclusions of modern statistics to sort data with general multi-distribution. The complexity of the new sorting is limited O（ n ）, which reaches the lower bound. Experiments have shown that this algorithm is better than others of similar kind when n 〉 1000.