排序算法总结1

最近很发奋的又想到再看看排序算法。要学习的很多，总是有很多不足。压力山大啊。

1.直接插入排序。
就这么简单的排序，看了好久才弄懂他的流程。唉，年纪大了。脑袋都不好使了！
{49}  {38} {13} {65} {97} {76}
将第一个数字看作是有序的。则 第一次｛38｝ 与｛49｝比较，｛38｝ 小于 ｛49｝
将｛38｝置为哨兵。---大于其的数字向后移动，而哨兵的值一直往前寻找自己合适插入的位置，直到比较的值小于或者等于自己。

//直接插入排序: 第一个当作哨兵
void insertSort(int a[], int len)
{
    int i, j;
    for(i = 2; i < len; i++)
    {
     if(a[i] < a[i-1])
     {
            a[0] = a[i];
            a[i] = a[i-1];
            for(j = i-2; a[0] < a[j]; j--)
            {
                a[j+1] = a[j];
            }
            a[j+1] = a[0];
     }
    }
}

2.直接插入排序改版---折半插入排序

//折半插入排序
void insertSort1(int a[], int len)
{
    int i, j;
    int low, high, mid;
    for(i = 2; i < len; i++)
    {
        a[0] = a[i];
        low = 1;
        high = i-1;
        while(low <= high)
        {
         mid = (low + high)/2;
            if(a[mid] > a[0])
                high = mid -1;
            else
                low = mid + 1;
        }
        for(j=i-1; j>=high+1; j--)
        {
            a[j+1] = a[j];
        }
        a[high+1] = a[0];
    }
}

3.希尔排序
1.将序列按增量划分为元素个数相同的若干组，使用直接插入排序进行排序，然后不断缩小增量到1.最后使用直接插入排序完成排序

//希尔排序
//间隔比较
void insertShellSort(int a[], int len, int dk)
{
    int i,j;
    for(i=dk+1; i<len; i++)
    {
     if(a[i] < a[i-dk])
        {
            a[0] = a[i];
            a[i] = a[i-dk];
            for(j=i-dk-dk; j>0&&a[0]<a[j]; j-=dk)
                a[j+dk] = a[j];
            a[j+dk] = a[0];
     }

    }
}

void shellSort(int a[], int len, int d)
{
    while(d >= 1)
    {
        insertShellSort(a, len, d);
        d = d/2;
    }
}

4.冒泡排序

//冒泡排序----设置一个跳出条件
void MaoPaoSort(int a[], int len)
{
    int i, j;
    int tmp;
    bool bchange;
    for(i=len-1; i>0; i--)
    {
        bchange = false;
     for(j=0; j<i; j++)
     {
     if(a[j] > a[j+1])
     {
                tmp = a[j];
                a[j] = a[j+1];
                a[j+1] = tmp;
                bchange = true;
     }
     }
        if(!bchange)//说明已经有序
            break;
    }
}