算法打卡_第一天：顺序查找+直接插入排序

活动地址：CSDN21天学习挑战赛

学习的最大理由是想摆脱平庸，早一天就多一份人生的精彩；迟一天就多一天平庸的困扰。

顺序查找

基本原理

对于任意一个序列以及一个给定的元素，将给定元素与序列中元素依次比较，直到找出与给定关键字相同的元素，或者将序列中的元素与其都比较完为止。
查找成功则返回位置，查找失败则返回错误值（-1或者自己设定的值）。

代码实现

int sq_search(keytype keyp[],int n,keytype key)
{
int i;
for(i=0; i<n; i++)
if(key[i] == key)
return i;//查找成功
return -1;//查找失败
}
1
2
3
4
5
6
7
8

优缺点

1、缺点：查找效率较低，特别是当待查找集合中元素较多时，不推荐使用顺序查找。
2、优点：算法简单而且使用面广。
1)对表中记录的存储没有任何要求，顺序存储和链接存储均可。
2)对表中记录的有序性也没有要求，无论记录是否按关键码有序均可。

直接插入排序

基本思想

每一趟将一个待排序的记录，按其关键字的大小插入到已经排好序的一组记录的适当位置上，直到所有待排序记录全部插入为止。

待排序记录 R1，R2，… ，Rn–1, Rn
第一步：R1
第二步：(R1 ), R2
第三步：(R1 , R2), R3
……
第 j 步：(R1，R2，… ，Rj–1), Rj
……
第 n 步: (R1，R2，… ，Rn–1), Rn．
例：j=5
原有序表中关键词比Rj大的记录数：dj
比较次数：dj+1 移动次数： dj+2

程序实现

#include
using namespace std;
int main()
{
    int a[]={98,76,109,34,67,190,80,12,14,89,1};
    int k=sizeof(a)/sizeof(a[0]);
    int i,j;
    for(i=1;i<k;i++)//循环从第2个元素开始
    {
        if(a[i]<a[i-1])
        {
            int temp=a[i];
            for(j=i-1;j>=0 && a[j]>temp;j--)
            {
                a[j+1]=a[j];
            }
            a[j+1]=temp;//此处就是a[j+1]=temp;
        }
    }
    for(int f=0;f<k;f++)
    {
        cout<<a[f]<<"  ";
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26