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 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;

I hope this article has been helpful to you in the programming of C language.

Related articles: