根据王道书上的代码,结合自己的理解,写的插入排序的代码,分为直接插入排序和希尔排序两个。
直接插入排序
直接插入排序的思想是将每一个元素插入到已经有序的序列中,使其仍然保持有序。在实际代码处理的时候,胸第二个元素开始处理,将前面的序列看成有序,实现原地排序的效果。
直接插入排序的空间复杂度为O(1),且为稳定的排序算法。
直接插入排序的最好时间复杂度为O(n),最坏时间复杂度为O(n2),平均时间复杂度为O(n2)
# include <stdio.h>
# include <stdlib.h>
# include <time.h>
# define LENGTH 10
void CreateList(int * data, int len)
{
int i = 0;
srand(time(NULL));
for (i=0; i<len; i++) {
data[i] = rand() % 100;
}
return;
}
void PrintList(int * data, int len)
{
int i = 0;
for (i=0; i<len; i++) {
printf("%d ", data[i]);
}
printf("\n");
return;
}
// 直接插入排序
void InsertSort(int * data /* 待处理的数据 */, int len /* 数据的长度 */)
{
int i = 0;
for (i=1; i<len; i++) { // 从第二个数据开始处理
int j = i - 1;
if (data[i] < data[i - 1]) { // 如果前面的序列存在比当前数值大的数
int temp = data[i];
while (j >= 0 && data[j] > temp) { // 一路往前把大的数向后移
data[j + 1] = data[j];
j--;
}
data[j + 1] = temp;
}
printf("%2d th sort: ", i);
PrintList(data, len);
}
return;
}
int main(void)
{
int * data = (int *)malloc(sizeof(int) * LENGTH);
CreateList(data, LENGTH);
printf("Before sort: ");
PrintList(data, LENGTH);
InsertSort(data, LENGTH);
printf("After sort: ");
PrintList(data, LENGTH);
return 0;
}
希尔排序
希尔排序是直接插入排序的一种优化。其核心思想为:
- 将间隔为d的元素取出来看成一个新的子序列
- 对子序列进行直接插入排序,这样会使得原序列相对有序
- 不断缩小d的值,直到d等于1,此时希尔排序退化为直接插入排序
因为希尔排序每一次的排序都是建立在之前相对有序的基础上,所以能相对提高效率。
直接插入排序的空间复杂度为O(1),且为不稳定的排序算法。
在增量序列函数选取合适的前提下,希尔排序的时间复杂度为O(n1.3),最坏情况下的时间复杂度为O(n2)。
# include <stdio.h>
# include <stdlib.h>
# include <time.h>
# define LENGTH 15
void CreateList(int * data, int len)
{
int i = 0;
srand(time(NULL));
for (i=0; i<len; i++) {
data[i] = rand() % 100;
}
return;
}
void PrintList(int * data, int len)
{
int i = 0;
for (i=0; i<len; i++) {
printf("%d ", data[i]);
}
printf("\n");
return;
}
// 希尔排序
void ShellSort(int * data, int len)
{
int d = 0;
int i = 0;
for (d=len/2; d>=1; d/=2) { // 设置步长,初始值为元素个数的一半,最后的值为1
for (i=d; i<len; i++) { // 在规定的步长内对元素进行直接插入排序
if (data[i] < data[i - d]) {
int temp = data[i];
int j = i - d;
while (j >= 0 && data[j] > temp) {
data[j + d] = data[j];
j = j - d;
}
data[j + d] = temp;
}
}
printf("d = %d: ", d);
PrintList(data, len);
}
return;
}
int main(void)
{
int * data = (int *)malloc(sizeof(int) * LENGTH);
CreateList(data, LENGTH);
printf("Before sort: ");
PrintList(data, LENGTH);
ShellSort(data, LENGTH);
printf("After sort: ");
PrintList(data, LENGTH);
return 0;
}