java排序算法之如何实现希尔排序-创新互联
小编给大家分享一下java排序算法之如何实现希尔排序，相信大部分人都还不怎么了解，因此分享这篇文章给大家参考一下，希望大家阅读完这篇文章后大有收获，下面让我们一起去了解一下吧！
1、介绍。
希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因D.L.Shell于1959年提出而得名。希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
希尔排序是不稳定排序，不需要额外内存，空间复杂度O(1)。时间复杂度，最佳情况：O(nlog^2n) 最差情况：O(nlog^2n) 平均情况：O(nlogn)。
2、步骤。
我们来看下希尔排序的基本步骤，在此我们选择增量gap=length/2，缩小增量继续以gap = gap/2的方式，这种增量选择我们可以用一个序列来表示，{n/2,(n/2)/2...1}，称为增量序列。希尔排序的增量序列的选择与证明是个数学难题，我们选择XM返佣www.kaifx.cn/broker/xm.html的这个增量序列是比较常用的，也是希尔建议的增量，称为希尔增量，但其实这个增量序列不是最优的。此处我们做示例使用希尔增量。先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；按增量序列个数k，对序列进行k 趟排序；每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
3、代码。
public static void main(String[] args) {
System.out.println("------开始------");
//生成生成两份随机数组，其中用系统自带的方法进行排序，到时候进行验证。
final int number = 100000;
int[] sortArray = new int[number];
int[] sortArrayCopy = new int[number];
for (int i = 0; i < sortArray.length; i++) {
sortArray[i] = (int) (Math.random()number);
}
System.arraycopy(sortArray, 0, sortArrayCopy, 0, number);//数组复制
Arrays.sort(sortArrayCopy);
//开始排序
long startTime = System.currentTimeMillis();
shellInsertSort(sortArray);//希尔插入排序
System.out.println("花费时间：" + (System.currentTimeMillis() - startTime));
//跟系统排序之后数组进行比较，查看是否排序成功。
if (Arrays.equals(sortArray, sortArrayCopy)) {
System.out.println("排序成功");
} else {
System.out.println("排序失败");
}
System.out.println("------结束------");
}
//希尔插入排序 最佳情况：T(n) = O(nlog2 n) 最坏情况：T(n) = O(nlog2 n) 平均情况：T(n) =O(nlog2n)
private static void shellInsertSort(int[] array) {
int groups = array.length / 2;//增量，一共的组数
while (groups > 0) {
//将groups看作1，就会跟直接插入排序的算法一模一样
for (int i = groups; i < array.length; i++) {//n-1轮 第一个无需排序
int curIndex = i;
while (curIndex > groups - 1) {
if (array[curIndex] > array[curIndex - groups]) {
break;
}
int flag = array[curIndex];
array[curIndex] = array[curIndex - groups];
array[curIndex - groups] = flag;
curIndex -= groups;
}
}
groups /= 2;
}
}
#include
using namespace std;
void shellSort(int
{
int gap,i,j,temp;
for (gap = n / 2; gap > 0;gap /= 2)
{
for (i = gap; i < n;i++)
{
if (a[i]
temp = a[i];
j = i - gap;
for (; j >= 0 && a[j] > temp;j-=gap)
{
a[j + gap] = a[j];
}
a[j + gap] = temp;
}
}
}
}
int main(int argc, charargv[])
{
int a[10] = {5,3,4,8,6,1,2,9,7,10};
shellSort(a, 10);
for (int i = 0; i < 10;i++)
{
cout << a[i] << " ";
}
cout << endl;
system("pause");
return 0;
}
import java.util.Arrays;
public class ShellSort {
public static void main(String[] args) {
int[] array={3,6,4,1,9,7,6,5,4,0,10,8,21,35};
System.out.println(Arrays.toString(array));
shellSort01(array);
System.out.println(Arrays.toString(array));
}
private static void shellSort01(int[] array) {
int gap=array.length;
while(true){
gap=gap/3+1;
insertSortWithGap01(array,gap);
if(gap==1){
break;
}
}
}
private static void insertSortWithGap01(int[] array, int gap) {
for(int i=gap;i
int j;
for(j=i-gap;j>=0&&array[j]>key;j-=gap){
array[j+gap]=array[j];
}
array[j+gap]=key;
}
}
}
public static void sort(long[] arr) {
//初始化一个间隔
int h = 1;
//计算大间隔
while(h < arr.length / 3) {
h = h3 + 1;
}
while(h > 0) {
//进行插入排序
long tmp = 0;
for(int i = h; i < arr.length; i++) {
tmp = arr[i];
int j = i;
while(j > h - 1 && arr[j - h] >= tmp) {
arr[j] = arr[j - h];
j -= h;
}
arr[j] = tmp;
}
//减小间隔
h = (h - 1) / 3;
}
}
}
以上是“java排序算法之如何实现希尔排序”这篇文章的所有内容，感谢各位的阅读！相信大家都有了一定的了解，希望分享的内容对大家有所帮助，如果还想学习更多知识，欢迎关注创新互联网站制作公司行业资讯频道！
创新互联www.cdcxhl.cn，专业提供香港、美国云服务器，动态BGP最优骨干路由自动选择，持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证， 机房独有T级流量清洗系统配攻击溯源，准确进行流量调度，确保服务器高可用性。佳节活动现已开启，新人活动云服务器买多久送多久。
本文标题：java排序算法之如何实现希尔排序-创新互联
URL分享：http://ybzwz.com/article/ppssi.html
