插入排序之直接插入排序

• 2019 年 10 月 5 日
• 筆記

版權聲明：本文為部落客原創文章，遵循 CC 4.0 BY-SA 版權協議，轉載請附上原文出處鏈接和本聲明。

本文鏈接：https://blog.csdn.net/qq_37933685/article/details/84792290

個人部落格：https://suveng.github.io/blog/​​​​​​​ title: 插入排序之直接插入排序 date: 2018-12-01 19:00:00 +0800 update: 2018-12-01 19:00:00 +0800 author: suveng tags:

• 演算法 preview: 插入排序之直接插入排序

文章目錄

• 插入排序之直接插入排序
  • 原理
  • 時間複雜度
  • 空間複雜度
  • 穩定性
  • 演算法實現
    • Java

插入排序之直接插入排序

原理

1. 列表第一個元素和前面元素比較，如果小於前面元素（其實不存在），則交換位置。（這步其實可以沒有）
2. 列表第二個元素和前面元素（第一個元素）比較，如果小於前面元素，則交換位置。
3. 列表第三個元素和前面元素（第二個元素）比較，如果小於前面元素，則交換位置。如果和前面元素交換了位置，現在在第二個位置上，則接著繼續和前面元素比較（第一個元素），如果小於前面元素，接著再次交換位置，然後再次重複比較過程…
4. 繼續重複以上過程，直到最後一個元素完成比較

時間複雜度

空間複雜度

O(1)

穩定性

穩定

**穩定性定義：**排序前後兩個相等的數相對位置不變，則演算法穩定。

演算法實現

Java

class InsertionSort {  	public static void main(String[] args) {  		System.out.println("hello，直接插入排序");  		InsertSort is=new InsertSort();  		int[] des=is.directInsertSort(new int[]{72,78,42,60,84,74,60,79,72,52});  		for(int i=0;i<des.length;i++){  			System.out.println(" "+des[i]);  		}  		System.out.println();  	}    	public int[] directInsertSort(int[] source){  		int n=source.length;  		//可以直接從第二個元素開始  		for(int i=1;i<n;i++){  			for(int j=i;j>0;j--){  				if(source[j]<source[j-1]){  					//異或法 交換變數，減少臨時變數  					source[j]=source[j]^source[j-1];  					source[j-1]=source[j]^source[j-1];  					source[j]=source[j]^source[j-1];  				}  			}  		}  		return source;  	}  }