[分享]插入排序和希尔排序不是一个算法么???

小可爱～

插入算法核心思想:
1 元素拿出来
2 符合条件的元素后移(比较大的元素往后移)
3 把拿出来的元素放到空着的地方

[C] 纯文本查看 复制代码

#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//1 元素拿出来
//2 符合条件的元素后移(比较大的元素往后移)

void InsertionSort(int *pArray, int len)
{
        int i, j;
        int k;
        int temp;
        if (NULL == pArray || len <= 0)
        {
                return;
        }
        for (i = 1; i < len; i++)
        {
                k = i;        //待插入的位置
                temp = pArray[k];
                for (j = i - 1; (j >= 0) && (pArray[j] > temp); j--)
                {
                        pArray[j + 1] = pArray[j];        //元素后移
                        k = j;        //需要插入的位置
                }
                pArray[k] = temp;        //元素插入
        }
}

int main(int argc, char *argv[])
{
        int ret = 0;
        int pArray[] = { 12, 5, 33, 65, 15555, 1 };
        int len = sizeof(pArray) / sizeof(int);

        InsertionSort(pArray, len);

        for (int i = 0; i < len; i++)
        {
                printf("%d ", pArray[i]);
        }
        puts("");
        system("pause");
        return ret;
}

希尔算法

[C] 纯文本查看 复制代码

#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//不稳定算法
//突破大 O (n ^ 2)

void printBuf(int *pArray, int len)
{
        int i = 0;
        if (NULL == pArray || 0 >= len)
        {
                printf("func err printBuf line:%d, file :%s\n", __LINE__, __FILE__);
                return;
        }

        for (i = 0; i < len; i++)
        {
                printf("%d\t", pArray[i]);
        }
        puts("");
}

//把大的提出来放到后面
void ShellSort01(int *pArray, int len)
{
        int i, j, k, tmp;
        int gap = len;

        do 
        {
                gap = gap / 3 + 1;
                for (i = gap; i < len; i += gap)
                {
                        k = i;
                        tmp = pArray[k];
                        //                                                                tmp > pArray[j] 这个大于号代表的是数组从大到小还是从小到大
                        for (j = i - gap; j >= 0 && tmp > pArray[j]; j -= gap)
                        {
                                pArray[j + gap] = pArray[j];
                                k = j;
                        }
                        pArray[k] = tmp;
                }
        } while (gap > 1);
        
}

void ShellPort02(int *pArray, int len)
{
        int i, j, k, tmp;
        int gap = len;

        do 
        {
                gap = gap / 3 + 1;
                for (i = gap; i < len; i += gap)
                {
                        k = i;
                        tmp = pArray[k];
                        for (j = i - gap; j >= 0 && tmp < pArray[j]; j -= gap)
                        {
                                pArray[j + gap] = pArray[j];
                                k = j;
                        }
                        pArray[k] = tmp;
                }
        } while (gap > 1);
}

int main(int argc, char *argv[])
{
        int ret = 0;
        int buf[] = { 45, 12, 654, 23, 8932, 9, 532, 213, 987, 3, 5, 546, 354 };
        int i = 0;
        int len = sizeof(buf) / sizeof(buf[0]);

        //从大到小
        ShellSort01(buf, len);
        //从小到大
        //ShellPort02(buf, len);
        printBuf(buf, len);
        system("pause");
        return ret;
}

仔细观看两个函数
一个是插入算法的, 一个是希尔算法的, 是不是很像???     

说白了, 就是把插入算法核心函数中所有的 1 全部替换成 gap

[C] 纯文本查看 复制代码

void InsertionSort(int *pArray, int len)
{
        int i, j;
        int k;
        int temp;
        if (NULL == pArray || len <= 0)
        {
                return;
        }
        for (i = 1; i < len; i++)
        {
                k = i;        //待插入的位置
                temp = pArray[k];
                for (j = i - 1; (j >= 0) && (pArray[j] > temp); j--)
                {
                        pArray[j + 1] = pArray[j];        //元素后移
                        k = j;        //需要插入的位置
                }
                pArray[k] = temp;        //元素插入
        }

void ShellSort01(int *pArray, int len)
{
        int i, j, k, tmp;
        int gap = len;

        do 
        {
                gap = gap / 3 + 1;//分组, 这是效率超过On2的方法
                for (i = gap; i < len; i += gap)
                {
                        k = i;
                        tmp = pArray[k];
                        //                                                                tmp > pArray[j] 这个大于号代表的是数组从大到小还是从小到大
                        for (j = i - gap; j >= 0 && tmp > pArray[j]; j -= gap)
                        {
                                pArray[j + gap] = pArray[j];
                                k = j;
                        }
                        pArray[k] = tmp;
                }
        } while (gap > 1);
        
}
}

不苦小和尚

楼主很厉害啊，女程序猿

wushaojienigesb

shell 算法要优于 插入的 毕竟已经分组了。

夜羽天隐

正好在学希尔算法

zrgong

shele 也是插入排序的一种，属于分组插入吧

LLMr

谢谢，很厉害，算法是我薄弱的地方以后真的应该好好学了

dydhyh

看到算法， 莫名的激动了下， 排序当初研究过一点。
个人的理解：
    插入排序是对一个"绝对有序"的序列进行插入的（这个有序不是指的序列本身有序，而是在插入排序的过程中，建立起了一个有序的序列）
    例：
        9 5 10 1
        对上述序列进行排序的话， 首先是取一个9出来， 成为一个单独的序列（脑补， 实际上并不是一个单独的）
        {9} 然后， 第二个元素5 插进来， 那么自然是插到5前面去， 所以这个序列就变成了{5, 9}, 以此类推。
        结合楼主的demo, 从整个序列中找到第i大（小）的数， 移动到第i个位置上。
而希尔排序是基于"分组"来进行排序的。
       例如上述例子序列
       假设增量d为2， 那么9 和 10 进行比较， 5 和 1 进行比较。 这里就体现出来分组了。
       插入排序是对整个序列进行对比的，而希尔是相对于组来对比。
       第一趟希尔排序后的结果为{9 1 10 5}
       序列被分成两个组{9 10 } 和 {5 1}
       希尔分组后，其实是对这两个组内进行插入排序 使其成为组内绝对有序的几个组
       当这个组变成1个的时候， 就成了绝对有序的序列了。
       PS: 希尔包含了插入  所以楼主会觉得代码很相似
以上是个人的一点见解。