常见的比较排序算法有插入排序(直接插入排序和希尔排序),选择排序(选择排序和堆排序),交换排序(冒泡排序和快速排序),归并排序。
还有非比较排序:基数排序和计数排序。
本文讲讲插入排序中的直接插入排序和希尔排序。
直接插入排序
![](https://img.laitimes.com/img/_0nNw4CM6IyYiwiM6ICdiwiI0NXYFhGd192UvwVe0lmdhJ3ZvwFM38CXlZHbvN3cpR2Lc1TPB10QGtWUCpEMJ9CXsxWam9CXwADNvwVZ6l2c052bm9CXUJDT1wkNhVzLcRnbvZ2LcVDbYFGaoJjYxgWblZXUYpVd1kmYr50MZV3YyI2cKJDT29GRjBjUIF2LcRHelR3LcJzLctmch1mclRXY39zM0kjM0gTN5EDOyETM3EDMy8CX0Vmbu4GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.jpg)
如图所示是我们直接插入排序的算法思想,我们可以看到它的时间复杂度为O(N的平方)。
代码实现:
void InsertSort(int *a,size_t n)
{
assert(a);
for (size_t i = ; i<n - ; ++i)
{
int end = i;
int tmp = a[end + ];
while ( end>= )
{
if (a[end] > tmp)
{
a[end + ] = a[end];
--end;
}
else
{
break;
}
}
a[end + ] = tmp;
}
}
希尔排序:希尔排序可以说的直接插入排序的一种优化,他大致分为两步:预排序,直接插入排序。
上图就是希尔排序的算法思想,通常我们gap的取值是数组大小的三分之一加1,为什么加1呢,因为我们要保证gap>=1。也就是说gap至少有一个元素。
代码实现:
void ShellSort(int* a, size_t n)
{
assert(a);
//1,预排序 2,
int gap = n;
while (gap > )
{
gap = gap / + ;
for (size_t i = ; i < n - gap; ++i)
{
int end = i;
int tmp = a[end + gap];
while (end >= )
{
if (a[end]>tmp)
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
a[end + gap] = tmp;
}
}
}
}