Various sorting algorithms and implementations in java

Let’s first take a look at the relationship between the 8 kinds of sorting:

The following picture is a comparison of various sorts:

1, direct insertion sorting

(1) Basic idea: In a set of numbers to be sorted, assuming that the previous (n-1) [n>=2] numbers are already in order, now the nth number needs to be inserted into the previous ordered numbers. , so that these n numbers

are also sorted. Repeat this cycle until everything is in order.

In the insertion algorithm, if there is a smallest number at the end of the array, the insertion algorithm will move from the last

position to the first.

(2) Example

package cglib; public class StringNumber { public static void insertSort(int[] a) { if (a == null || a.length < 2) { return; } int length=a.length; //数组长度 int j; //当前值的位置 int i; //指向j前的位置 int key; //当前要进行插入排序的值 //从数组的第二个位置开始遍历值 for(j=1;j
        

         Copy after login
        
       

{3, -1, 0, -8, 2, 1} 将i=0 进 i=0 i=-1 退出while i=-1 将i=1 进 i=1 i=0 退出while i=0 将i=2 进 i=2 i=1 进 i=1 i=0 进 i=0 i=-1 退出while i=-1 将i=3 进 i=3 i=2 退出while i=2 将i=4 进 i=4 i=3 进 i=3 i=2 退出while i=2 {-8, -1, 0, 1, 2, 3}

Basic algorithm:

First divide the entire sequence of elements to be sorted into several sub-elements Sequences (composed of elements separated by a certain "increment") are directly inserted and sorted, and then the increments are reduced in sequence and then sorted. When the elements in the entire sequence are basically in order (the increment is small enough), the entire sequence is sorted. The elements undergo a direct insertion sort. Because direct insertion sorting is very efficient when the elements are basically ordered (close to the best case), Hill sorting has a greater time efficiency than the first two methods. The choice of step size is an important part of Hill sorting. Any sequence of step sizes will work as long as the final step size is 1.

The algorithm initially sorts with a certain step size, then continues to sort with a certain step size, and finally the algorithm sorts with a step size of 1. When the step size is 1, the algorithm changes to insertion sort, which ensures that the data will be sorted. Donald Shell initially suggested choosing a step size of frac{n}{2} and halving the step size until the step size reaches 1. Although this approach can be better than mathcal{O}(n^2)-like algorithms (insertion sort), there is still room for reducing the average time and worst time.

Hill sorting example: an array of n=10 58 27 32 93 65 87 58 46 9 65, with a step size of n/2.为 The first sorting step is 10/2 = 5

58 27 32 93 65 87 58 46 9 65

2A 2A 3A 3A 3B

5A 5B

, with 5 as the step size, (1A,1B), (2A,2B), (3A,3B), etc. as grouping marks. The uppercase letters indicate which element of the group it is. The same numbers indicate that they are in the same group, so Divide it into 5 groups, namely (58,87), (27,58), (32,46), (93,9), (65,65), and then perform direct insertion sorting on each group. After sorting, there are 5 groups For (58,87), (27,58), (32,46), (9,93), (65,65), the group sorting just becomes the following table within each group, the same below.

The second sorting step is 5/2 = 2

希尔排序的时间性能优于直接插入排序的原因：
①当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。
②当n值较小时，n和n2的差别也较小，即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度0(n2)差别不大。
③在希尔排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量di逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经按di-1作为距离排过序，使文件较接近于有序状态，所以新的一趟排序过程也较快。

增量序列的选择：Shell排序的执行时间依赖于增量序列。
好的增量序列的共同特征(查到的资料都这么讲)：
① 最后一个增量必须为1；
② 应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。

package cglib; public class StringNumber { public static void main(String[] args) { int[] arr = new int[]{44,33,99,10,30,20,59,78,23,48}; System.out.print("排序前："); for(int o: arr) { System.out.print(o+" "); } System.out.println(); shellSort(arr); System.out.print("排序后："); for(int o: arr) { System.out.print(o+" "); } System.out.println(); } private static void shellSort(int[] arr) { int j; int len = arr.length; for(int val=len>>1; val>0; val>>=1) { //下面是对本次的所有分组做直接插入排序 for(int i=val; i
         Copy after login