An shell sorting instance of the basic sorting algorithm of C language
- 2020-05-27 06:53:00
- OfStack
In this paper, an example of shell sorting algorithm in C language is presented. I will share it with you for your reference as follows:
shell sort is an improvement on the direct insert method.
/*-------------------------------------------------------------------------------------
Shell_sort.h
shell Sorting is an improvement on the direct insert method, which does not compare adjacent elements, but pairs 1 A comparison of elements at regular intervals .
Several ways to select an incremental sequence: ( For convenience, this example USES the first 1 Species increment sequence )
1. h[1]=size . h[k] = h[k-1]/2.
The worst running time is O(N^2).
Worst case: the array length is zero 2^n, The even position of the array is the same 1 The number, the odd position is the same thing 1 The number,
And it's smaller than the even position. Now to the end 1 Before traversal shell Sorting actually does nothing.
The last 1 Subtraversal is equivalent to the direct insert method.
2. Hibbard Incremental sequence: h = 1,3,7,,2^k-1
The main difference between this and the above is that adjacent increments have no common factor
The worst running time is O(n^{1.5});
3. Sedgewick Incremental sequence: {1 . 5 . 19 . 41 . 109 . }
-------------------------------------------------------------------------------------*/
#ifndef SHELL_SORT_H
#define SHELL_SORT_H
#include "typedef.h"
void Shell_sort(T* a, int n)
{
for(int gap = n; gap > 0; gap = gap/2)
{
for(int i = 0; i != n; ++i)
{
T temp = a[i];
int j = i - gap;
for( ; j >= 0 && a[j] > temp; j = j-gap)
a[j+gap] = a[j];
a[j+gap] = temp;
}
}
}
#endif
I hope this article has been helpful to you in the programming of C language.