算法第四版--直接插入排序

系列文章目錄

一、直接插入排序InsertSort

基本思想：每次将一個待排序的元素插入到前面已經排好的子序列當中，直至全部元素插入完成

1.分析

數組共分為3部分：有序序列，待排序元素，無序序列

首先，初始狀态時，有序序列為a[0]，整個過程會将a[1······n-1]

依次插入到前面已排好序的子序列當中

（a[n-1]為數組的最後一個元素，即a.length-1）

過程中為

2.代碼

代碼如下（示例）：

import edu.princeton.cs.algs4.StdOut;      //算法第四版中的自己的庫
//直接插入排序
public class Insertion {
	public static void sort(Comparable[] a) 
	{	
		for(int i=1; i<a.length; i++)     //a[1]開始，a[a.length-1]結束
		{
			for(int j=i-1; j>=0&& less(a[j+1],a[j]);j--)	
				exch(a,j+1,j);                  
		}	
	}
	
	//v < w?  比較大小
	private static boolean less(Comparable v, Comparable w) {
		return v.compareTo(w) < 0;          
	}
	//交換 a[i] 和a[j]
	private static void exch(Comparable[] a , int i,int j) {
		Comparable t=a[i];
		a[i] = a[j];
		a[j] = t;
	}		
           

摘自書中的兩句話：

1、在 Java中，元素通常都是對象，對主鍵的抽象描述則是通過一種内置的機制（請見2.1.1.4節中的Comparable接 口）來完成的。

2、大多數情況下，我們的排序代碼隻會通過兩個方法操作資料：less( )方法對元素進行比較，exch()方法将元素交換位置。exch ()方法的實作很簡單，通 過Comparable接口實作less( ) 方法也不困難。将資料操作限制在這兩個方法中使得代碼的可讀性和可移植性更好，更容易驗證代碼的正确性、分析性能以及排序算法之間的比較。

總結

提示：額外了解一下Comparable接口