演算法描述
在本節中，我們考慮如何用減-技術對-一個陣列A[..n- 1]排序，遵循該方法的思路，
我們假設對較小陣列A[0..n - 2]排序的問題已經解決了，得到了一個大小為n-1的有序陣列: A[0]≤..≤A[n- 2]，我們如何利用這個較小規模的解，并將元素A[n- 1]考慮進來，來得到原問題的解呢?顯然，我們需要做的就是在這些有序的元素中為A[n- 1]找到一個合適的位置，然后把它插入到那里，一般來說，我們可以從右到左掃描這個有序的子陣列，直
到遇到第一個小于等于A[n- 1]的元素，然后把A[n - 1]插在該元素的后面，這種演算法被稱為直接插入排序(straight insertion sort)，或者簡稱為插入排序(insertion sort)，
雖然插入排序很明顯是基于遞回思想的，但從底至上地實作這個演算法，也就是使用迭代，效率會更高，從A[I]開始，到A[n- 1]為止，A[1]被插在陣列的前i個有序元素中的適當位置.上(但是，和選擇排序不同，這個位置一般來說并不是它們的最終位置)，
演算法設計
查看代碼
public class TEST {
public static void main(String[] args) {
// TODO Auto-generated method stub
int a[]= {89,45,68,90,29,34,17};
System.out.print("排序前：");
for(int k=0;k<a.length;k++){
System.out.print(a[k]+" ");
}
System.out.println();
for(int i=1;i<a.length;i++) {
int v=a[i];
int j=i-1;
while(j>=0&&a[j]>v) {
a[j+1]=a[j];
j=j-1;
a[j+1]=v;
}
}
System.out.print("排序后：");
for(int k=0;k<a.length;k++){
System.out.print(a[k]+" ");
}
}
}運行結果
在黑夜里夢想著光，心中覆寫悲傷，在悲傷里忍受孤獨，空守一絲溫暖， 我的淚水是無底深海，對你的愛已無言，相信無盡的力量，那是真愛永在， 我的信仰是無底深海，澎湃著心中火焰，燃燒無盡的力量，那是忠誠永在排序前：89 45 68 90 29 34 17
排序后：17 29 34 45 68 89 90
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/394953.html
標籤：其他
上一篇：【計理02組01號】選擇排序
下一篇：【計理02組04號】順序查找