数据结构C语言版直接插入排序
文章目录
内部排序:插入排序
- 基本思想: 每一步将一个待排序的元素,按其排序码的大小,插入到前面已经排好序 的一组元素的合适位置上去,直到元素全部插完为止。
- 直接插入排序; 当插入第i(i>=1)个元素时,前面的array[0],array[1],…,array[i-1]已经 排好序,此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序 进行比较,找到插入位置即将array[i]插入,原来位置上的元素顺序后移
- 元素集合越接近有序,直接插入排序算法的时间效率越高 最优情况下:时间效率为O(n) 最差情况下:时间复杂度为O(n^2) 空间复杂度:O(1),它是一种稳定的排序算法
- 图示:
- 代码:
Sort.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#define N 10
void InputData(int* d);//输入数据
void PrintData(int* d);//输出数据
void InsertSort(int * d);//直接插入排序
void ShellSort(int *d, int length);//希尔排序
Sort.c
#include "Sort.h"
void InputData(int* d)
{
int i = 0;
printf("输入数据:\n");
for (i = 0; i < N; i++)
{
printf(" d[%d]:", i);
scanf("%d", &d[i]);
printf(" ");
}
printf("\n\n");
}
void PrintData(int* d)
{
int i = 0;
printf("输出数据:");
for (i = 0; i < N; i++)
{
printf("%d ", d[i]);
}
printf("\n\n");
}
void Swap(int* d1, int *d2)
{
assert(d1 && d2);
int tmp = 0;
tmp = *d1;
*d1 = *d2;
*d2 = tmp;
}
//直接插入排序
//假设待排序的记录存放在数组d[0..N-1]中。
//初始时,d[0]自成1个有序区,无序区为R[1.N-1]。
//从i=1起直至i=N-1为止,依次将d[i]插入当前的有序区d[1..N-1]中,
//生成含N个记录的有序区。
void InsertSort(int * d)
{
assert(d);
int i = 0;
int j = 0;
int right = 0;
for (i = 1; i < N; i++)
{
//在原来的数组里操作,比较一次移动一次
right = i;//记录要载入数据的位置,哨兵
for (j = right - 1; j >= 0; j--)
{
if (d[right] < d[j])
{
Swap(&d[right], &d[j]);
}
right--;
}
}
printf("排序成功!\n\n");
}
main.c
#include "Sort.h"
void Test()
{
int d[N] = {15, 45, 23, 78, 63, 5, 23, 58, 31, 10};
/*int d[N];
InputData(d);*/
PrintData(d);
/*InsertSort(d);
PrintData(d);*/
ShellSort(d, sizeof(d)/sizeof(d[0]));
PrintData(d);
}
int main()
{
Test();
system("pause");
return 0;
}
结果:
关于时间复杂度的计算:排序时当数据为非递减有序排列即正序时比较次数为:(n+2)(n-1)/2,反之逆序时,比较次数为(n+4)(n-1)/2,若数据随机,取其平均值为:n^2/4,即时间复杂度为O (n^2)。