希尔排序基础java代码 希尔排序基础java代码

Java的希尔排序我写的这段跳不出循环，我看不出问题在哪。。。有谁能帮一下？

你的程序无限循环的主要原因是for(int j=0;jh;j=j++)中的j=j++语句造成的,在java中j++是先赋值后自加,j永远也不会自增,

10年积累的网站设计制作、做网站经验，可以快速应对客户对网站的新想法和需求。提供各种问题对应的解决方案。让选择我们的客户得到更好、更有力的网络服务。我虽然不认识你，你也不认识我。但先做网站后付款的网站建设流程，更有顺德免费网站建设让你可以放心的选择与我们合作。

其它也有不对的地方,我都帮你改正了,完整的程序如下(改动的地方见注释)

import java.util.Arrays;

public class test3 {

public static void main(String[] args) {

int[] arr = {2,9,41,5,7,2,6};

sort(arr);

System.out.println(Arrays.toString(arr));

}

public static int[] sort(int[] arr){

int h = arr.length;//这里把h=1改成h=arr.length

//这里去掉下面的while循环

//while(h arr.length/2){

// h = h * 2 + 1;

//}

while(h 1){ //这里把h=1改成h1

h = (int)(h / 2);//这里对h取整数并且移到这里

for(int j = 0; j h; j++) { //这里把j = j++改成j++

for (int i = j + h; i arr.length; i = i + h) {

for(int z = i -h; z = 0; z--) { //这里把z=i -1改成z=i-h

if (arr[z] arr[i]) {

int temp;

temp = arr[z];

arr[z] = arr[i];

arr[i] = temp;

}

}

}

}

}

return arr;

}

}

写一个简单的JAVA排序程序

// 排序

public class Array

