希爾排序

希爾(Shell)排序是插入排序的概括，它通過比較由幾個位置的間隙分隔的元素來克服插入排序的缺點。 通常，希爾(Shell)排序執行以下步驟。

• 第1步：以扁平形式排列元素，並使用插入排序對列進行排序。
• 第2步：重複第1步; 每次使用較少數量的較長列，最終只需要對一列數據進行排序。

複雜性

演算法

Shell_Sort(Arr, n)


第1步 : SET FLAG = 1, GAP_SIZE = N
第2步 : 當 FLAG = 1 OR GAP_SIZE > 1 時，迴圈第3步到第6步。

第3步 :SET FLAG = 0
第4步 :SET GAP_SIZE = (GAP_SIZE + 1) / 2
第5步 :當 I = 0 到 I < (N -GAP_SIZE) 時，迴圈第6步。

第6步 :IF Arr[I + GAP_SIZE] > Arr[I]
        SWAP Arr[I + GAP_SIZE], Arr[I]
        SET FLAG = 0
第7步 : 迴圈

使用C語言實現希爾排序，代碼如下 -

#include <stdio.h>
void shellsort(int arr[], int num)
{
    int i, j, k, tmp;
    for (i = num / 2; i > 0; i = i / 2)
    {
        for (j = i; j < num; j++)
        {
            for(k = j - i; k >= 0; k = k - i)
            {
                if (arr[k+i] >= arr[k])
                break;
                else
                {
                    tmp = arr[k];
                    arr[k] = arr[k+i];
                    arr[k+i] = tmp;
                }
            }
        }
    }
}
int main()
{
    int arr[30];
    int k,  num;
    printf("Enter total no. of elements : ");
    scanf("%d", &num);
    printf("Enter %d numbers: ", num);

    for (k =  0 ; k < num; k++)
    {
        scanf("%d", &arr[k]);
    }
    shellsort(arr, num);
    printf("Sorted array is: ");
    for (k = 0; k < num; k++)
        printf("%d ", arr[k]);
    return 0;
}

執行上面示例代碼，得到以下結果：

Enter total no. of elements : 6
3
2
4
10
2
1

Sorted array is: 1 2 2 3 4 10

使用Java語言實現希爾排序，代碼如下 -

import java.util.*;
public class Shell_Sort
{
    static void shellsort(int[] arr, intnum)
    {
        int i, j, k, tmp;
        for (i = num / 2; i> 0; i = i / 2)
        {
            for (j = i; j<num; j++)
            {
                for(k = j - i; k>= 0; k = k - i)
                {
                    if (arr[k+i] >= arr[k])
                    break;
                    else
                    {
                        tmp = arr[k];
                        arr[k] = arr[k+i];
                        arr[k+i] = tmp;
                    }
                }
            }
        }
    }
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int arr[]= newint[30];
        intk,  num;
        System.out.println("Enter total no. of elements : ");
        num = sc.nextInt();
        for (k =  0 ; k<num; k++)
        {
            arr[k]=sc.nextInt();
        }
        shellsort(arr, num);
        System.out.println("\n Sorted array is: ");
        for (k = 0; k<num; k++)
            System.out.println(arr[k]);
    }
}

執行上面示例代碼，得到以下結果：

Enter total no. of elements : 6
3
2
4
10
2
1

Sorted array is: 1 2 2 3 4 10

使用C#語言實現希爾排序，代碼如下 -

using System;
public class Shell_Sort
{
    static void shellsort(int[] arr, int num)
    {
        int i, j, k, tmp;
        for (i = num / 2; i > 0; i = i / 2)
        {
            for (j = i; j < num; j++)
            {
                for(k = j - i; k >= 0; k = k - i)
                {
                    if (arr[k+i] >= arr[k])
                        break;
                    else
                    {
                        tmp = arr[k];
                        arr[k] = arr[k+i];
                        arr[k+i] = tmp;
                    }
                }
            }
        }
    }
    public void Main()
    {
        int[] arr=new int[10];
        int k,  num;
        Console.WriteLine("Enter total no. of elements : ");
        num = Convert.ToInt32(Console.ReadLine());
        for (k =  0 ; k < num; k++)
        {
            arr[k]=Convert.ToInt32(Console.ReadLine());
        }
        shellsort(arr, num);
        Console.WriteLine("\n Sorted array is: ");
        for (k = 0; k < num; k++)
            Console.WriteLine(arr[k]);
    }
}

執行上面示例代碼，得到以下結果：

Enter total no. of elements : 6
3
2
4
10
2
1

Sorted array is: 1 2 2 3 4 10