[分享]插入排序和希尔排序不是一个算法么???
本帖最后由 小可爱～ 于 2016-10-25 13:11 编辑插入算法核心思想:
1 元素拿出来
2 符合条件的元素后移(比较大的元素往后移)
3 把拿出来的元素放到空着的地方
#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;
for (j = i - 1; (j >= 0) && (pArray > temp); j--)
{
pArray = pArray; //元素后移
k = j; //需要插入的位置
}
pArray = 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);
}
puts("");
system("pause");
return ret;
}
希尔算法
#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);
}
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;
// tmp > pArray 这个大于号代表的是数组从大到小还是从小到大
for (j = i - gap; j >= 0 && tmp > pArray; j -= gap)
{
pArray = pArray;
k = j;
}
pArray = 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;
for (j = i - gap; j >= 0 && tmp < pArray; j -= gap)
{
pArray = pArray;
k = j;
}
pArray = 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);
//从大到小
ShellSort01(buf, len);
//从小到大
//ShellPort02(buf, len);
printBuf(buf, len);
system("pause");
return ret;
}
仔细观看两个函数
一个是插入算法的, 一个是希尔算法的, 是不是很像???
说白了, 就是把插入算法核心函数中所有的 1 全部替换成 gap
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;
for (j = i - 1; (j >= 0) && (pArray > temp); j--)
{
pArray = pArray; //元素后移
k = j; //需要插入的位置
}
pArray = 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;
// tmp > pArray 这个大于号代表的是数组从大到小还是从小到大
for (j = i - gap; j >= 0 && tmp > pArray; j -= gap)
{
pArray = pArray;
k = j;
}
pArray = tmp;
}
} while (gap > 1);
}
}
楼主很厉害啊，女程序猿 shell 算法要优于 插入的 毕竟已经分组了。 正好在学希尔算法 shele 也是插入排序的一种，属于分组插入吧 谢谢，很厉害，算法是我薄弱的地方以后真的应该好好学了
看到算法， 莫名的激动了下， 排序当初研究过一点。
个人的理解：
插入排序是对一个"绝对有序"的序列进行插入的（这个有序不是指的序列本身有序，而是在插入排序的过程中，建立起了一个有序的序列）
例：
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: 希尔包含了插入所以楼主会觉得代码很相似
以上是个人的一点见解。
页:
[1]