1. 问题描述:给定一个数组序列使用希尔排序算法对数组进行排序并且输出排序结果

2. ①
希尔排序又叫做缩小增量排序,其本质还是插入排序,只是在将待排序序列按照某种规则分成几个子序列,分别对这几个子序列进行直接插入排序,这个规则的体现就是增量的选取,如果选择增量为1那么就是直接插入排序。而希尔排序的每一趟排序都会使整个序列变得有序,等到整个序列有序了,那么再使用增量为1的插入排序的话那么就会使得排序的效率提高

所以希尔排序首先要解决的问题是使得数组内部的序列大部分是有序的,怎么样实现这个想法呢?方法是将数组按照不同的间隔分成若干个序列,在序列内进行直接插入排序,最后进行一趟直接插入排序

② 常用的增量是以2为跨度的增量,所以每一次排序的时候那么增量都为上一次的一半,这也就是我们常说的希尔增量

③ 一半来说算法的时间复杂度低于O(n ^ 2),但是在极端的情况下,希尔排序的时间复杂度仍然是O(n ^
2),甚至比直接比直接插入排序更慢,因为数组的在划分增量的时候每一次都没有在内部移动元素进行排序,因为在划分的序列中都是有序的,等到最后一次增量为1的时候那么菜进行直接插入排序这个时候排序就比直接插入排序更慢了,比如像下面的例子:
2 1 5 3 7 6 5 8
④ 希尔排序的空间复杂度为O(1)

3. Java代码如下:
import java.util.Arrays; public class Main { public static void main(String[]
args) { int array[] = {5, 3, 9, 6, 1, 7, 2, 4, 8, 10}; sort(array);
System.out.println(Arrays.toString(array)); } public static void sort(int
array[]){ int d = array.length; while(d > 1){ d = d / 2; for(int x = 0; x < d;
x++){ for(int i = x + d; i < array.length; i = i + d){ int temp = array[i]; int
j; for(j = i - d; j >= 0 && array[j] > temp; j = j - d){ array[j + d] =
array[j]; } array[j + d] = temp; } } } } }
 

技术
©2019-2020 Toolsou All rights reserved,
详解ubuntu14.04如何设置静态IPQCustomPlot系列(5)-实时动态曲线比尔·盖茨:疫情后彻底恢复正常可能要到2022年末华为认证HCIA-AI人工智能Python基础知识整理笔记百度、阿里、腾讯内部岗位级别和薪资结构,附带求职建议!Jsp+Ajax+Servlet+Mysql实现增删改查(一)2021年1月程序员工资统计,平均14915元Faster RCNN系列算法原理讲解(笔记)经典算法-递归(生兔子案例)