希尔排序算法实现

本文概述

• 复杂
• 算法
• C程序
• Java程序
• C＃程序

壳排序是插入排序的一般化, 它通过比较由多个位置的间隙分隔的元素来克服插入排序的缺点。通常, Shell sort执行以下步骤。

• 步骤1：以表格形式排列元素, 并使用插入排序对列进行排序。
• 步骤2：重复步骤1；每次只有较少数量的较长列, 这样一来最终只有一列数据要排序。

复杂

算法

Shell_Sort（Arr, n）

• 步骤1：SET FLAG = 1, GAP_SIZE = N
• 步骤2：在FLAG = 1或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：如果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("\nEnter %d numbers: ", num);  

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

输出：

Enter total no. of elements : 6

Enter 6 numbers: 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