利用Java實現(xiàn)一個希爾排序的方法？針對這個問題，這篇文章詳細(xì)介紹了相對應(yīng)的分析和解答，希望可以幫助更多想解決這個問題的小伙伴找到更簡單易行的方法。
成都創(chuàng)新互聯(lián)公司自2013年創(chuàng)立以來，是專業(yè)互聯(lián)網(wǎng)技術(shù)服務(wù)公司，擁有項目成都做網(wǎng)站、成都網(wǎng)站制作網(wǎng)站策劃，項目實施與項目整合能力。我們以讓每一個夢想脫穎而出為使命，1280元五常做網(wǎng)站,已為上家服務(wù),為五常各地企業(yè)和個人服務(wù),聯(lián)系電話:18982081108
一、希爾排序(Shell Sort)
希爾排序（Shell Sort）是一種插入排序算法，因D.L.Shell于1959年提出而得名。
Shell排序又稱作縮小增量排序。
二、希爾排序的基本思想
希爾排序的中心思想就是：將數(shù)據(jù)進(jìn)行分組，然后對每一組數(shù)據(jù)進(jìn)行排序，在每一組數(shù)據(jù)都有序之后，就可以對所有的分組利用插入排序進(jìn)行最后一次排序。這樣可以顯著減少交換的次數(shù)，以達(dá)到加快排序速度的目的。
希爾排序的中心思想：先取一個小于n的整數(shù)d1作為第一個增量，把文件的全部記錄分成d1個組。所有距離為dl的倍數(shù)的記錄放在同一個組中。先在各組內(nèi)進(jìn)行直接插人排序；然后，取第二個增量d2 該方法實質(zhì)上是一種分組插入方法。 shell排序的算法實現(xiàn): 注意： 當(dāng)增量d=1時，ShellPass和InsertSort基本一致，只是由于沒有哨兵而在內(nèi)循環(huán)中增加了一個循環(huán)判定條件"j>0"，以防下標(biāo)越界。 三、希爾排序算法分析 1、增量序列的選擇。 Shell排序的執(zhí)行時間依賴于增量序列。好的增量序列的共同特征如下： 有人通過大量實驗給出了目前最好的結(jié)果：當(dāng)n較大時，比較和移動的次數(shù)大概在n^1.25到n^1.26之間。 2、Shell排序的時間性能優(yōu)于直接插入排序。 希爾排序的時間性能優(yōu)于直接排序的原因如下： 3、穩(wěn)定性 希爾排序是不穩(wěn)定的。 四、算法演練 假定待排序文件由10個記錄，其關(guān)鍵字分別是：40、38、65、97、76、13、27、49、55、04。 其動畫效果如下面的gif動畫所示： ps:讀者也可以自己打開下面的鏈接，自己設(shè)定要排序的數(shù)組，進(jìn)行排序演練 五、代碼實現(xiàn) 運行結(jié)果為： 發(fā)現(xiàn)增長序列是5,2,1 和題目要求的5,3,1不同。通過分析要排序的文件由10個記錄，10/2=5,5-2=3,3-2=1。剛好符合要求，因此將上面的代碼稍作修改即可改變增長序列的值。 將shellSort(int[] source) 方法里的下面這行代碼 for (int gap = source.length / 2; gap > 0; gap /= 2) { 如果想使用指定的增長序列來對指定的數(shù)組進(jìn)行希爾排序，可以對上面的程序修改，修改后代碼如下： 運行結(jié)果如下： 關(guān)于利用Java實現(xiàn)一個希爾排序的方法問題的解答就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，如果你還有很多疑惑沒有解開，可以關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道了解更多相關(guān)知識。void ShellPass(SeqList R，int d)
{//希爾排序中的一趟排序，d為當(dāng)前增量
for(i=d+1;i<=n；i++) //將R[d+1．．n]分別插入各組當(dāng)前的有序區(qū)
if(R[i].key
a.最后一個增量必須為1。
b.應(yīng)該盡量避免序列中的值(尤其是相鄰的值)互為倍數(shù)的情況。
a.當(dāng)文件初態(tài)基本有序時，直接插入排序所需的比較和移動次數(shù)均較少。
b.當(dāng)n值較小時，n和n^2的差別也較小，即直接插入排序的最好時間復(fù)雜度O(n)和最壞時間復(fù)雜度O(n^2)差別不大。
c.在希爾排序開始時增量較大，分組較多，每組記錄數(shù)目少，故每組內(nèi)直接插入排序較快，后來增量d(i)逐漸縮小，分組數(shù)逐漸減少，而各組的記錄數(shù)目逐漸增多，但由于已經(jīng)按d(i-1)做為距離拍過序，使文件較接近于有序狀態(tài)，所以新的一趟排序過程也較快。因此，希爾排序在效率上較直接插入排序有較大的改進(jìn)。
增量序列取值依次為：5、3、1
排序過程演示如下圖所示：
希爾排序動畫演示public class ShellSortTest {
private static void shellSort(int[] source) {
int j;
for (int gap = source.length / 2; gap > 0; gap /= 2) {
for (int i = gap; i < source.length; i++) {
int temp = source[i];
for (j = i; j >= gap && temp < source[j - gap]; j -= gap)
source[j] = source[j - gap];
source[j] = temp;
}
System.out.print("增長序列：" + gap + " :");
printArray(source);
}
}
private static void printArray(int[] source) {
for (int i = 0; i < source.length; i++) {
System.out.print("\t" + source[i]);
}
System.out.println();
}
public static void main(String[] args) {
int source[] = new int[] {49,38,65,97,76,13,27,49,55,04 };
System.out.print("原始序列：");
printArray(source);
System.out.println("");
shellSort(source);
System.out.print("\n\n最后結(jié)果：");
printArray(source);
}
}
原始序列： 49 38 65 97 76 13 27 49 55 4
增長序列：5 : 13 27 49 55 4 49 38 65 97 76
增長序列：2 : 4 27 13 49 38 55 49 65 97 76
增長序列：1 : 4 13 27 38 49 49 55 65 76 97
最后結(jié)果： 4 13 27 38 49 49 55 65 76 97
改為：
for (int gap = source.length / 2; gap > 0; gap -= 2) {
然后重新運行程序，打印結(jié)果如下：原始序列： 49 38 65 97 76 13 27 49 55 4
增長序列：5 : 13 27 49 55 4 49 38 65 97 76
增長序列：3 : 13 4 49 38 27 49 55 65 97 76
增長序列：1 : 4 13 27 38 49 49 55 65 76 97
最后結(jié)果： 4 13 27 38 49 49 55 65 76 97
public class ShellSortTest2 {
/**
* 待排序的數(shù)組
*/
private int[] sources;
/**
* 數(shù)組內(nèi)元素個數(shù)
*/
private int itemsNum;
/**
* 增量數(shù)組序列
*/
private int[] intervalSequence;
/**
* @param maxItems
* 數(shù)組大小
* @param intervalSequence
* 增量數(shù)組序列
*/
public ShellSortTest2(int[] source, int[] intervalSequence) {
this.sources = new int[source.length];
this.itemsNum = 0;// 還沒有元素
this.intervalSequence = intervalSequence;
}
/**
* 希爾排序算法
*/
public void shellSort() {
int gap = 0;// 為增量
for (int iIntervalLength = 0; iIntervalLength < intervalSequence.length; iIntervalLength++)// 最外層循環(huán)，由增量序列元素個數(shù)決定
{
gap = intervalSequence[iIntervalLength]; // 從增量數(shù)組序列取出相應(yīng)的增長序列
int innerArraySize;// 每次內(nèi)部插入排序的元素個數(shù)
if (0 == itemsNum % gap) {
innerArraySize = itemsNum / gap;
} else {
innerArraySize = itemsNum / gap + 1;
}
for (int i = 0; i < gap; i++) {
int temp = 0;
int out = 0, in = 0;
if (i + (innerArraySize - 1) * gap >= itemsNum) {
innerArraySize--;
}
// 內(nèi)部用插入排序
for (int j = 1; j < innerArraySize; j++) {
out = i + j * gap;
temp = sources[out];
in = out;
while (in > gap - 1 && sources[in - gap] > temp) {
sources[in] = sources[in - gap];
in = in - gap;
}
sources[in] = temp;
}
}
System.out.print("增長序列為: " + gap + " ");
this.displayArray();
}
}
/**
* 初始化待排序數(shù)組
*/
public void initArray(int[] array) {
for (int i = 0; i < array.length; i++) {
sources[i] = array[i];
}
itemsNum = array.length;
}
/**
* 顯示數(shù)組內(nèi)容
*/
public void displayArray() {
for (int i = 0; i < itemsNum; i++) {
System.out.print("\t" + sources[i] + " ");
}
System.out.println("\n");
}
public static void main(String[] args) {
int[] intervalSequence = { 5, 3, 1 };
int[] source = { 49, 38, 65, 97, 76, 13, 27, 49, 55, 04 };
ShellSortTest2 ss = new ShellSortTest2(source, intervalSequence);
// 初始化待排序數(shù)組
ss.initArray(source);
System.out.print("原始序列： ");
ss.displayArray();
// 希爾排序
ss.shellSort();
System.out.print("最后結(jié)果： ");
ss.displayArray();
}
}
原始序列： 49 38 65 97 76 13 27 49 55 4
增長序列為: 5 13 27 49 55 4 49 38 65 97 76
增長序列為: 3 13 4 49 38 27 49 55 65 97 76
增長序列為: 1 4 13 27 38 49 49 55 65 76 97
最后結(jié)果： 4 13 27 38 49 49 55 65 76 97
網(wǎng)頁標(biāo)題：利用Java實現(xiàn)一個希爾排序的方法
當(dāng)前鏈接：http://weahome.cn/article/ihiijs.html
重慶分公司
重慶分公司
