您好,登錄后才能下訂單哦!
這篇文章給大家分享的是有關(guān)Java中插入排序算法之希爾排序+直接插入排序的示例分析的內(nèi)容。小編覺得挺實用的,因此分享給大家做個參考,一起跟隨小編過來看看吧。
在介紹希爾排序之前,先了解一下直接插入排序
x
插入一個有序區(qū)間
這里end
是指向數(shù)組最后一個元素
根據(jù)上面的單趟排序啟發(fā)
end是數(shù)組的最后一個元素,end之后的元素都是待排序
一個關(guān)鍵的判斷點,end和x比較大小
這里end < x
還需要再做改善
可以發(fā)現(xiàn)有兩個循環(huán),一個循環(huán)時end
倒著遍歷完之后,使得最開始的end
結(jié)束的數(shù)組加入x
后是一個有序數(shù)組,最后再返回這個新數(shù)組的最后一個元素所在位置
注意公共部分
end--; x = a[end + 1];
外面是一個for
循環(huán),從第二個到最后一個元素
for(i = 0; i < n - 1; i++) { }
代碼:
//插入排序 void InsetSort(int* a, int n) { int end = 0; int i = 0; for (i = 0; i < n - 1; i++) { end = i; int x = a[end + 1]; while (end >= 0) { if (a[end] > x) { a[end + 1] = a[end]; a[end] = x; } else { break; } end--; } } }
時間復(fù)雜度O(N2)
測試:
int main() { int a[4] = { 2, 6, 5, 3 }; InsetSort(a, 4); //ShellSort(a, 4); int i = 0; for (i = 0; i < 4; i++) { printf("%d ", a[i]); } printf("\n"); return 0; }
希爾排序法又稱縮小增量法
希爾排序法的基本思想是:先選定一個整數(shù),把待排序文件中所有記錄分成
gap
個組,所有距離為的記錄分在同一組內(nèi),并對每一組內(nèi)的記錄進行排序。然后,重復(fù)上述分組和排序的工作。當(dāng)?shù)竭_gap=1
時,所有記錄在統(tǒng)一組內(nèi)排好序。
希爾排序是根據(jù)直接插入排序的基礎(chǔ)上,先進行分組排序
以3
個為一組進行排序
時間復(fù)雜度:
每次排可以看作長度為gap
的數(shù)組直接插入排序
一共有gap
組,當(dāng)然并不是每組都是gap/n
個元素,但當(dāng)數(shù)據(jù)相當(dāng)多的時候我們看作每個數(shù)組都有gap/n
個元素
所以是 (1+2……+n/gap)gap
如果gap = 1,則時間復(fù)雜度是O(n2),相當(dāng)于直接插入排序
//希爾排序 void ShellSort(int* a, int n) { int end = 0; int i = 0; int j = 0; int gap = 6; //預(yù)排序 for (j = 0; j < gap; j++) { //最后一個數(shù)一定是1 gap = gap / 2; for (i = 0; i < n - gap; i++) { end = i; //這里其實就是直接插入排序,而數(shù)組的每個元素間隔是gap int x = a[end + gap]; while (end >= 0) { if (a[end] > x) { a[end + gap] = a[end]; a[end] = x; } else { break; } end -= gap; } } } }
測試用例還是上面直接插入排序的例子
結(jié)果還是成功的
//性能測試 void TestOP() { srand(time(0)); //以1000個數(shù)字為例 const int N = 10000; int* a1 = (int*)malloc(sizeof(int) * N); int* a2 = (int*)malloc(sizeof(int) * N); for (int i = 0; i < N; ++i) { a1[i] = rand(); a2[i] = a1[i]; } //這里clock是運行到這里的時間 int begin1 = clock(); InsertSort(a1, N); int end1 = clock(); int begin2 = clock(); ShellSort(a2, N); int end2 = clock(); //end-begin為排序所用時間 printf("%d\n%d\n", end1 - begin1, end2 - begin2); }
可以看出希爾排序比直接排序快得多,但希爾排序因為gap可以改變,目前沒有一個統(tǒng)一的時間復(fù)雜度,先按照時間復(fù)雜度為O(n1.3)來吧
感謝各位的閱讀!關(guān)于“Java中插入排序算法之希爾排序+直接插入排序的示例分析”這篇文章就分享到這里了,希望以上內(nèi)容可以對大家有一定的幫助,讓大家可以學(xué)到更多知識,如果覺得文章不錯,可以把它分享出去讓更多的人看到吧!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。