0.x 4.直接插入排序

dddd数据结构课本

• Author：李英民 | Henry
• E-mail: li_yingmin@outlookdotcom
• $Beijing~~U~of~Posts~and~Telecom$$(BUPT~)$
• Home: https://liyingmin.wixsite.com/henry

• 快速了解我: About Me

• 转载请保留上述引用内容，谢谢配合！

改进版：减少交换操作

#include <iostream>
#include <algorithm>
#include "SortTestHelper.h"
#include "SelectionSort.h"
using namespace std;
void insertionSort(int arr[], int n)
{
    if(n <= 0) return; //一定要考虑到这种情况
    for(int i = 1; i != n; ++i)
    {
        int temp = arr[i];
        int j = i;
        for(; j != 0 && temp < arr[j - 1]; --j)
        //temp<arr[j-1]这个条件可以提前终止循环，当arr[j-1]<=temp，此时这个j的位置就是arr[i]应该插入的位置；或者j=0，这时所有元素都移到j>0的位置，则直接在j=0的位置插入arr[i]
        {
            arr[j] = arr[j - 1];
        }
        arr[j] = temp;
    }
}
int main() {
    int a[10] = {10,9,8,7,6,5,4,3,2,1};
    insertionSort(a,10);
    for( int i = 0 ; i < 10 ; i ++ )
        cout<<a[i]<<ends;//ends表示刷新缓冲区，并附带一个空格" "
    cout<<endl;
    return 0;
}