直接插入排序
程序员文章站
2022-06-04 09:37:18
...
排序就是把一组数据,按关键字排成有序数列。根据储存位置的不同分为内部排序和外部排序,在这里首先介绍内部排序。内部排序根据排序算法或逻辑分为:
- 插入排序:直接插入排序、希尔排序;
- 选择排序:简单选择排序、堆排序;
- 交换排序:冒泡排序、快速排序;
- 归并排序;
- 基数排序。
接下来对每种排序方法的思想进行介绍,并代码实现,以及分析其时间复杂度、空间复杂度和稳定性。
直接插入排序
把一个需要排序的数组分为已排序好的部分和未排序的部分,从未排序部分获取一个关键字作为待排序数,从已排序部分找到合适位置,插入这个数据。
如上图所示的具体例子,我们给出一个数组,首先单独的一个5是有序的;
接下来待排序的是1,赋值给临时变量tmp,5和1比较,5>1,将5后移,再将tmp赋给第一个元素,此时前两个元素是有序的;
接下来待排序的是3,赋值给临时变量tmp,5和3比较,5>3,将5后移,1再和3比较,1<3,然后将tmp赋给第二个个元素,此时前三个元素是有序的;
以此类推,直到全部有序。
代码实现如下:
#include<stdio.h>
void InsertSort(int arr[],int len)
{
int i;
int j;
int tmp;
for(i=1;i<len;i++)
{
tmp = arr[i];
for(j=i-1; j>=0 && arr[j]>tmp; --j)
{
arr[j+1] = arr[j];
}
arr[j+1] = tmp;
}
}
void InsertSort(int arr[], int len)
{
int i, j;
for (i = 2; i < len; ++i)
{
arr[0] = arr[i];//arr[0]哨兵位,相当于tmp的作用
for (j = i - 1; arr[j] > arr[0]; --j)
{
arr[j + 1] = arr[j];
}
arr[j + 1] = arr[0];
}
}
从空间来看,它只需要一个记录的辅助空间,空间复杂度为O(1);
从时间来看,排序的基本操作为:比较两个关键字的大小和移动记录,时间复杂度为O(n^2)。
交换的条件为arr[j]>tmp,在两个数相等时不交换顺序,所以该算法是稳定的。
缺点:数据多时,移动数据花费大量时间。
适用于数据少且较有序时。