6.插入排序(改进版)

//插入排序法（改进版）
template<typename T>
void insertionSort(T arr[], int n){
    for(int i = 1; i < n; i++){
      //寻找元素arr[i]合适的插入位置
        T e = arr[i];
        int j;//j用来保存元素e应该插入的位置
        for(j = i; j > 0 && arr[j-1] > e; j--)
            arr[j] = arr[j-1];
        arr[j] = e;
    }
}

图片演示:

测试程序：

#include <iostream>
#include <algorithm>
#include "temp.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]);
    }
    */
    //写法3
    T e = arr[i];
    int j; //j保存元素e应该插入的位置
    for( j = i; j > 0 && arr[j-1] > e; j-- )
        arr[j] = arr[j-1]; 
    arr[j] = e;
    }   
}

int main()
{
    int n = 10000;
    
    //测试1 一般测试(有序性很差) 
    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;
    
    //测试2 有序性更强的测试
     
    cout << "Test for more ordered random array ,size = " << n << ", random range [0,3]" << endl;
    arr1 = SortTestHelper::generateRandomArray(n, 0, 3);
    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;
    
    //测试3 测试近乎有序的数组
    
    int swapTimes = 100;
    cout << "Test for Random Nearly Ordered Array, size = " << n << ", swap time = " << swapTimes << endl;
    arr1 = SortTestHelper::generateNearlyOrderedArray(n,swapTimes);
    arr2 = SortTestHelper::copyIntArray(arr1, n);

    SortTestHelper::testSort("Insertion Sort", insertionSort,arr1,n);
    SortTestHelper::testSort("Selection Sort", selectionSort,arr2,n);

    delete[]arr1;
    delete[]arr2;
    
    return 0;
}

temp.h:
#ifndef _TEMP_H
#define _TEMP_H
#include <iostream>
#include <ctime>
#include <cassert>
#include <algorithm>
using namespace std;

namespace SortTestHelper{
    // 生成有n个元素的随机数组,每个元素的随机范围为[rangeL, rangeR]
    int *generateRandomArray(int n, int rangeL, int rangeR){
        assert(rangeL <= rangeR);
        int *arr = new int[n];
        srand(time(NULL));//将当前时间作为种子设置 
        for(int i = 0; i < n; i++)
            arr[i]  = rand() % (rangeR - rangeL + 1) + rangeL;//函数返回一个随机整数，但需要对随机整数的范围进行控制 
        return arr;
    }
    
    
    int *generateNearlyOrderedArray(int n, int swapTimes){
        int *arr = new int [n];
        for(int i = 0; i < n; i++)
            arr[i] = i;
        srand(time(NULL));
        for( int i = 0; i < swapTimes; i++ ){
            int posx = rand()%n;
            int posy = rand()%n;
            swap( arr[posx], arr[posy]);
        }
        return arr;
    }
    
    int* copyIntArray(int a[], int n){
        int *arr = new int [n];
        copy(a, a + n, arr);
        return arr;
    }
    
    
    template<typename T>
    void PrintArray(T arr[], int n){
        for( int i = 0; i < n; i++)
            cout << arr[i] << " ";
        cout << endl;
        return;
    }
    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;
    }
    /*
    * endTime - startTime返回的是运行了几个时钟周期
    * CLOCK_PER_SEC是标准库中定义的宏，表示每秒钟运行的时钟周期的个数
    */
    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();
        assert(isSorted(arr,n));
        cout << sortName << ":" << double( endTime - startTime ) / CLOCKS_PER_SEC << " s" << endl;
        return;
    }
};

#endif

SelectionSort.h:
#ifndef _SELECTIONSORT_H
#define _SELECTIONSORT_H
#include<iostream>
#include<algorithm>
using namespace std;

template<typename T>
void selectionSort(T arr[], int n)
{
    for(int i = 0; i < n-1; 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

改进后的排序算法效率大幅提升.

以下是未改进的插入排序版本：

可以看出在有序性很差的情况下，未改进的插入排序算法的性能是很差的.

事实上插入排序对于近乎有序的数组甚至比O(nlogn)级别的排序算法还要快.
最坏情况下O(n^2).
最优情况下，即当数组为完全有序时，插入排序将变成O(n)级别的算法.