每天一个小算法（Shell Sort2）

希尔排序：

伪代码：

input: an array a of length n with array elements numbered 0 to n − 1

inc ← round(n/2)

while inc > 0 do:

    for i = inc .. n − 1 do:

        temp ← a[i]

        j ← i

        while j ≥ inc and a[j − inc] > temp do:

            a[j] ← a[j − inc]

            j ← j − inc

        a[j] ← temp

    inc ← round(inc / 2)

C语言实现：

#include <stdio.h>

#include <stdlib.h>

#define LEN 10

int main()

{

     int i, j, temp;

     int gap = 0;

     int a[] = {10,9,8,7,6,5,4,3,2,1};

     while (gap<=LEN)

     {

          gap = gap * 3 + 1;

     }

     while (gap > 0)

     {

         for ( i = gap; i < LEN; i++ )

         {

             j = i - gap;

             temp = a[i];

             while (( j >= 0 ) && ( a[j] > temp ))

             {

                 a[j + gap] = a[j];

                 j = j - gap;

             }

             a[j+gap] = temp;

         }

         gap = ( gap - 1 ) / 3;

     }

	 for(i=0;i<LEN;i++)

	 {

		 printf("%d\n",a[i]);

	 }

 }

巴特西

每天一个小算法（Shell Sort2）

最新文章

热门文章