{

public static int[] random(int n) //产生n个随机数，返回整型数组

{

if (n0)

{

int table[] = new int[n];

for (int i=0; itable.length; i++)

table[i] = (int)(Math.random()*100); //产生一个0～100之间的随机数

return table; //返回一个数组

}

return null;

}

public static void print(int[] table) //输出数组元素

{

if (table!=null)

for (int i=0; itable.length; i++)

System.out.print(" "+table[i]);

System.out.println();

}

public static void insertSort(int[] table) //直接插入排序

{ //数组是引用类型，元素值将被改变

System.out.println("直接插入排序");

for (int i=1; itable.length; i++) //n-1趟扫描

{

int temp=table[i], j; //每趟将table[i]插入到前面已排序的序列中

// System.out.print("移动");

for (j=i-1; j-1 temptable[j]; j--) //将前面较大元素向后移动

{

// System.out.print(table[j]+", ");

table[j+1] = table[j];

}

table[j+1] = temp; //temp值到达插入位置

System.out.print("第"+i+"趟: ");

print(table);

}

}

public static void shellSort(int[] table) //希尔排序

{

System.out.println("希尔排序");

for (int delta=table.length/2; delta0; delta/=2) //控制增量，增量减半，若干趟扫描

{

for (int i=delta; itable.length; i++) //一趟中若干组，每个元素在自己所属组内进行直接插入排序

{

int temp = table[i]; //当前待插入元素

int j=i-delta; //相距delta远

while (j=0 temptable[j]) //一组中前面较大的元素向后移动

{

table[j+delta] = table[j];

j-=delta; //继续与前面的元素比较

}

table[j+delta] = temp; //插入元素位置

}

System.out.print("delta="+delta+" ");

print(table);

}

}

private static void swap(int[] table, int i, int j) //交换数组中下标为i、j的元素

{

if (i=0 itable.length j=0 jtable.length i!=j) //判断i、j是否越界

{

int temp = table[j];

table[j] = table[i];

table[i] = temp;

}

}

public static void bubbleSort(int[] table) //冒泡排序

{

System.out.println("冒泡排序");

boolean exchange=true; //是否交换的标记

for (int i=1; itable.length exchange; i++) //有交换时再进行下一趟，最多n-1趟

{

exchange=false; //假定元素未交换

for (int j=0; jtable.length-i; j++) //一次比较、交换

if (table[j]table[j+1]) //反序时，交换

{

int temp = table[j];

table[j] = table[j+1];

table[j+1] = temp;

exchange=true; //有交换

}

System.out.print("第"+i+"趟: ");

print(table);

}

}

public static void quickSort(int[] table) //快速排序

{

quickSort(table, 0, table.length-1);

}

private static void quickSort(int[] table, int low, int high) //一趟快速排序，递归算法

{ //low、high指定序列的下界和上界

if (lowhigh) //序列有效

{

int i=low, j=high;

int vot=table[i]; //第一个值作为基准值

while (i!=j) //一趟排序

{

while (ij vot=table[j]) //从后向前寻找较小值

j--;

if (ij)

{

table[i]=table[j]; //较小元素向前移动

i++;

}

while (ij table[i]vot) //从前向后寻找较大值

i++;

if (ij)

{

table[j]=table[i]; //较大元素向后移动

j--;

}

}

table[i]=vot; //基准值的最终位置

System.out.print(low+".."+high+", vot="+vot+" ");

print(table);

quickSort(table, low, j-1); //前端子序列再排序

quickSort(table, i+1, high); //后端子序列再排序

}

}

public static void selectSort(int[] table) //直接选择排序

{

System.out.println("直接选择排序");

for (int i=0; itable.length-1; i++) //n-1趟排序

{ //每趟在从table[i]开始的子序列中寻找最小元素

int min=i; //设第i个数据元素最小

for (int j=i+1; jtable.length; j++) //在子序列中查找最小值

if (table[j]table[min])

min = j; //记住最小元素下标

if (min!=i) //将本趟最小元素交换到前边

{

int temp = table[i];

table[i] = table[min];

table[min] = temp;

}

System.out.print("第"+i+"趟: ");

print(table);

}

}

private static void sift(int[] table, int low, int high) //将以low为根的子树调整成最小堆

{ //low、high是序列下界和上界

int i=low; //子树的根

int j=2*i+1; //j为i结点的左孩子

int temp=table[i]; //获得第i个元素的值

while (j=high) //沿较小值孩子结点向下筛选

{

if (jhigh table[j]table[j+1]) //数组元素比较（改成为最大堆）

j++; //j为左右孩子的较小者

if (temptable[j]) //若父母结点值较大（改成为最大堆）

{

table[i]=table[j]; //孩子结点中的较小值上移

i=j; //i、j向下一层

j=2*i+1;

}

else

j=high+1; //退出循环

}

table[i]=temp; //当前子树的原根值调整后的位置

System.out.print("sift "+low+".."+high+" ");

print(table);

}

public static void heapSort(int[] table)

{

System.out.println("堆排序");

int n=table.length;

for (int j=n/2-1; j=0; j--) //创建最小堆

sift(table, j, n-1);

// System.out.println("最小堆？ "+isMinHeap(table));

for (int j=n-1; j0; j--) //每趟将最小值交换到后面，再调整成堆

{

int temp = table[0];

table[0] = table[j];

table[j] = temp;

sift(table, 0, j-1);

}

}

public static void mergeSort(int[] X) //归并排序

{

System.out.println("归并排序");

int n=1; //已排序的子序列长度，初值为1

int[] Y = new int[X.length]; //Y数组长度同X数组

do

{

mergepass(X, Y, n); //一趟归并，将X数组中各子序列归并到Y中

print(Y);

n*=2; //子序列长度加倍

if (nX.length)

{

mergepass(Y, X, n); //将Y数组中各子序列再归并到X中

print(X);

n*=2;

}

} while (nX.length);

}

private static void mergepass(int[] X, int[] Y, int n) //一趟归并

{

System.out.print("子序列长度n="+n+" ");

int i=0;

while (iX.length-2*n+1)

{

merge(X,Y,i,i+n,n);

i += 2*n;

}

if (i+nX.length)

merge(X,Y,i,i+n,n); //再一次归并

else

for (int j=i; jX.length; j++) //将X剩余元素复制到Y中

Y[j]=X[j];

}

private static void merge(int[] X, int[] Y, int m, int r, int n) //一次归并

{

int i=m, j=r, k=m;

while (ir jr+n jX.length) //将X中两个相邻子序列归并到Y中

if (X[i]X[j]) //较小值复制到Y中

Y[k++]=X[i++];

else

Y[k++]=X[j++];

while (ir) //将前一个子序列剩余元素复制到Y中

Y[k++]=X[i++];

while (jr+n jX.length) //将后一个子序列剩余元素复制到Y中

Y[k++]=X[j++];

}

public static void main(String[] args)

{

// int[] table = {52,26,97,19,66,8,49};//Array.random(9);{49,65,13,81,76,97,38,49};////{85,12,36,24,47,30,53,91,76};//;//{4,5,8,1,2,7,3,6};// {32,26,87,72,26,17};//

int[] table = {13,27,38,49,97,76,49,81}; //最小堆

System.out.print("关键字序列: ");

Array.print(table);

// Array.insertSort(table);

// Array.shellSort(table);

// Array.bubbleSort(table);

// Array.quickSort(table);

// Array.selectSort(table);

// Array.heapSort(table);

// Array.mergeSort(table);

System.out.println("最小堆序列? "+Array.isMinHeap(table));

}

//第9章习题

public static boolean isMinHeap(int[] table) //判断一个数据序列是否为最小堆

{

if (table==null)

return false;

int i = table.length/2 -1; //最深一棵子树的根结点

while (i=0)

{

int j=2*i+1; //左孩子

if (jtable.length)

if (table[i]table[j])

return false;

else

if (j+1table.length table[i]table[j+1]) //右孩子

return false;

i--;

}

return true;

}

}

