插入排序 vs. 选择排序

1. 插入排序：复杂度
   类似玩扑克时候的快速整理手中的牌的过程。我们每次拿到一张新的牌，会将其插入到已有的牌中的合适位置。
   插入排序每次循环开始前，第1...j-1个元素是已经排列好的，我们从后面未排列的元素中取第j个元素插入到前1...j-1个元素中的合适位置，插入后保持元素1...j的有序性。这样j递增n-1次后，所有的n个元素就排列好了。

#include <iostream>
using namespace std;

void insertion_sort(int A[],int length){
    for(int j=1;j<length;j++){
        int key=A[j];
        int i=j-1;
        while(i>=0&&A[i]>A[j]){
            A[i+1]=A[i];
            i--;
        }
        A[i+1]=key;
    }
}

int main(int argc, const char * argv[]) {
    int arr[]={1,3,2,5,88,9};
    int l=sizeof(arr)/sizeof(int);
    insertion_sort(arr,l);
    for(int i=0;i<l;i++)
        cout<<arr[i]<<" ";
    cout<<endl;
    return 0;
}

2. 选择排序：复杂度
   每次选择n个元素中第i个最小的元素，放到第i个位置上。

#include <iostream>
using namespace std;

void selection_sort(int A[],int length){
    for(int i=0;i<length-1;i++){
        int m=A[i],key=i;
        for(int j=i+1;j<length;j++)
            if(A[j]<m){
                m=A[j];
                key=j;
            }
        swap(A[i],A[key]);
    }
}

int main(int argc, const char * argv[]) {
    int arr[]={1,3,2,5,88,9};
    int l=sizeof(arr)/sizeof(int);
    selection_sort(arr,l);
    for(int i=0;i<l;i++)
        cout<<arr[i]<<" ";
    cout<<endl;
    return 0;
}