排序演算法之直接插入排序
lj就是lj，這個演算法花了很長時間才整明白，
話不多說直接看代碼：
public class Paixv {
public static void printArray(int[] num) {
for(int i : num) {
System.out.printf("%d\t", i);
}
System.out.println();
}
public static void main(String[] args)
{
int tmp=0;
int j=0;
int num[]= {6,5,1,2,0,8,7,9,3,4,10};//定義10個整數
for(int i=1;i<num.length;i++)//10次排序
{
if(num[i]<num[i-1])//如果發現后面一個數比前面數大
{
tmp=num[i];//用tmp存放num[i]
for (j=i-1;j>=0;j--)//在有序區中從反向找出tmp的合適位置，第一個被操作的數沒有有序區，第二個會出現，
{
if (tmp<num[j]) //發現有序區比tmp大的第一個數
{
num[j+1]=num[j];//為將num[i]插入其位置，把后面的元素向后移動一位
}
else
break;//移動完成，位置已經找出，停止比較，
}
num[j+1]=tmp;//插入元素
}
printArray(num);//演示每一步
}
for(int i=0;i<num.length;i++)
{
System.out.print(num[i]);
}
}
}
結果
5 6 1 2 0 8 7 9 3 4 10
1 5 6 2 0 8 7 9 3 4 10
1 2 5 6 0 8 7 9 3 4 10
0 1 2 5 6 8 7 9 3 4 10
0 1 2 5 6 8 7 9 3 4 10
0 1 2 5 6 7 8 9 3 4 10
0 1 2 5 6 7 8 9 3 4 10
0 1 2 3 5 6 7 8 9 4 10
0 1 2 3 4 5 6 7 8 9 10
0 1 2 3 4 5 6 7 8 9 10
0 1 2 3 4 5 6 7 8 9 10
演算法時間復雜度分析
最佳狀態為正序，進行了n-1次比較，時間復雜度為O（n），
平均狀態：把num[i]插入有序區，平均比較為i/2次，移動次數為i/2+2次（tmp交換兩次），共(n-1)(n+4)/2，時間復雜度為O（n^2）
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/168723.html
標籤：其他