介绍
- 英文名为shellsort，又称“缩小增量排序”
- 是直接插入排序算法的一种更高效的改进版本
- 希尔排序是把记录按下标的指定步长分组，然后按照每组使用直接插入排序，这样能保证一定程度上小的数值在前边
- 此排序需要有插入排序的基础，不清除的可以移步了解一下
解释起来有点拗口，直接按照步骤上图
代码
<!----java----->
public class shellsort {
public static void main(string[] args) {
int[] arr = {1260,134,209,408,34,68907,29,1034,51,855,2,33,566,7,12};
sort(arr);
system.out.println(arrays.tostring(arr));
}
public static void sort(int[] arr){
for(int gap=arr.length/2;gap>0;gap/=2){
for(int i=gap;i<arr.length;i++){
for(int j=i-gap;j>=0;j-=gap){
if(arr[j+gap]<arr[j]){
int temp = arr[j];
arr[j] = arr[j+gap];
arr[j+gap] = temp;
}else {
break;
}
}
}
}
}
}
<!------------------------>
运行结果；
[2, 7, 12, 29, 33, 34, 51, 134, 209, 408, 566, 855, 1034, 1260, 68907]
<!----python----->
def sort(arr):
step = len(arr) // 2;
while step > 0:
for i in range(step, len(arr)):
j = i - step
while j >= 0 and arr[j] > arr[j + step]:
arr[j], arr[j + step] = arr[j + step], arr[j];
j -= step
step //= 2;
print(arr)
if __name__ == '__main__':
arr = [1260, 134, 209, 408, 34, 68907, 29, 1034, 51, 855, 2, 33, 566, 7, 12]
sort(arr)
<!------------------------>
运行结果；
[2, 7, 12, 29, 33, 34, 51, 134, 209, 408, 566, 855, 1034, 1260, 68907]
复杂度
- 时间复杂度在平均情况下为o(n log n)，但在最坏情况下为o(n^2)
- 空间复杂度未明确给出,由于其本质上是插入排序的一种变体，可以推测其空间复杂度也为o(1)
- 它是稳定排序，意味着相等元素的相对顺序在排序后保持不变。
- 适用于快速排序的预处理
版权声明：本文内容由互联网用户贡献，该文观点仅代表作者本人。本站仅提供信息存储服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 2386932994@qq.com 举报，一经查实将立刻删除。
我要评论
发表评论