溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章主要介紹“Java數據結構之插入排序與希爾排序怎么實現”，在日常操作中，相信很多人在Java數據結構之插入排序與希爾排序怎么實現問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”Java數據結構之插入排序與希爾排序怎么實現”的疑惑有所幫助！接下來，請跟著小編一起來學習吧！
排序：所謂排序，就是使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減的排列起來的操作。
穩定性：假定在待排序的記錄序列中，存在多個具有相同的關鍵字的記錄，若經過排序，這些記錄的相對次 序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，則稱這種排 序算法是穩定的；否則稱為不穩定的。
內部排序：數據元素全部放在內存中的排序。
外部排序：數據元素太多不能同時放在內存中，根據排序過程的要求不能在內外存之間移動數據的排序。
看過排序的基礎概念，可能有的小伙伴會問就算我學會了排序，但是在實際生活中有什么用嗎？其實排序在生活中無處不在，比如說對一件商品不同維度的選擇，又或者是對高校的排名，其實背后都存在著排序的思想，學好排序，能夠幫助我們以另一種維度來觀察生活中的方方面面并幫助我們更好地解決生活中的問題。
在數據結構這一塊，我們常見的排序算法共有四種：
①插入排序：直接插入排序、希爾排序
②選擇排序：選擇排序、堆排序
③交換排序：冒泡排序、快速排序
④歸并排序：歸并排序
由于篇幅的關系，本篇我們主要介紹的是插入排序中的直接插入排序和希爾排序，而直接插入排序又常常被稱為插入排序。
2.1.1基本思想
直接插入排序是一種簡單的插入排序法
其基本思想是把待排序的記錄按其關鍵碼值的大小逐個插入到一個已經排好序的有序序列中，直到所有的記錄插入完為止，得到一個新的有序序列
實際中我們玩撲克牌時，就用了插入排序的思想。當你摸了一張新牌，自然而然地就會與手上已有的牌堆進行一一比較，在比較之后將其放入其應該所處的位置。所以我們可能并不知道插入排序是什么，但我們潛意識的做法恰恰就符合了插入排序。
2.1.2直接插入排序
用比較書面的語言來描述直接插入排序：當插入第i(i>=1)個元素時，前面的 array[0],array[1],…,array[i-1]已經排好序，此時用array[i]的排序碼與 array[i-1],array[i-2],…的排序碼順序進行比較，找到插入位置即將array[i]插入，原來位置上的元素順序后移
但這么說可能有的小伙伴會不太理解，那么通俗地來講吧。現在在你面前有一個亂序的數組，我們的目的是要將這個亂序的數組調整為升序或者降序。
以升序為例叭，由于數組是無序的，因此我們需要從數組的第二個元素開始排序。為什么不是第一個呢，因為只有一個數字的的時候，你無法與其余元素比較，自然也就沒有亂序一說，因此只有一個元素的時候我們就默認它是有序的。
在理解完為什么要從第二個元素開始排序后，現在我們就要進行元素的依次插入和排序了。先是第二個元素的插入和排序，在下圖中我們會發現第二個元素是44，44大于第一個元素3，因此不需要挪動第二個元素。緊接著就是第三個元素的插入和排序，我們發現第三個元素38小于第二個元素44，不符合我們升序的預期，因此將44挪動到38的位置，在第二、三個元素有序后，我們發現38大于3，也就是第一、二個元素也是有序的，因此就無需再挪動第一個元素的位置，這時候我們已經確認38應該所處的是數組中第二個元素的位置，因此我們只需將38插入到第二個元素的位置即可。相信看到這里的小伙伴對后續元素的插入與排序應該是信手拈來了，
接下來就是代碼的書寫了。在代碼上，我們該如何實現上述元素的插入與排序呢？我們采取了兩個主要的變量“des”和“end”，des就是我們所要插入的元素的初識下標，而end代表的是插入之前的序列的最后一個元素的下標，隨著des的比較，end要不斷向前移動，那么什么時候end的移動才會停止呢，也就是比較的結束，大致分為兩種情況：①des所代表的元素大于end所代表的的元素 ②end已經來到序列的第一個元素，這時候des要么是第一個元素，或者是第二個元素。
具體圖片和代碼如下：
//插入排序[升序]
int* InsertSort(int* arr, int n)
{
//整體排序
for (int i = 1; i < n; i++)
{
int end = i - 1;
int des = arr[i];
//單趟排序
while (end >= 0)
{
if (des >= arr[end])
break;
if (des < arr[end])
{
arr[end + 1] = arr[end];
end--;
}
arr[end+1] = des;
}
}
}注：直接插入排序特性總結
①元素集合越接近有序，直接插入排序算法的時間效率越高
②時間復雜度：O(N^2)
③ 空間復雜度：O(1)，它是一種穩定的排序算法
④ 穩定性：穩定
2.1.3希爾排序（縮小增量排序）
希爾排序法又稱縮小增量法。
希爾排序法的基本思想是：先選定一個整數，把待排序文件中所有記錄分成整數個組，所有距離為的記錄分在同一組內，并對每一組內的記錄進行排序。然后重復上述分組和排序的工作，當到達整數等于1時，所有記錄在統一組內排好序。
通俗來講，希爾排序就是多次的直接插入排序，不過除了最后一次直接插入排序之外的排序又和原本的直接插入排序有所不同。那么有的小伙伴看到這里可能就會問了為什么要進行多次的插入排序，單次的插入排序又和正常的插入排序不同在哪里呢？別著急，下面我們一個個回答。
先是為什么要多次的插入排序，看過上面對于插入排序的特性總結我們會發現，當元素的集合越接近有序，那么對其進行插入排序的時間效率就越高。因此希爾排序除了最后一次的排序是正常的插入排序之外的多次插入排序的目的就是不斷的調整這個元素的集合，使其不斷的接近有序。
緊接著就是希爾排序除最后一次插入排序之外的插入排序與正常插入排序的差異。通過上面對插入排序的學習，我們會發現對于一個亂序的數組的來說，一個元素若想來到正確的位置必須要與其余元素一一比較，也就是一步步的挪動，這種挪動在數組元素個數少的情況下尚可，但當這個數組的元素個數很多的時候，以升序來說，想象這個數組內最大的元素位于數組的第一個位置，那么是不是就要將這個元素與數組內其余元素一一比較以后，才能來到數組的最后一個位置，但當我們加大比較的步伐，也就是增大相比較的兩個元素之間的距離，那么這個元素是不是就可以更快的來到它應該所處的位置。放置于飛行棋的情境之下，插入排序每次都擲出1，而哈希排序除了最后一次的插入排序擲出的點數是1，其余的插入排序所擲出的點數是都是大于1的，所以可想而知，哈希排序能夠更快的到達排序的終點。
為了方便小伙伴們的理解，這部分代碼共分為兩部分：①固定步伐的直接插入排序②哈希排序。
先是固定步伐的直接插入排序，先讓我們通過圖片來直觀的看到數組數組內的元素通過這種操作后的變化。
//固定步伐的直接插入排序[升序]
void ShellSort(int* arr, int n)
{
int gap = 3;
int end;
//有兩種寫法，看你要控制end，還是des
/*for (int i=0; i < n-gap; i++)
{
int end = i;
int des = arr[end + gap];
while (end >= 0)
{
if (des >= arr[end])
break;
if (des < arr[end])
{
arr[end + gap] = arr[end];
end -= gap;
}
arr[end + gap] = des;
}
}*/
for (int i = gap; i < n ; i++)
{
int end = i-gap;
int des = arr[end + gap];
while (end >= 0)
{
if (des >= arr[end])
break;
if (des < arr[end])
{
arr[end + gap] = arr[end];
end -= gap;
}
arr[end + gap] = des;
}
}
}接著就是希爾排序
上述的代碼是gap=3的情況下的直接插入排序，那么對于希爾排序而言，我們該對gap該如何選擇呢？對于不同gap值的插入排序來說，我們會發現：gap越大，元素跳得越快，數組越不接近有序；而gap越小，元素跳的越慢，數組越接近有序。由于數組的大小不定，因此希爾排序也沒有一個合適gap值適用于所有數組，顯然，這個gap值一定是動態變化的。
對于gap的動態變化，常見的有兩種：
①令gap等于數組的元素個數，每次插入排序后令gap除等2
②另一種則是令gap等于數組的元素個數，不過每次插入排序后令gap除以3再加1
無論哪種處理都能使gap動態變化并最后等于1，對數組進行一次插入排序，達到最后想要的效果。
代碼如下：
//希爾排序
void ShellSortPlus(int* arr, int n)
{
int gap=n;
int end;
while (gap > 1)
{
gap = gap / 2;
for (int i=0; i < n - gap;i++)//有兩種寫法，看你要控制end，還是des
{
int end = i;
int des = arr[end + gap];
while (end >= 0)
{
if (des >= arr[end])
break;
if (des < arr[end])
{
arr[end + gap] = arr[end];
end -= gap;
}
arr[end + gap] = des;
}
}
}
}為了方便小伙伴們測試排序后的效果，為大家提供了測試的代碼并包含排序的具體代碼和包含的頭文件。
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
//插入排序[升序]
int* InsertSort(int* arr, int n)
{
//整體排序
for (int i = 1; i < n; i++)
{
int end = i - 1;
int des = arr[i];
//單趟排序
while (end >= 0)
{
if (des >= arr[end])
break;
if (des < arr[end])
{
arr[end + 1] = arr[end];
end--;
}
arr[end+1] = des;
}
}
}
//固定步伐的直接插入排序[升序]
void ShellSort(int* arr, int n)
{
int gap = 3;
int end;
//有兩種寫法，看你要控制end，還是des
/*for (int i=0; i < n-gap; i++)
{
int end = i;
int des = arr[end + gap];
while (end >= 0)
{
if (des >= arr[end])
break;
if (des < arr[end])
{
arr[end + gap] = arr[end];
end -= gap;
}
arr[end + gap] = des;
}
}*/
for (int i = gap; i < n ; i++)
{
int end = i-gap;
int des = arr[end + gap];
while (end >= 0)
{
if (des >= arr[end])
break;
if (des < arr[end])
{
arr[end + gap] = arr[end];
end -= gap;
}
arr[end + gap] = des;
}
}
}
//希爾排序
void ShellSortPlus(int* arr, int n)
{
int gap=n;
int end;
while (gap > 1)
{
gap = gap / 2;
for (int i=0; i < n - gap;i++)//有兩種寫法，看你要控制end，還是des
{
int end = i;
int des = arr[end + gap];
while (end >= 0)
{
if (des >= arr[end])
break;
if (des < arr[end])
{
arr[end + gap] = arr[end];
end -= gap;
}
arr[end + gap] = des;
}
}
}
}
//打印排序好的數組
void PrintSort(int*arr,int n)
{
for(int i=0;i<n;i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
//測試插入排序
void Text1()
{
int arr[10] = { 25,14,8,7,18,24,16,57,98,105 };
InsertSort(arr, sizeof(arr) / sizeof(arr[0]));
PrintSort(arr, sizeof(arr) / sizeof(arr[0]));
}
//測試固定步伐的插入排序
void Text2()
{
int arr[10] = { 9,1,2,5,7,4,8,6,3,5};
ShellSort(arr, sizeof(arr) / sizeof(arr[0]));
PrintSort(arr, sizeof(arr) / sizeof(arr[0]));
}
//測試希爾排序
void Text3()
{
int arr[10] = { 9,1,2,5,7,4,8,6,3,5 };
ShellSortPlus(arr, sizeof(arr) / sizeof(arr[0]));
PrintSort(arr, sizeof(arr) / sizeof(arr[0]));
}
int main()
{
//Text1();
Text2();
//Text3();
return 0;
}到此，關于“Java數據結構之插入排序與希爾排序怎么實現”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注億速云網站，小編會繼續努力為大家帶來更多實用的文章！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
