排序算法大概可以分为五种:插入排序,交换排序,选择排序,归并排序和计数排序。
这篇文章讨论一下,插入排序中的直接插入和折半插入。
排序,归根结底它的作用是对表中的记录进行一个有序的归纳。
一个排序,基本上都需要两个步骤:一是找到要插入的位置,二是移动记录。
先来看一下插入排序的算法:
/直接插入排序/ void Straight_Insert_Sort(Sqlist &L) { int j; for (int i = 2; i <= L.length; i++) { L.R[0] = L.R[i]; for (j = i - 1; L.R[j].key > L.R[0].key; j--) { L.R[j + 1] = L.R[j]; } L.R[j + 1] = L.R[0]; } } 我们假定记录中的第一个关键字为有序,现在,需要将从第二个关键字开始的所有记录插入到表中。
下面解释一下上述代码:
从第二个数开始循环插入每一个数字,
将L.R[0]定位哨兵,当需要被插入的数字出现时,将它的值赋给哨兵。
这里利用到i之前的记录一定是有序的,所以循环比较哨兵与前面记录的值,从第i-1个数开始,依次往后移动。
直到哨兵与所比较的值相等时,终止,这是一个稳定排序。
下面来看一下折半插入的算法:
/*折半插入排序*/
void B_Insert_Sort(Sqlist &L)
{
int i, j, low, mid, high;
for (i = 2; i <= L.length; i++)
{
L.R[0] = L.R[i];
low = 1; high = i - 1;
while (low <= high)
{
mid = (low + high) / 2;
if (L.R[0].key<L.R[mid].key)
{
high = mid - 1;
}
else
{
low = mid + 1;
}
}//查找出应该插入的位置
for (j = i - 1; j>=high+1; j--)
{
L.R[j + 1] = L.R[j];
}
L.R[high + 1] = L.R[0];
}
}
与上述同理,循环插入第二个数开始之后的关键字。
不同的地方是,这里利用折半查找,找到,插入记录的位置,需要注意的是,为什么high+1就是应该插入关键字的位置呢?
我们可以这样想:while的最后,一定会出现low=high的情况,此时,如果哨兵的值小于mid,那么high=mid-1,实际上,mid前面值都比哨兵小,后面的值都比哨兵大,所以此时哨兵应该就在mid的位置。同理,可以得知当哨兵的值大于mid时。
完整代码:
// sort_solution.cpp: 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include "stdlib.h"
#include "malloc.h"
#define TRUE 1
#define ERROR -1
#define OVERFLOW -2
#define Max_Size 200
typedef int KeyType;
typedef struct
{
KeyType key;//关键字类型
//int Rec;//记录类型
}RecType;
typedef struct Sqlist
{
int length;
RecType R[Max_Size];//这里没有加一的原因是,我的length远远小于我的Max_Size
}Sqlist;//表类型
void Create(Sqlist &L)
{
L.length = 10;//默认表记录长度
L.R[0].key = 0;
for (int i=1 ;i<=L.length;i++)
{
printf("请输入第%d条记录的关键字:",i);
scanf("%d",&L.R[i].key);
getchar();
}
}
void Travel(Sqlist L)
{
for (int i = 1; i <= L.length; i++)
{
printf("%d\r\n",L.R[i].key);
}
}
/*直接插入排序*/
void Straight_Insert_Sort(Sqlist &L)
{
int j;
for (int i = 2; i <= L.length; i++)
{
L.R[0] = L.R[i];
for (j = i - 1; L.R[j].key > L.R[0].key; j--)
{
L.R[j + 1] = L.R[j];
}
L.R[j + 1] = L.R[0];
}
}
/*折半插入排序*/
void B_Insert_Sort(Sqlist &L)
{
int i, j, low, mid, high;
for (i = 2; i <= L.length; i++)
{
L.R[0] = L.R[i];
low = 1; high = i - 1;
while (low <= high)
{
mid = (low + high) / 2;
if (L.R[0].key<L.R[mid].key)
{
high = mid - 1;
}
else
{
low = mid + 1;
}
}//查找出应该插入的位置
for (j = i - 1; j>=high+1; j--)
{
L.R[j + 1] = L.R[j];
}
L.R[high + 1] = L.R[0];
}
}
int main()
{
Sqlist L;
Create(L);
//Straight_Insert_Sort(L);
B_Insert_Sort(L);
Travel(L);
return 0;
}
全文结束,欢迎在评论区讨论~