/*

程序运行结果如下：

关键字序列: 32 26 87 72 26 17 8 40

直接插入排序

第1趟排序: 26 32 87 72 26 17 8 40

第2趟排序: 26 32 87 72 26 17 8 40

第3趟排序: 26 32 72 87 26 17 8 40

第4趟排序: 26 26 32 72 87 17 8 40 //排序算法稳定

第5趟排序: 17 26 26 32 72 87 8 40

第6趟排序: 8 17 26 26 32 72 87 40

第7趟排序: 8 17 26 26 32 40 72 87

关键字序列: 42 1 74 25 45 29 87 53

直接插入排序

第1趟排序: 1 42 74 25 45 29 87 53

第2趟排序: 1 42 74 25 45 29 87 53

第3趟排序: 1 25 42 74 45 29 87 53

第4趟排序: 1 25 42 45 74 29 87 53

第5趟排序: 1 25 29 42 45 74 87 53

第6趟排序: 1 25 29 42 45 74 87 53

第7趟排序: 1 25 29 42 45 53 74 87

关键字序列: 21 12 2 40 99 97 68 57

直接插入排序

第1趟排序: 12 21 2 40 99 97 68 57

第2趟排序: 2 12 21 40 99 97 68 57

第3趟排序: 2 12 21 40 99 97 68 57

第4趟排序: 2 12 21 40 99 97 68 57

第5趟排序: 2 12 21 40 97 99 68 57

第6趟排序: 2 12 21 40 68 97 99 57

第7趟排序: 2 12 21 40 57 68 97 99

关键字序列: 27 38 65 97 76 13 27 49 55 4

希尔排序

delta=5 13 27 49 55 4 27 38 65 97 76

delta=2 4 27 13 27 38 55 49 65 97 76

delta=1 4 13 27 27 38 49 55 65 76 97

关键字序列: 49 38 65 97 76 13 27 49 55 4 //严书

希尔排序

delta=5 13 27 49 55 4 49 38 65 97 76

delta=2 4 27 13 49 38 55 49 65 97 76 //与严书不同

delta=1 4 13 27 38 49 49 55 65 76 97

关键字序列: 65 34 25 87 12 38 56 46 14 77 92 23

希尔排序

delta=6 56 34 14 77 12 23 65 46 25 87 92 38

delta=3 56 12 14 65 34 23 77 46 25 87 92 38

delta=1 12 14 23 25 34 38 46 56 65 77 87 92

关键字序列: 84 12 43 62 86 7 90 91

希尔排序

delta=4 84 7 43 62 86 12 90 91

delta=2 43 7 84 12 86 62 90 91

delta=1 7 12 43 62 84 86 90 91

关键字序列: 32 26 87 72 26 17

冒泡排序

第1趟排序: 26 32 72 26 17 87

第2趟排序: 26 32 26 17 72 87

第3趟排序: 26 26 17 32 72 87

第4趟排序: 26 17 26 32 72 87

第5趟排序: 17 26 26 32 72 87

关键字序列: 1 2 3 4 5 6 7 8

冒泡排序

第1趟排序: 1 2 3 4 5 6 7 8

关键字序列: 1 3 2 4 5 8 6 7

冒泡排序

第1趟排序: 1 2 3 4 5 6 7 8

第2趟排序: 1 2 3 4 5 6 7 8

关键字序列: 4 5 8 1 2 7 3 6

冒泡排序

第1趟排序: 4 5 1 2 7 3 6 8

第2趟排序: 4 1 2 5 3 6 7 8

第3趟排序: 1 2 4 3 5 6 7 8

第4趟排序: 1 2 3 4 5 6 7 8

第5趟排序: 1 2 3 4 5 6 7 8

关键字序列: 38 26 97 19 66 1 5 49

0..7, vot=38 5 26 1 19 38 66 97 49

0..3, vot=5 1 5 26 19 38 66 97 49

2..3, vot=26 1 5 19 26 38 66 97 49

5..7, vot=66 1 5 19 26 38 49 66 97

关键字序列: 38 5 49 26 19 97 1 66

0..7, vot=38 1 5 19 26 38 97 49 66

0..3, vot=1 1 5 19 26 38 97 49 66

1..3, vot=5 1 5 19 26 38 97 49 66

2..3, vot=19 1 5 19 26 38 97 49 66

5..7, vot=97 1 5 19 26 38 66 49 97

5..6, vot=66 1 5 19 26 38 49 66 97

关键字序列: 49 38 65 97 76 13 27 49

0..7, vot=49 49 38 27 13 49 76 97 65

0..3, vot=49 13 38 27 49 49 76 97 65

0..2, vot=13 13 38 27 49 49 76 97 65

1..2, vot=38 13 27 38 49 49 76 97 65

5..7, vot=76 13 27 38 49 49 65 76 97

关键字序列: 27 38 65 97 76 13 27 49 55 4

low=0 high=9 vot=27 4 27 13 27 76 97 65 49 55 38

low=0 high=2 vot=4 4 27 13 27 76 97 65 49 55 38

low=1 high=2 vot=27 4 13 27 27 76 97 65 49 55 38

low=4 high=9 vot=76 4 13 27 27 38 55 65 49 76 97

low=4 high=7 vot=38 4 13 27 27 38 55 65 49 76 97

low=5 high=7 vot=55 4 13 27 27 38 49 55 65 76 97

关键字序列: 38 26 97 19 66 1 5 49

直接选择排序

第0趟排序: 1 26 97 19 66 38 5 49

第1趟排序: 1 5 97 19 66 38 26 49

第2趟排序: 1 5 19 97 66 38 26 49

第3趟排序: 1 5 19 26 66 38 97 49

第4趟排序: 1 5 19 26 38 66 97 49

第5趟排序: 1 5 19 26 38 49 97 66

第6趟排序: 1 5 19 26 38 49 66 97

最小堆

关键字序列: 81 49 76 27 97 38 49 13 65

sift 3..8 81 49 76 13 97 38 49 27 65

sift 2..8 81 49 38 13 97 76 49 27 65

sift 1..8 81 13 38 27 97 76 49 49 65

sift 0..8 13 27 38 49 97 76 49 81 65

13 27 38 49 97 76 49 81 65

sift 0..7 27 49 38 65 97 76 49 81 13

sift 0..6 38 49 49 65 97 76 81 27 13

sift 0..5 49 65 49 81 97 76 38 27 13

sift 0..4 49 65 76 81 97 49 38 27 13

sift 0..3 65 81 76 97 49 49 38 27 13

sift 0..2 76 81 97 65 49 49 38 27 13

sift 0..1 81 97 76 65 49 49 38 27 13

sift 0..0 97 81 76 65 49 49 38 27 13

最大堆

关键字序列: 49 65 13 81 76 27 97 38 49

sift 3..8 49 65 13 81 76 27 97 38 49

sift 2..8 49 65 97 81 76 27 13 38 49

sift 1..8 49 81 97 65 76 27 13 38 49

sift 0..8 97 81 49 65 76 27 13 38 49

97 81 49 65 76 27 13 38 49

sift 0..7 81 76 49 65 49 27 13 38 97

sift 0..6 76 65 49 38 49 27 13 81 97

sift 0..5 65 49 49 38 13 27 76 81 97

sift 0..4 49 38 49 27 13 65 76 81 97

sift 0..3 49 38 13 27 49 65 76 81 97

sift 0..2 38 27 13 49 49 65 76 81 97

sift 0..1 27 13 38 49 49 65 76 81 97

sift 0..0 13 27 38 49 49 65 76 81 97

关键字序列: 52 26 97 19 66 8 49

归并排序

子序列长度n=1 26 52 19 97 8 66 49

子序列长度n=2 19 26 52 97 8 49 66

子序列长度n=4 8 19 26 49 52 66 97

关键字序列: 13 27 38 49 97 76 49 81 65

最小堆序列? true

*/

