排序算法

插入排序

直接插入排序

基本思想:
我们将一个待排序序列分为有序区和无序区(一般开始的时候将第一个元素作为有序区,剩下的元素作为无序区),每次将无序区的第一个元素作为待插入记录,按大小插入到前面已经排好的有序区中的适当位置,直到记录全部插入完成为止。(如果待插入的元素与有序序列中的某个元素相等,则将待插入元素插入到相等元素的后面)

二分查找算法百度百科

算法效率O(log<sub>2</sub>n)(对数时间)
输入为一个有序的元素序列,如果要查找的元素包含在列表中,二分查找返回其位置,否则返回null

二分查找的基本思想是将n个元素分成大致相等的两部分,取a[n/2]与x做比较,如果x=a[n/2],则找到x,算法中止;如果x数组a的左半部分继续搜索x,如果x>a[n/2],则只要在数组a的右半部搜索x.

仅当列表是有序的时候,二分查找才是有效的

python实现

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
27
28
29
30
# -*- coding: utf-8 -*-
# binary_search

def binary_search(list_1, item):

low = 0
high = len(list_1)-1

while low <= high:
'''使用 // 整除运算符可以不用int进行类型转换'''
#每次都检查中间的元素
mid = (low + high)/2
guess = list_1[int(mid)]

if guess == item:
return int(mid)#返回所在位置的索引
if guess < item: #猜的数字小了,修改low
low = mid+1
if guess > item: #猜的数字大了,修改high
high = mid-1
return None

def main():

list_2 = [1,2,3,4,5,6,7,8,9]

print(binary_search(list_2, 8))
print(binary_search(list_2, 10))

main()

C++实现

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
27
28
29
30
31
32
33
34
35
36
37
38
#include<iostream>
#include<typeinfo>
using namespace std;

int binary_search(int a[9],int n,int x)//n为元素个数
{
int mid;
int high,low=0;
int guess;

high = n-1;//数组下标从0开始

while(low <= high)
{
mid = (high+low)/2;
guess = a[mid];
if(guess == x)
return mid;
if(guess > x)
high = mid-1;
if(guess < x)
low = mid+1;
}
return -1;
}

int main()
{
int temp;
int a[9] = {1,2,3,4,5,6,7,8,9};

cout<<sizeof(a)/sizeof(int)<<endl;
cout<<typeid(sizeof(a)/sizeof(int)).name()<<endl;
temp = binary_search(a,sizeof(a)/sizeof(int),5);
cout<<temp<<endl;

return 0;
}

类型名获取

使用头文件typeinfo下的typeid(parameter).name()获取类型名



博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本站使用 Material X 作为主题 , 总访问量为 次 。
桂ICP备19000444号