一.插入排序
1.利用监视哨实现

class Solution{
public:
    static void InsertSort(int data[], int n){
        //data为待排数组(data[0]不真正存储元素，而是用于存放监视哨)
        //n为数组中元素个数
        for (int i=2; i<=n; ++i){
            if(data[i]<data[i-1]){
                data[0] = data[i]; //复制为监视哨
                int j=0;
                for(j=i-1; data[0]<data[j]; --j){
                    data[j+1] = data[j]; //记录后移
                }
                data[j+1] = data[0]; //插入到正确位置
            }
        }
    }
};

2.递归实现

class Solution{
public:
    static void RecursiveInsert(int data[], int i, int j){
        if(i>=j){
            return;
        }
        int n=j-1;
        if(n > 1){
            RecursiveInsert(data, i, n);
        } else{
            return;
        }
        if(data[n]<data[n-1]){
            data[0] = data[n]; //监视哨
            int m=0;
            for(m=n-1; data[0]<data[m]; --m){
                data[m+1] = data[m]; //记录后移
            }
            data[m+1] = data[0]; //插入到正确位置
        }
    }
};

二.冒泡排序

static void BubbleSort(int data[], int n){
    //对data[1:n]进行冒泡排序
    int i=n;
    while(i>1){
        int lastExchangeIndex = 1;
        for(int j=1; j<i; j++){
            if(data[j+1] < data[j]){
                int temp = data[j+1]; //进行交换
                data[j+1] = data[j];
                data[j] = temp;
                lastExchangeIndex = j; //记录下进行交换的记录位置
            }
        }
        i = lastExchangeIndex; //本趟进行过交换的最后一个记录的位置
    }
}

三.快速排序

static void QuickSort(int data[], int i, int j){
    //对数组data[1:n]进行快速排序
    if(i < j-1){
        //数组长度大于1
        int pivotloc = Partition(data, i, j);
        //对data[1:n]进行一次划分 pivotloc是枢轴位置
        QuickSort(data, i, pivotloc-1); //对低子序列递归排序
        QuickSort(data, pivotloc+1, j); //对高子序列递归排序
    }
}

static int Partition(int data[], int low, int high){
    data[0] = data[low];
    int pivotkey = data[low]; //枢轴

    while (low < high){
        while (low<high && data[high]>=pivotkey){
            --high; //从右向左搜索
        }
        data[low] = data[high];
        while (low<high && data[low]<=pivotkey){
            ++low; //从左向右搜索
        }
        data[high] = data[low];
    }
    data[low] = data[0];
    return low;
}

四.归并排序

void merge(int a[], int left, int mid, int right, int result[]){
    //合并a[l:m]和a[m+1:r]到b[l:r]
    int i=left, j=mid+1, k=left;
    while ((i<=mid) && (j<=right)){
        if(a[i]<=a[j]){
            result[k++] = a[i++];
        } else{
            result[k++] = a[j++];
        }
    }
    if(i>mid){
        for(int q=j; q<=right; q++){
            result[k++] = a[q];
        }
    } else{
        for(int q=i; q<=mid; q++){
            result[k++] = a[q];
        }
    }
}

void MergeSort(int a[], int left, int right, int result[]){
    //A[left:right]是一个全程数组 含有right-left+1个待排序元素
    if(left == right){
        return;
    }
    if(left<right){ //至少有两个元素
        int mid = (left+right)/2; //当前数组分割点
        MergeSort(a, left, mid, result); //递归 分别对两个子问题归并排序
        MergeSort(a, mid+1, right, result);
        merge(a, left, mid, right, result); //把排好序的两个子问题合并，放入另一个数组result中
        for(int i=left; i<=right; i++){
            a[i] = result[i];
        }
    }
}