05《算法入门教程》希尔排序

本节内容是排序算法系列之一： 希尔排序 ，主要讲解了希尔排序的主体思路，选取了一个待排序的数字列表对希尔排序算法进行了演示，给出了希尔排序算法的 Java 代码实现，帮助大家可以更好的理解希尔排序算法。

希尔排序（Shell Sort），是计算机科学与技术领域中较为简单的一种排序算法。

希尔排序是插入排序的一种，有时候也被称为 “缩小增量排序”。它是插入排序的改进版，与插入排序的不同之处在于，希尔排序会优先比较距离较远的元素。希尔排序是按照其设计者希尔（Donald Shell）的名字命名而来，并于 1959 年公布出来。

在介绍完希尔排序之后，我们一起来看一下希尔排序的实现步骤具体是什么样的吧。这里我们假设待排序的序列为 [9,2,11,7,12,5]，我们按照从小到大的序列进行排序。

选择一个增量序列 k1，k2, … km，其中 k1k2…km=1，即增量序列大小依次减小，并且最后一个增量序列大小为 1。

按照增量序列的个数 m，对整个待排序序列进行 m 趟排序。

每一趟排序，根据对应的增量 ki，需要将待排序的序列分成对应长度的子序列，分别在子序列上面进行直接插入排序。当且仅当增量序列为 1 时，整个序列作为一个整体处理。

