插入排序法 Insertion Sort
写在Insertion Sort之前：
第一节我们已经学习了一种O(n^2)时间复杂度的排序算法——选择排序法
我们来学习第二种O(n^2)时间复杂度的排序算法——插入排序。
Insertion Sort 思路：
我们大多数人玩扑克整理牌的思想大体就是插入排序的思想——就是看后面的每一张牌，然后插入到前面合适的位置，当我们对最后一张牌完成了此操作，我们手里的牌就排序完成了！
1.png
我们来看动画演示：
我们要对这个数组排序：
数组.png
我们先看第1个元素（8）：
第1个
对于8这个第1个元素，我们不动，因为我们只考虑8这个元素是，它只有一个人（已经排好序了）
下面我们来看6这个元素（即第2个数）：
第2个数.png
我们要把6放到前面这个数组中合适的位置（此时我们只考虑前面2个元素，即8和6），此时6和8相比比前面的8小，所以交换位置：
交换6和8.png
交换后：
交换后.png
此时，前两个元素就已经排好序了：
前两个元素已排好.png
再来看第3个元素（2）：
第3个元素.png
要把2插入到前面合适的位置：（此时我们只考虑前面3个元素，即6、8和2）
2分别和前面的相比：
2比8小，交换：
2和8交换.png
QQ图片20170725190522.png
之后，2和6比，2比6小，交换：
QQ图片20170725190821.png
QQ图片20170725190844.png
前3个元素已经排好位置：
QQ图片20170725190916.png
后面直接看图吧：
QQ图片20170725191026.png
QQ图片20170725191050.png
QQ图片20170725191134.png
最后3和2比，3比2大，3和2不交换；至此，前面4个已经排好序：
QQ图片20170725191238.png
有兴趣的可以已经推推后面的动作，也可以下载PPT看演示文稿。
下面来看C++代码：
SortTestHelper.h:
#ifndef INC_04_INSERTION_SORT_SORTTESTHELPER_H
#define INC_04_INSERTION_SORT_SORTTESTHELPER_H
#include <iostream>
#include <algorithm>
#include <string>
#include <ctime>
#include <cassert>
using namespace std;
namespace SortTestHelper {
// 生成有n个元素的随机数组,每个元素的随机范围为[rangeL, rangeR]
int *generateRandomArray(int n, int range_l, int range_r) {
int *arr = new int[n];
srand(time(NULL));
for (int i = 0; i < n; i++)
arr[i] = rand() % (range_r - range_l + 1) + range_l;
return arr;
}
// 拷贝整型数组a中的所有元素到一个新的数组, 并返回新的数组
int *copyIntArray(int a[], int n){
int *arr = new int[n];
//* 在VS中, copy函数被认为是不安全的, 请大家手动写一遍for循环:)
copy(a, a+n, arr);
return arr;
}
// 打印arr数组的所有内容
template<typename T>
void printArray(T arr[], int n) {
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
return;
}
// 判断arr数组是否有序
template<typename T>
bool isSorted(T arr[], int n) {
for (int i = 0; i < n - 1; i++)
if (arr[i] > arr[i + 1])
return false;
return true;
}
// 测试sort排序算法排序arr数组所得到结果的正确性和算法运行时间
template<typename T>
void testSort(const string &sortName, void (*sort)(T[], int), T arr[], int n) {
clock_t startTime = clock();
sort(arr, n);
clock_t endTime = clock();
cout << sortName << " : " << double(endTime - startTime) / CLOCKS_PER_SEC << " s"<<endl;
assert(isSorted(arr, n));
return;
}
};
#endif //INC_04_INSERTION_SORT_SORTTESTHELPER_H
SelectionSort.h:
#ifndef INC_04_INSERTION_SORT_SELECTIONSORT_H
#define INC_04_INSERTION_SORT_SELECTIONSORT_H
#include <iostream>
#include <algorithm>
using namespace std;
template<typename T>
void selectionSort(T arr[], int n){
for(int i = 0 ; i < n ; i ++){
int minIndex = i;
for( int j = i + 1 ; j < n ; j ++ )
if( arr[j] < arr[minIndex] )
minIndex = j;
swap( arr[i] , arr[minIndex] );
}
}
#endif //INC_04_INSERTION_SORT_SELECTIONSORT_H
main.cpp:
#include <iostream>
#include <algorithm>
#include "SortTestHelper.h"
#include "SelectionSort.h"
using namespace std;
template<typename T>
void insertionSort(T arr[], int n){
for( int i = 1 ; i < n ; i ++ ) {
// 寻找元素arr[i]合适的插入位置
// 写法1
// for( int j = i ; j > 0 ; j-- )
// if( arr[j] < arr[j-1] )
// swap( arr[j] , arr[j-1] );
// else
// break;
// 写法2
for( int j = i ; j > 0 && arr[j] < arr[j-1] ; j -- )
swap( arr[j] , arr[j-1] );
}
return;
}
// 比较SelectionSort和InsertionSort两种排序算法的性能效率
// 此时， 插入排序比选择排序性能略低
int main() {
int n = 20000;
cout<<"Test for random array, size = "<<n<<", random range [0, "<<n<<"]"<<endl;
int *arr1 = SortTestHelper::generateRandomArray(n,0,n);
int *arr2 = SortTestHelper::copyIntArray(arr1, n);
SortTestHelper::testSort("Insertion Sort", insertionSort,arr1,n);
SortTestHelper::testSort("Selection Sort", selectionSort,arr2,n);
delete[] arr1;
delete[] arr2;
cout<<endl;
return 0;
}
对插入排序，第1个元素根本不用考虑，1个就已经算排好序了！
对于循环边界控制，告诫大家不要偷懒，头脑中要是考虑不清楚就马上去用笔在纸上模拟模拟
注意：
插入排序和选择排序最大的一个区别，就是：对于第二层循环，插入排序是可以提前结束的！
第二层循环提前结束.png
而对于选择排序 不管整个数组是什么样子的，为了找到没一轮中最小的那个元素，必须从头到尾把剩下的整个数组全扫面一遍，而没有提前终止条件。
因为以上原因，插入排序理论上要比选择排序效率好，但是：
C++代码运行结果：
插入排序 选择排序.png
结果显示插入排序用时9秒多 选择排序用时0.5秒
插入排序比选择排序用时多！
具体原因即算法改进请关注：
2 排序基础 - 5插入排序法的改进
Java代码：
** InsertionSort.java: **
import java.util.*;
public class InsertionSort{
// 我们的算法类不允许产生任何实例
private InsertionSort(){}
public static void sort(Comparable[] arr){
int n = arr.length;
for (int i = 0; i < n; i++) {
// 寻找元素arr[i]合适的插入位置
// 写法1
// for( int j = i ; j > 0 ; j -- )
// if( arr[j].compareTo( arr[j-1] ) < 0 )
// swap( arr, j , j-1 );
// else
// break;
// 写法2
for( int j = i; j > 0 && arr[j].compareTo(arr[j-1]) < 0 ; j--)
swap(arr, j, j-1);
}
}
private static void swap(Object[] arr, int i, int j) {
Object t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
// 测试InsertionSort
public static void main(String[] args) {
int N = 20000;
Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
SortTestHelper.testSort("bobo.algo.InsertionSort", arr);
return;
}
}
** SelectionSort.java: **
import java.util.*;
public class SelectionSort{
// 我们的算法类不允许产生任何实例
private SelectionSort(){}
public static void sort(Comparable[] arr){
int n = arr.length;
for( int i = 0 ; i < n ; i ++ ){
// 寻找[i, n)区间里的最小值的索引
int minIndex = i;
for( int j = i + 1 ; j < n ; j ++ )
// 使用compareTo方法比较两个Comparable对象的大小
if( arr[j].compareTo( arr[minIndex] ) < 0 )
minIndex = j;
swap( arr , i , minIndex);
}
}
private static void swap(Object[] arr, int i, int j) {
Object t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
// 测试SelectionSort
public static void main(String[] args) {
int N = 20000;
Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
SortTestHelper.testSort("bobo.algo.SelectionSort", arr);
return;
}
}
** SortTestHelper.java: **
import java.lang.reflect.Method;
import java.lang.Class;
public class SortTestHelper {
// SortTestHelper不允许产生任何实例
private SortTestHelper(){}
// 生成有n个元素的随机数组,每个元素的随机范围为[rangeL, rangeR]
public static Integer[] generateRandomArray(int n, int rangeL, int rangeR) {
assert rangeL <= rangeR;
Integer[] arr = new Integer[n];
for (int i = 0; i < n; i++)
arr[i] = new Integer((int)(Math.random() * (rangeR - rangeL + 1) + rangeL));
return arr;
}
// 打印arr数组的所有内容
public static void printArray(Object[] arr) {
for (int i = 0; i < arr.length; i++){
System.out.print( arr[i] );
System.out.print( ' ' );
}
System.out.println();
return;
}
// 判断arr数组是否有序
public static boolean isSorted(Comparable[] arr){
for( int i = 0 ; i < arr.length - 1 ; i ++ )
if( arr[i].compareTo(arr[i+1]) > 0 )
return false;
return true;
}
// 测试sortClassName所对应的排序算法排序arr数组所得到结果的正确性和算法运行时间
public static void testSort(String sortClassName, Comparable[] arr){
// 通过Java的反射机制，通过排序的类名，运行排序函数
try{
// 通过sortClassName获得排序函数的Class对象
Class sortClass = Class.forName(sortClassName);
// 通过排序函数的Class对象获得排序方法
Method sortMethod = sortClass.getMethod("sort",new Class[]{Comparable[].class});
// 排序参数只有一个，是可比较数组arr
Object[] params = new Object[]{arr};
long startTime = System.currentTimeMillis();
// 调用排序函数
sortMethod.invoke(null,params);
long endTime = System.currentTimeMillis();
assert isSorted( arr );
System.out.println( sortClass.getSimpleName()+ " : " + (endTime-startTime) + "ms" );
}
catch(Exception e){
e.printStackTrace();
}
}
}
** Main.java: **
import java.util.Arrays;
public class Main {
// 比较SelectionSort和InsertionSort两种排序算法的性能效率
// 此时，插入排序比选择排序性能略低
public static void main(String[] args) {
int N = 20000;
System.out.println("Test for random array, size = " + N + " , random range [0, " + N + "]");
Integer[] arr1 = SortTestHelper.generateRandomArray(N, 0, N);
Integer[] arr2 = Arrays.copyOf(arr1, arr1.length);
SortTestHelper.testSort("bobo.algo.SelectionSort", arr1);
SortTestHelper.testSort("bobo.algo.InsertionSort", arr2);
return;
}
}
