插入排序演算法

⑴ 插入排序的演算法復雜度

如果目標是把n個元素的序列升序排列，那麼採用插入排序存在最好情況和最壞情況。最好情況就是，序列已經是升序排列了，在這種情況下，需要進行的比較操作需（n-1）次即可。最壞情況就是，序列是降序排列，那麼此時需要進行的比較共有n(n-1)/2次。插入排序的賦值操作是比較操作的次數加上 (n-1）次。平均來說插入排序演算法的時間復雜度為O(n^2）。因而，插入排序不適合對於數據量比較大的排序應用。但是，如果需要排序的數據量很小，例如，量級小於千，那麼插入排序還是一個不錯的選擇。

⑵ 編寫程序用直接插入排序的演算法進行排序。

#include<stdio.h>
#include<time.h>
#include<math.h>
#include<malloc.h>

void BubbleSort(int *L,int N)
{ //冒泡
int i,j;
int t;

for(i=1;i<=N;i++)
{
for(j=N;j>i;j--)
if(L[j]<L[j-1])
{
t=L[j];
L[j]=L[j-1];
L[j-1]=t;
}
}
}

int SelectMinKey(int *L,int N,int n)
{
int i,min=n;

for(i=n+1;i<=N;i++)
if(L[i]<L[min])
min=i;

return min;
}

void SelectSort(int *L,int N)
{ //選擇
int i,j;
int t;

for(i=1;i<N;i++)
{
j=SelectMinKey(L,N,i);
if(i!=j)
{
t=L[i];
L[i]=L[j];
L[j]=t;
}
}
}

void InsertSort(int *L,int N)
{ //插入
int i,j;

for(i=2;i<=N;i++)
{
if(L[i]<L[i-1])
{
L[0]=L[i];
L[i]=L[i-1];
for(j=i-2;L[0]<L[j];j--)
L[j+1]=L[j];
L[j+1]=L[0];
}
}
}

void ShellInsert(int *L,int N, int dk)
{ // 對順序表L作一趟希爾插入排序。本演算法對演算法10.1作了以下修改：
// 1. 前後記錄位置的增量是dk，而不是1；
// 2. r[0]只是暫存單元，不是哨兵。當j<=0時，插入位置已找到。
int i,j;
for(i=dk+1;i<=N;++i)
if(L[i]<L[i-dk])
{ // 需將L.r[i]插入有序增量子表
L[0]=L[i]; // 暫存在L.r[0]
for(j=i-dk;(j>0&&L[0]<L[j]);j-=dk)
L[j+dk]=L[j]; // 記錄後移，查找插入位置
L[j+dk]=L[0]; // 插入
}
} // ShellInsert

void ShellSt(int *L,int N, int dlta[], int t)
{ // 演算法10.5
// 按增量序列dlta[0..t-1]對順序表L作希爾排序。
for(int k=0;k<t;++k)
ShellInsert(L,N, dlta[k]); // 一趟增量為dlta[k]的插入排序
} // ShellSort

void ShellSort(int *L,int N)
{ //希爾
int t=(int)log(N);
int k,*dlta;

dlta=(int*)malloc(t*4); //產生增量序列
for(k=0;k<t;k++)
dlta[k]=(int)pow(2,t-k)-1;

ShellSt(L,N,dlta,t);
}

int main()
{
int N=250;
int i,j,k;
int t;
int ti[16];
int *L;

srand(time(NULL));

printf("長度\t|冒泡\t|選擇\t|插入\t|希爾\n");
printf("--------+-------------------------------------------------------------");
for(j=0;N<100000;j++)
{
L=(int *)malloc((N+1)*4);

t=0;

for(i=1;i<=N;i++)
L[i]=rand();
ti[t++]=clock();
BubbleSort(L,N);
ti[t++]=clock();

for(i=1;i<=N;i++)
L[i]=rand();
ti[t++]=clock();
SelectSort(L,N);
ti[t++]=clock();

for(i=1;i<=N;i++)
L[i]=rand();
ti[t++]=clock();
InsertSort(L,N);
ti[t++]=clock();

for(i=1;i<=N;i++)
L[i]=rand();
ti[t++]=clock();
ShellSort(L,N);
ti[t++]=clock();

printf("\n%d\t",N);
for(k=0;k<4;k++)
printf("| %d\t",(ti[2*k+1]-ti[2*k]));

N*=5;
}
printf("\n\n");
}

//這是我們當年學數據結構時我自己寫的，給你改了一下，輸出是對隨機產生一些數，對四種演算法進行比較，有問題可以hi我啊

⑶ 插入排序演算法在最壞情況下最多的比較次數是

第i個數與前i-1個數繼續比較，最壞一共比較i-1次。最後還會與最前面設置的哨兵比較一次，加上1。
所以第i個數比較i次。從i=2的位置開始求和。
最後結果是b

⑷ VB插入排序演算法

Option Explicit

Private Sub Form_Load()
Dim i As Integer, intC As Integer
Dim IntOuSus() As String, strOuSus As String
Dim IntJiSus() As String, strJiSus As String

Randomize
For i = 1 To 30
intC = CInt(Rnd * 90) + 10
If intC Mod 2 = 1 Then
strJiSus = strJiSus & IIf(strJiSus = "", "", ",") & intC
Else
strOuSus = strOuSus & IIf(strOuSus = "", "", ",") & intC
End If
Next
IntOuSus = Split(strOuSus, ",")
IntJiSus = Split(strJiSus, ",")

OrderNumbers IntJiSus, "ASC"
OrderNumbers IntOuSus, "DESC"

End Sub

'注意以下過程中第一個參數使用了ByRef
'此方法比傳統的冒泡法快得多
Private Sub OrderNumbers(ByRef a() As String, Optional ByVal ASCDESC As String = "ASC")
Dim min As Long, max As Long, num As Long, first As Long, last As Long, temp As Long, all As New Collection, steps As Long
ASCDESC = UCase(ASCDESC)
min = LBound(a)
max = UBound(a)
all.Add a(min)
steps = 1
For num = min + 1 To max
last = all.Count
If a(num) < CDbl(all(1)) Then all.Add a(num), BEFORE:=1: GoTo nextnum '加到第一項
If a(num) > CDbl(all(last)) Then all.Add a(num), AFTER:=last: GoTo nextnum '加到最後一項

first = 1
Do While last > first + 1 '利用DO循環減少循環次數
temp = (last + first) \ 2
If a(num) > CDbl(all(temp)) Then
first = temp
Else
last = temp
steps = steps + 1
End If
Loop
all.Add a(num), BEFORE:=last '加到指定的索引

nextnum:
steps = steps + 1
Next
For num = min To max
If ASCDESC = "ASC" Then a(num) = CDbl(all(num - min + 1)): steps = steps + 1 '升序
If ASCDESC = "DESC" Then a(num) = CDbl(all(max - num + 1)): steps = steps + 1 '降序
Next
'MsgBox "本數組共經過 " & steps & "步實現" & IIf(ASCDESC = "ASC", "升序", "降序") & "排序！", 64, "INFORMATION"
Set all = Nothing
End Sub

⑸ 插入排序法是什麼

排序
排序(Sorting)的基本功能是依某種條件將資料項目按順序排列,例如依照數字的大小由
小至大排列,或是按筆畫順序排列姓名 .
插入排序法 :
所謂插入排序法乃是將一個數目插入該占據的位置.假設我們輸入的是
5,1,4,2,3
我們從第二個數字開始,這個數字是1,我們的任務只要看看1有沒有正確的位置,我
們的做法是和這個數字左邊的數字來比,因此我們比較1和5,1比5小,所以我們就交
換1和5,原來的排列就變成了
1,5,4,2,3
接下來,我們看第3個數字有沒有在正確的位置.這個數字是4,它的左邊數字是5,4
比5小,所以我們將4和5交換,排列變成了
1,4,5,2,3
我們必須繼續看4有沒有在正確的位置,4的左邊是1,1比4小,4就維持不動了.
再來看第四個數字,這個數字是2,我們將2和它左邊的數字相比,都比2大,所以就
將2一路往左移動,一直移到2的左邊是1,這時候排序變成了
1,2,4,5,3
最後,我們檢查第五個數字,這個數字是3,3必須往左移,一直移到3的左邊是2為止,
所以我們的排列就變成了
1,2,3,4,5
排序因此完成了.
所謂插入排序法,就是檢查第i個數字,如果在它的左邊的數字比它大,進行交換,這
個動作一直繼續下去,直到這個數字的左邊數字比它還要小,就可以停止了.
插入排序法主要的迴圈有兩個變數:i和j,每一次執行這個迴圈,就會將第i個數字放
到左邊恰當的位置去.

時間復雜度： O(n的平方)

⑹ 插入排序的演算法

排序演算法在編程領域中起著舉足輕重的作用，在目標檢索、機器學習、數值計算、圖像處理等領域有著廣泛地應用。為了追本溯源，公眾號特推出常用經典排序演算法系列推文，讓小夥伴們深入了解排序演算法的實現原理，同時也提升matlab編程能力。
插入排序演算法，它是將無序序列分成兩部分，一部分為假設已經排列完成的序列，另一部分為餘下序列，將餘下序列中的元素取出插入到已排列完成的序列中，依次比較確定插入位置，下面就一起來看看該算的實現原理吧。
插入排序演算法實現過程(以升序排列為例)：
對於長度為N的無序數組A，假定序列A(1)為排列完成的序列K，將A(2)與A(1)作比較，如果A(2)<A(1)，則兩者交換，否則保持不變，即完成序列K的元素添加；將A(3)與A(2)比較，如果A(2)<A(3)，則保持不變，否則兩者交換，繼續將A(3)與A(1)比較，如果A(3)>A(1)，則兩者交換，否則保持不變；以此類推，將餘下序列中的元素取出插入到序列K中，從序列K尾部往首部進行比較，直至完成所有元素的插入。

matlab代碼
主程序：main.m

format short;
clc;clear;
A = round(rand(1,8),2);
nA = InsertSort(A);
disp(['原始序列：',num2str(A)]);
disp(['插入排序：',num2str(nA)]);
插入排序函數：InsertSort.m

function A = InsertSort(A)
% 感謝關註：matlab愛好者
% 插入排序演算法源代碼
% 作者：matlab愛好者

len = length(A);
for w = 1:len-1
% 從餘下序列中取出一個元素插入到新序列中
for v = w+1:-1:2
if(A(v)<A(v-1))
% 如果新元素小於所插入位置的元素，則交換
tmp = A(v-1);
A(v-1) = A(v);
A(v) = tmp;
else
% 否則保持位置不變
break;
end
end
end

⑺ C語言的插入排序法是什麼

插入排序(insertion sort)

如果需要對一個小型數組進行升序排列，那麼可以選用插入排序，插入排序可以用打牌時對摸起的牌根據牌的點數來對其進行插入排列來描述。

可以把左手中的牌比做已經摸起的牌，即已經被排列好的牌，左手可以容納的牌數的空間可以假想為和要摸的牌的總數相同；而在桌子上的那部分沒摸的牌則是未被排序的牌，這二者的關系可以抽象為數組中已經被排序好的部分和未被排序好的部分。

一開始摸起的第一張牌不需要排序，可以認定其為已排序的牌。

如果用外層循環for來表示摸起的牌的話，則可以抽象為：

// 對象數組

// 桌子上的牌

int A[] = {5,1,3,6,2,4};

// 從數組的第二個元素開始抽取

for(int i = 1; i < sizeof A/sizeof A[0]; ++i)

{

int pick = A[i]; // 被摸起的牌

int j = i - 1; // j記錄已排序部分的最後一張牌的位置

. . .

}

而後摸起的排要根據排列策略和先前摸起的牌的點數的大小來確定其插入的合適位置，這里示範的排列策略是升序排列，摸起了這張牌後，便自右向左地和手中的牌進行比較。

把pick稱作摸起的牌，如果pick比手中的牌小，則手中較大的那張牌就向右挪一位，pick再和下一張牌做比較，如果下一張牌仍然比pick大，那麼那張牌便也向右移動一個位置，依此類推。

如果手中下一張和pick比較的牌比pick小，那麼pick就被插入在了手中前一張牌移動後空下的位置；

或者手中所有的牌都比pick大，那麼所有的牌就都向右移動過一個位置，所以pick最終被插入在了手中最左邊的位置。

這個過程可以抽象為：

// 對象數組

// 桌子上的牌

int A[] = {5,1,3,6,2,4};

// 從數組的第二個元素開始抽取

for(int i = 1; i < sizeof A/sizeof A[0]; ++i)

{

int pick = A[i]; // 被摸起的牌

int j = i - 1; // j記錄已排序部分的最後一張牌的位置

// 如果循環了j+1次，即j = -1時還未找到比pick小的牌

// 那麼pick就是最小的牌被插入在位置A[0]處

// A[j]是當前手中和pick進行比較的牌

while(j >= 0 && A[j] > pick)

{

// 未找到可插入位置，則A[j]向後挪一位

A[j+1] = A[j];

// j減1繼續向左定位手中下一張供和pick比較的牌--j;

}


// while結束後，j+1所表達的位置便是pick可以插入的位置

A[j+1] = pick;

}

// 對於有N個元素的數組A，採用插入排序法排序時，當外層循環進行了N-1次後排序完畢

⑻ java插入排序演算法

import java.util.Arrays;
public class Insert {
public static void main(String[] args) {
int[] ary={8,3,7,1,9,4};
selectionSort(ary);
System.out.println(Arrays.toString(ary));
}
public static void selectionSort(int[] ary) {
int i,j,t;
for(i=1;i<ary.length;i++){
t=ary[i];
for(j=i-1;j>=0&&t<ary[j];j--){
ary[j+1]=ary[j];
}ary[j+1]=t;
}
}
}

插入演算法的原理是當要被插入的數比數組中元素小就放在他的前面，加了一個中間變數t，把數組元素先放那存著。如果成功插入就把插入數據放到對應的數組位置。然後下一個繼續先放在t裡面存著。直到最後一個數