本文概述
- 复杂
- 算法
- C程序
- Java程序
- C＃程序
- 步骤1：以表格形式排列元素, 并使用插入排序对列进行排序。
- 步骤2：重复步骤1；每次只有较少数量的较长列, 这样一来最终只有一列数据要排序。
| 复杂 | 最好的情况 | 平均情况 | 最差的情况 |
|---|---|---|---|
| 时间复杂度 | Ω(n log(n)) | θ(n log(n)2) | O（n log（n）2） |
| 空间复杂度 | O(1) |
- 步骤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：结束
#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 : 6Enter 6 numbers: 3241021Sorted array is: 1 2 2 3 4 10Java程序
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 : 63241021Sorted array is: 1 2 2 3 4 10C＃程序
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 : 63241021Sorted array is: 1 2 2 3 4 10
