插入排序算法总结

1.直接插入排序
从前往后固定有序元素

void insertSort(int a[], int n)
{
    for (int i = 1; i < n; i++) {
        int  temp = a[i];
        for (int j = i - 1; j >= 0 && a[j] > temp; j--) {
            a[j + 1] = a[j];
        }
        a[j + 1] = temp;    
    }

}

2.折半插入排序
从前往后固定有序元素

void halfInsertSort(int a[], int n)
{
    for(int i = 1; i < n; i ++)
    {
        int l = 0, r = i - 1, tmp = a[i];

        while(r >= l)
        {  
           int mid = (l + r) / 2;
            if(a[mid] > tmp) r = mid - 1;
            else l = mid + 1;
        }

        for(int j = i - 1; j >= r + 1; j --) a[j + 1] = a[j];
        a[r + 1] = tmp;
    }
}

3.希尔排序

void shell_sort(int arr[], int len) {
    int gap, i, j;
    int temp;
    for (gap = len >> 1; gap > 0; gap >>= 1)
        for (i = gap; i < len; i++) {
            temp = arr[i];
            for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap)
                arr[j + gap] = arr[j];
            arr[j + gap] = temp;
        }
}

4.冒泡排序
从后往前固定有序元素

void bubbleSort(int a[], int n)
{
    for(int i = 1; i < n; i ++)
    {
        bool flag = true;

        for(int j = 1; j <n - i + 1; j ++)
        {
            if(a[j] < a[j - 1]) swap(a[j],a[j - 1]);
            flag = false;
        }

        if(flag == true) return;
    }
}

5.快排

void quickSort(int a[], int l, int r)
{
    if(l >= r) return;

    int x = a[l + r >> 1],i = l - 1, j = r + 1;

    while(i < j)
    {
        do i ++; while(a[i] < x);
        do j --; while(a[j] > x);
        if(i < j) swap(a[i],a[j]);
    }

    quick_sort(a, l, j); quick_sort(a, j + 1, r);
}

6.简单选择排序
从前往后遍历数组，从前往后固定有序元素，在每一次的遍历序列前面留出一位，遍历序列中的最小值与该位比较得出完整序列的最小值。

void simpleSelectSort(int a[], int n)
{
    for(int i = 1; i < n; i ++)
    {
        int min = i;

        for(int j = i; j < n; j ++)
        {
            if(a[j] < a[min]) min = j;
        }

        if(a[min] < a[i - 1]) swap(a[i - 1],a[min]);
    }
}

7.堆排序

8.归并排序

void mergeSort(int a[], int l, int r)
{
    if (l >= r) return;

    int mid = l + r >> 1;
    merge_sort(a, l, mid);
    merge_sort(a, mid + 1, r);

    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (a[i] <= a[j]) tmp[k ++ ] = a[i ++ ];
        else tmp[k ++ ] = a[j ++ ];

    while (i <= mid) tmp[k ++ ] = a[i ++ ];
    while (j <= r) tmp[k ++ ] = a[j ++ ];

    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}