最近从网易公开课在看麻省理工学院的公开课《算法导论》，感觉还不错，接下来几篇文章所示学习日记了，不准备对算法细节做过多描述，感兴趣的可以自己去看。

文章分几篇讲经典排序算法，直接上代码，根据结果对算法性能有个直观了解。本篇先说插入排序（insertion sort）。

(一)算法实现

1 protected void sort(int[] toSort) { 2         if (toSort.length <= 1) { 3             return; 4         } 5         for (int i = 1; i < toSort.length; i++) { 6             if (toSort[i] < toSort[i - 1]) { 7                 int j = i; 8                 int temp = toSort[i]; 9                 while (j > 0 && temp < toSort[j - 1]) {10                     toSort[j] = toSort[j - 1];11                     j--;12                 }13                 toSort[j] = temp;14             }15         }16     }

 

1）插入排序属于原地排序，节省空间

2）插入排序的时间复杂度是O(n²)

3）插入排序属于比较排序

4）插入排序属于稳定排序算法

 

（二）算法性能

**************************************************

Number to Sort is:2500

Array to sort is:{665184,192100,475135,171530,869545,506246,640618,543738,91353,493005...}

Cost time of 【InsertionSort】 is(milliseconds):3

Sort result of 【InsertionSort】:{856,985,2432,3792,3910,3915,4423,4516,4653,4780...}

**************************************************

Number to Sort is:25000

Array to sort is:{99880,631403,265087,597224,876665,955084,996547,879081,197806,926881...}

Cost time of 【InsertionSort】 is(milliseconds):267

Sort result of 【InsertionSort】:{14,14,17,83,97,152,179,199,240,299...}

**************************************************

Number to Sort is:250000

Array to sort is:{777293,731773,508229,920721,338608,707195,940,445210,19071,768830...}

Cost time of 【InsertionSort】 is(milliseconds):21,523

Sort result of 【InsertionSort】:{2,7,7,19,19,21,24,29,30,39...}

相关代码：

1 package com.cnblogs.riyueshiwang.sort; 2  3 import java.util.Arrays; 4  5 public class InsertionSort extends abstractSort { 6     @Override 7     protected void sort(int[] toSort) { 8         if (toSort.length <= 1) { 9             return;10         }11         for (int i = 1; i < toSort.length; i++) {12             if (toSort[i] < toSort[i - 1]) {13                 int j = i;14                 int temp = toSort[i];15                 while (j > 0 && temp < toSort[j - 1]) {16                     toSort[j] = toSort[j - 1];17                     j--;18                 }19                 toSort[j] = temp;20             }21         }22     }23 24     public static void main(String[] args) {25         for (int j = 0, n = 2500; j < 3; j++, n = n * 10) {26             System.out27                     .println("**************************************************");28             System.out.println("Number to Sort is:" + n);29             int[] array = CommonUtils.getRandomIntArray(n, 1000000);30             System.out.print("Array to sort is:");31             CommonUtils.printIntArray(array);32 33             int[] array1 = Arrays.copyOf(array, n);34             new InsertionSort().sortAndprint(array1);35         }36     }37 }

1 package com.cnblogs.riyueshiwang.sort; 2  3 import java.text.MessageFormat; 4  5 public abstract class abstractSort { 6     /** 7      *  8      * @param toSort 9      *            array to sort10      */11     protected abstract void sort(int[] toSort);12 13     public void sortAndprint(int[] toSort) {14         Long begin = System.currentTimeMillis();15         sort(toSort);16         Long end = System.currentTimeMillis();17         System.out.println(MessageFormat.format(18                 "Cost time of 【{0}】 is(milliseconds):{1}", this.getClass()19                         .getSimpleName(), (end - begin)));20         System.out.print(MessageFormat.format("Sort result of 【{0}】:", this21                 .getClass().getSimpleName()));22         CommonUtils.printIntArray(toSort);23     }24 25 }

1 package com.cnblogs.riyueshiwang.sort; 2  3 import java.util.Random; 4  5 public class CommonUtils { 6     private static Random random = new Random(); 7  8     public static void printIntArray(int[] array) { 9         System.out.print('{');10 11         int length = Math.min(array.length, 10);12         for (int i = 0; i < length; i++) {13             System.out.print(array[i]);14             if (i != length - 1) {15                 System.out.print(',');16             } else {17                 if (array.length > 10) {18                     System.out.print("...");19                 }20                 System.out.println('}');21             }22         }23     }24 25     public static int[] getRandomIntArray(int size, int maxValue) {26         int[] array = new int[size];27         for (int i = 0; i < size; i++) {28             array[i] = random.nextInt(maxValue);29         }30         return array;31     }32 33     public static void swap(int[] toSort, int i, int j) {34         int temp = toSort[i];35         toSort[i] = toSort[j];36         toSort[j] = temp;37     }38 }