文章目錄
-
目錄
前言
一、什么是插入排序
1.直接插入排序
2.折半插入排序
? ? ? ? ?3.希爾排序
總結(jié)
前言
理解三種排序，并將三種排序用C++實(shí)現(xiàn)，借鑒了王卓老師和沒有難學(xué)的知識(shí)的圖例
提示：以下是本篇文章正文內(nèi)容，下面案例可供參考
一、什么是插入排序
? ? ? ? 插入排序是簡單直觀的排序方法，其思想是每次將一個(gè)待排序的記錄按其關(guān)鍵字大小插入前面已排好序的子序列，直到全部記錄插入完成。用我的話翻譯過來就是：一組數(shù)據(jù)有一部分是已經(jīng)排好序的，只需要將混亂的部分按照排列好的大小順序挨個(gè)插入到前面已經(jīng)排好順序序列里面，使全部數(shù)據(jù)按順序排列。類似與整理撲克牌的大小順序。
1.直接插入排序
? ? 方法1：默認(rèn)第一個(gè)數(shù)是已經(jīng)排好序的，從第二個(gè)數(shù)開始，與前一位作比較，找到適合插入的有序位置后，將有序位置及其后面的位置的數(shù)值都往后移一位，空出要插入的有序位置，把待排序的的數(shù)再復(fù)制給該位置即可，往后依次相同做法。
插入位置有以下3種：
? ? ?
?舉個(gè)例子更好地理解：
?（1）? a數(shù)組中，0-3的位置是已經(jīng)從小到大排好序的，那么從第4個(gè)位置開始排，也就是第i位，j是第i位的前一位，用來記錄有序位的。
?（2）復(fù)制插入元素，將要進(jìn)行插入排序的數(shù)復(fù)制給x:
? (3)記錄后移，查找插入位置，將7與前一位16相比，7<16,應(yīng)該在16的前面，16往后移，往前繼續(xù)找，j-1;
? ? ? 將7與10相比，7<10,應(yīng)該在10的前面，16往后移，往前繼續(xù)找，j-1；
?
? ? ?7和5相比，7>5，所以該在5的后面，所以要插入的有序位是j+1;
?代碼如下（示例）：
#include<iostream>
using namespace std;
const int N = 100001;
int arr[N];
int main()
{
int n = 5;
int x;
for (int i = 0; i < n; i++)
{
cin >> arr[i]; //輸入數(shù)據(jù)
}
for (int i = 1; i < n; i++) //除了第一個(gè)數(shù)不用管，要排n-1次序
{
if (arr[i] < arr[i - 1]) //如果待排序數(shù)（指：將要進(jìn)行排序的數(shù)，注意連讀嗷） 比前一位小，進(jìn)行后移和插入操作；否則，不變，開始下一位待排數(shù)
{
int j;
x = arr[i]; //用一個(gè)中間變量來暫時(shí)存放待排序數(shù)
for (int j = i - 1; j >= 0 && x < arr[j]; j--) //后移操作：從后位開始往后移，所以從j=i-1開始,依次往前j--
{
arr[j + 1] = arr[j]; //后移核心：把前一位的值復(fù)制給后一位
}
arr[j + 1] = x; //插入
}
}
for (int i = 0; i < n; i++) cout << arr[i] << ' ';
return 0;
}這個(gè)方法中每次循環(huán)都要比較兩次條件，運(yùn)行起來耗時(shí)過多，而且每次都要判斷下標(biāo)是否越界，下面的方法可以避免邊界問題。
方法2：和方法1差不多，存數(shù)據(jù)時(shí)，從下標(biāo)為1開始，下標(biāo)為0的位置作為哨兵，上面第（2）步里的復(fù)制轉(zhuǎn)變?yōu)椋喊巡迦肱判虻臄?shù)賦值給哨兵。
（1）將下標(biāo)為0的位置作為哨兵，當(dāng)?shù)趇位的數(shù)小于i-1位的數(shù)時(shí)，把第i位的數(shù)存放在哨兵上
?（2）記錄后移，查找插入位置，將哨兵的值與前一位16相比，7<16,應(yīng)該在16的前面，16往后移，往前繼續(xù)找，j-1;
?
? ? ?將7與10相比，7<10,應(yīng)該在10的前面，16往后移，往前繼續(xù)找，j-1；
?
?7和5相比，7>5，所以該在5的后面，所以要插入的有序位是j+1;
?
代碼如下（示例）：文章來源：http://www.zghlxwxcb.cn/news/detail-761348.html
#include<iostream>
using namespace std;
const int N = 100001;
int arr[N];
int main()
{
int n = 12;
for (int i = 1; i <= n; i++)
cin>>arr[i];
int i, j;
for ( int i = 2; i <= n; i++) //第0位的是哨兵位，假設(shè)第一位是有序的，從第二位開始比較大小，直到最后一位
{
if (arr[i] < arr[i - 1])
{
arr[0] = arr[i]; //如果第二位的數(shù)比第一位大，就把第二位的數(shù)值賦給哨兵位0位
for (j = i - 1; arr[0]< arr[j]; j--) //j是要待排序的前一位，當(dāng)前一位比待排序位的值大，那么j--,繼續(xù)向前找待排序位的值小的
{
arr[j + 1] = arr[j];
}
arr[j + 1] = arr[0]; //找到之后，在比待排序位小的那位后面插入待排序位，也就是哨兵位
}
}
for (int i = 1; i <= n; i++) //輸出
cout << arr[i] << ' ';
return 0;
}
2.折半插入排序
在已經(jīng)排好序的部分中去插入待排序的數(shù)，有點(diǎn)二分查找那意思，把待插入排序的數(shù)和排好序的中間位置的數(shù)作比較，就可以在原來一半的范圍里繼續(xù)比較，再縮小一半的范圍...直到找到插入的有序位。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（1）從第i位插入，下標(biāo)為0的是哨兵，低位left是下標(biāo)位1的位置，高位right是待排序的位前一位i-1，中間位是mid=(left+right)/2=（1+4）/ 2=2,7>mid,7在mid的右半邊找插入位置
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
?（2）此時(shí)低位變?yōu)閘eft=mid+1=3,中間位相應(yīng)改變mid=(left+right)/2=(3+4)/2=3,7<mid,7在mid的左半邊找插入位置
?（3）此時(shí)高位變?yōu)閞ight=mid-1=2,left>right，那么7應(yīng)該在下標(biāo)為3處，即第right+1位
（4） 找到插入位置后，開始后移步驟，把第right+1位及其后面的位向后移，空出right+1，將哨兵的值給right+1,就這樣排到最后一位。
?代碼如下（示例）：
#include<iostream>
using namespace std;
const int N = 10010;
int arr[N];
int main()
{
int n;
cin >> n; //n個(gè)數(shù)
for (int i = 1; i <= n; i++) //輸入要排列的數(shù)據(jù)
cin>>arr[i];
for (int i=2;i<=n;i++) //從第2的數(shù)開始排列，直到最后一個(gè)
{
int j;
arr[0] = arr[i]; //把待排列的數(shù)給哨兵位arr[0]
int left = 1, right = i - 1; //二分的三個(gè)位置，左邊：第1位，右邊待排序前的一位，中間位
while (left <= right)
{
int mid = (left + right) / 2; //注意：該語句寫while外面的話，while里面將會(huì)一直循環(huán)
if (arr[0] < arr[mid]) left = mid + 1;
else right = mid - 1;
}
//待排序的數(shù)最后的位置一定是在right+1上，所以要把right+1這個(gè)位置空出來，就要把right+1及其后面的位置上的數(shù)據(jù)往后移
for (int j = i - 1; j >= right + 1; j--)
arr[j + 1] = arr[j];
arr[right+1] = arr[0]; //最后將哨兵位置上的數(shù)賦值到right+1位置上
}
for (int i = 1; i <= n; i++)
cout << arr[i] << ' ';
return 0;
}3.希爾排序
????????基本思想:先將整個(gè)待排記錄序列分割成若干子序列，分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄“基本有序”時(shí)，再對(duì)全體記錄進(jìn)行一次直接插入排序。簡言之，縮小增量，多遍插入排序，增量下一次是上一次的一半，增量是來表示分組的數(shù)量，最后一次增量必須為1
（1）第一次，以8/2=4為增量grap，分為4組，將7和2? 3和0 5和8 9和6這四組分別進(jìn)行插入排序
（2） 排好后，增量grap變?yōu)?/2=2,?分為2和5和7和8、0和6和3和9這兩組分別進(jìn)行插入排序
?（3）排好后，grap=2/2=1,即全部進(jìn)行插入排序
? ? ? ? 最后得到
運(yùn)行代碼直接插入邏輯相同，再多一個(gè)增量變換的循環(huán)，別的幾處值與增量有關(guān)
代碼如下（示例）：
#include<iostream>
using namespace std;
const int N = 10010;
int arr[N];
int main()
{
int n = 10;
for (int i = 1; i <= n; i++)
cin >> arr[i]; //輸入10個(gè)數(shù)
for (int gap=n/2;gap>0;gap=gap/2) //增量
{
for (int i = gap + 1; i <= n; i++) //從相隔步長數(shù)的作比較 比如：下標(biāo)1和下標(biāo)6之間相隔5
{
if (arr[i] < arr[i - gap]) //第i位比相差增量位的數(shù)小的話
{
int j;
arr[0] = arr[i]; //，就把值給哨兵
for ( j = i - gap; j > 0 && arr[0] < arr[j]; j -= gap) //這里多一個(gè)j>0的條件，保證每次比較都是在邊界內(nèi)的值
arr[j + gap] = arr[j]; //往后移
arr[j + gap] = arr[0]; //找到合適的插入有序位就把哨兵的數(shù)給第j+dk位
}
}
}
for (int i = 1; i <= n; i++)
cout << arr[i]<<' '; //輸出
return 0;
}總結(jié)
從上可得，插入排序的要點(diǎn)：1.存：把待排序的數(shù)暫存到一個(gè)新的位置，也可以是哨兵；2.找：找插入位置；3.移：把插入位置及其后面的位置上的數(shù)往后移一位?以上就是今天要講的內(nèi)容，隨后還會(huì)更新排序的相關(guān)內(nèi)容，希望可以幫助到你~文章來源地址http://www.zghlxwxcb.cn/news/detail-761348.html
到了這里，關(guān)于數(shù)據(jù)結(jié)與算法之排序-插入排序（直接插入/折半插入/希爾）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