其实，上面的 步骤 1 和 步骤 2 都是在排序之前进行的处理，选择对应的增量。上面的 步骤 3 每执行一次，就相当于是进行了一次插入排序，只是每次都会选择一个增量，将整个待排序序列按照增量进行划分，然后在对应增量上面进行插入排序。接下来，让我们用上面的待排序数字队列 [9,2,11,7,12,5] 进行整个算法步骤的排序演示工作。

按照 2.1 节的排序步骤，我们需要先选择对应的希尔排序中的增量值，按照一般性的原则，我们可以将增量按照待排序的序列长度依次整除 2，直到增量为 1 停止，得到对应的增量。如下：

接着，我们调用 2.1 中的 步骤 2, 步骤 3 ，按照增量值的取法，依次进行对应序列的插入排序，首先我们取增量值为 3，对应排序示例如下：

在完成增量为 3 的插入排序之后，我们接着进行增量为 1 的插入排序，这个步骤其实跟我们之前的插入排序步骤完全一致。整个过程如下：

从上面的示例可以看出，其实整个希尔排序的过程，就是根据增量大小依次进行插入排序，本质上还是针对插入排序的一种优化。

在说明希尔排序的整个过程之后，接下来，我们看看如何用 Java 代码实现希尔排序算法。

运行结果如下：

