Shulou(Shulou.com)06/02 Report--

This article is to share with you the content of the Hill sort + direct insertion sort example analysis of the insertion sort algorithm in Java. Xiaobian thinks it is quite practical, so share it with everyone for reference. Let's follow Xiaobian and have a look.

Hill sort

Before introducing Hill sorting, let's look at direct insertion sorting

I. Direct insertion sort 1. single-pass sort

x inserts an ordered interval

where end is pointing to the last element of the array.

2. direct insertion sort

According to the above single-pass sorting heuristic

end is the last element of the array, and all elements after end are to be sorted

A key decision point, end, and x compare sizes

here end

< x 还需要再做改善 可以发现有两个循环，一个循环时end倒着遍历完之后，使得最开始的end结束的数组加入x后是一个有序数组，最后再返回这个新数组的最后一个元素所在位置 注意公共部分 end--；x = a[end + 1]; 外面是一个for循环，从第二个到最后一个元素 for(i = 0; i < n - 1; i++){ } 代码： //插入排序void InsetSort(int* a, int n){ int end = 0; int i = 0; for (i = 0; i < n - 1; i++) { end = i; int x = a[end + 1]; while (end >

= 0) { if (a[end] > x) { a[end + 1] = a[end]; a[end] = x; } else { break; } end--; } } }

Time complexity O(N2)

Testing:

int main(){ int a[4] = { 2, 6, 5, 3 }; InsetSort(a, 4); //ShellSort(a, 4); int i = 0; for (i = 0; i

< 4; i++) { printf("%d ", a[i]); } printf("\n"); return 0;}

II. Hill sorting

Hill sorting method is also called reduction increment method

The basic idea of Hill sorting method is: first select an integer, divide all records in the file to be sorted into gap groups, divide all records with distance into the same group, and sort the records in each group. Then repeat the grouping and sorting process described above. When gap=1 is reached, all records are sorted in a unified group.

Hill sort is based on direct insertion sort, first group sort

Sort in groups of 3

Time Complexity:

Each row can be seen as an array of length gap directly inserted into the sort

There are gap groups, not all gap/n elements of course, but when the data is quite large we think of each array as gap/n elements.

So it's (1+2…+n/gap)gap

If gap = 1, then the time complexity is O(n2), equivalent to direct insertion sort

void ShellSort(int* a, int n){ int end = 0; int i = 0; int j = 0; int gap = 6; //presort for (j = 0; j

< gap; j++) { //最后一个数一定是1 gap = gap / 2; for (i = 0; i < n - gap; i++) { end = i; //这里其实就是直接插入排序，而数组的每个元素间隔是gap int x = a[end + gap]; while (end >

= 0) { if (a[end] > x) { a[end + gap] = a[end]; a[end] = x; } else { break; } end -= gap; } } }}

The test case is still an example of the sort inserted directly above

It turned out to be a success.

Third, test Hill sorting and direct insertion sorting performance//performance test TestOP(){ srand(time(0)); //Take 1000 numbers for example const int N = 10000; int* a1 = (int*)malloc(sizeof(int) * N); int* a2 = (int*)malloc(sizeof(int) * N); for (int i = 0; i < N; ++i) { a1[i] = rand(); a2[i] = a1[i]; } //here clock is the time to run here int begin1 = clock(); InsertSort(a1, N); int end1 = clock(); int begin2 = clock(); ShellSort(a2, N); int end2 = clock(); //end-begin is the time taken to sort printf("%d\n%d\n", end1 - begin1, end2 - begin2);}

It can be seen that Hill sort is much faster than direct sort, but Hill sort because the gap can be changed, there is no uniform time complexity, first according to the time complexity of O(n1.3) to do it

Thank you for reading! About "Java insertion sort algorithm Hill sort + direct insertion sort example analysis" This article is shared here, I hope the above content can have some help for everyone, so that we can learn more knowledge, if you think the article is good, you can share it to let more people see it!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.