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

Most people don't understand the knowledge points of this article "How to implement Hill sorting algorithm in C++", so Xiaobian summarizes the following contents for everyone. The contents are detailed, the steps are clear, and they have certain reference value. I hope everyone can gain something after reading this article. Let's take a look at this article "How to implement Hill sorting algorithm in C++".

1. Code Template//Shell Sort void ShellSort(SqList *L){ int i, j; int increment = L->length; //initialize the increment to the length of the sequence do { increment = increment / 3 + 1; //calculate the delta value for (i = increment + 1; i length; i ++ ) { if (L->arr[i]

arr[i - increment]) { //If L->[i] needs to insert ordered increment subtable L->arr[0] = L->arr[i]; //temporarily stored in sentinel position for (j = i - increment; j > 0 && L->arr[0]

arr[j]; j -= increment) { //traverse the increment subtable to find the insertion position L->arr[j + increment] = L->arr[j]; } L->arr[j+increment] = L->arr[0]; //insert } } } while (increment > 1);}2. Algorithm Introduction

Hill sort, also known as reduced incremental sort, the algorithm belongs to the advanced algorithm of insertion sort, adopting the strategy of jumping segmentation, moving the elements with smaller keywords forward, greatly reducing the number of exchange comparisons. So that the sequence as a whole is basically orderly, that is, the large elements are basically in the back, the small elements are basically in the front, and the medium elements are basically in the middle.

The key to Hill sorting is to group elements separated by an increment into a subsequence, and the last increment of the sequence must be 1, so that the final result is orderly and correct. However, how to choose the best increment is still inconclusive. And since the elements move in jumps, all Hill sorting is an unstable sorting algorithm with time complexity affected by incremental selection, which is O(n^1.3) at best and O(n*n) at worst.

3. Examples #include using namespace std;const int N = 100;typedef struct{ int arr[N]; //store the sequence to be sorted int length; //store length of sequence} SqList;void ShellSort(SqList *L){ int i, j; int increment = L->length; do { increment = increment / 3 + 1; for (i = increment + 1; i length; i ++ ) { if (L->arr[i]

arr[i - increment]) { L->arr[0] = L->arr[i]; for (j = i - increment; j > 0 && L->arr[0]

arr[j]; j -= increment) L->arr[j + increment] = L->arr[j]; L->arr[j + increment] = L->arr[0]; } } } while (increment > 1);}int main(){ SqList L; L.arr[1] = 50; L.arr[2] = 10; L.arr[3] = 90; L.arr[4] = 30; L.arr[5] = 70; L.arr[6] = 40; L.arr[7] = 80; L.arr[8] = 60; L.arr[9] = 20; L.length = 9; ShellSort(&L); for (int i = 1; i

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.