代码中的第 8 行初始化一个需要排序的数组，后面按照从小到大的排序规则，实现了数组的排序。第 12 行至 30 行是整个希尔排序的流程。第 14 行代码表示希尔排序中的增量每次整除 2 取得，第 17 行至 25 行是一个 for 循环结构，表明按照增量进行插入排序。最后第 32 行代码输出排序好的数组。

本节主要学习了希尔排序算法，通过本节课程的学习，需要熟悉希尔排序的算法流程，知道希尔排序算法的实现思路，可以自己用代码实现希尔排序算法。至此，我们已经学习了排序算法中的冒泡排序、插入排序、选择排序、希尔排序。

java中希尔排序算法代码

public class ShellSort {  

//交换数组元素  

private static void swap(int[] a, int i, int j) {  

int t = a[i];  

a[i] = a[j];  

a[j] = t;  

}  

public static void sort(int[] a) {  

int h = 1;  

while (h  a.length / 3) {//寻找合适的间隔h  

h = 3 * h + 1;  

}  

while (h = 1) {  

//将数组变为间隔h个元素有序  

for (int i = h; i  a.length; i++) {  

//间隔h插入排序  

for (int j = i; j = h  a[j]  a[j - h]; j -= h) {  

swap(a, j, j - h);  

}  

}  

h /= 3;  

}  

}  

}

Java几种简单的排序源代码

给你介绍4种排序方法及源码，供参考

1.冒泡排序

主要思路： 从前往后依次交换两个相邻的元素，大的交换到后面，这样每次大的数据就到后面，每一次遍历，最大的数据到达最后面，时间复杂度是O(n^2)。

public static void bubbleSort(int[] arr){

for(int i =0; i  arr.length - 1; i++){

for(int j=0; j  arr.length-1; j++){

if(arr[j]  arr[j+1]){

arr[j] = arr[j]^arr[j+1];

arr[j+1] = arr[j]^arr[j+1];

arr[j] = arr[j]^arr[j+1];

}

}

}

}

2.选择排序

主要思路：每次遍历序列，从中选取最小的元素放到最前面，n次选择后，前面就都是最小元素的排列了，时间复杂度是O(n^2）。

public static void selectSort(int[] arr){

for(int i = 0; i arr.length -1; i++){

for(int j = i+1; j  arr.length; j++){

if(arr[j]  arr[i]){

arr[j] = arr[j]^arr[i];

arr[i] = arr[j]^arr[i];

arr[j] = arr[j]^arr[i];

}

}

}

}

3.插入排序

主要思路：使用了两层嵌套循环，逐个处理待排序的记录。每个记录与前面已经排好序的记录序列进行比较，并将其插入到合适的位置，时间复杂度是O(n^2）。

public static void insertionSort(int[] arr){

int j;

for(int p = 1; p  arr.length; p++){

int temp = arr[p];   //保存要插入的数据

//将无序中的数和前面有序的数据相比，将比它大的数，向后移动

for(j=p; j0  temp arr[j-1]; j--){

arr[j] = arr[j-1];

}

//正确的位置设置成保存的数据

arr[j] = temp;

}

}

4.希尔排序

主要思路：用步长分组，每个分组进行插入排序，再慢慢减小步长，当步长为1的时候完成一次插入排序，  希尔排序的时间复杂度是：O（nlogn）～O（n2），平均时间复杂度大致是O(n^1.5)

public static void shellSort(int[] arr){

int j ;

for(int gap = arr.length/2; gap  0 ; gap/=2){

for(int i = gap; i  arr.length; i++){

int temp = arr[i];

for(j = i; j=gap  temparr[j-gap]; j-=gap){

arr[j] = arr[j-gap];

}

arr[j] = temp;

}

}

}