排序算法

yeshan333

文章首发于：2018年11月20日

Algorithm

插入排序

直接插入排序

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

插入排序

二分查找

yeshan333

文章首发于：2018年11月19日

Algorithm

CPP

Algorithm

Python

二分查找算法百度百科

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

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

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

python实现

# -*- 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++实现

#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()获取类型名

ACM入门（占个位）

yeshan333

文章首发于：2018年10月2日

Algorithm

CPP

Algorithm

A+B for Input-Output Practice(using C++)

1.

Problem Description
Your task is to Calculate a + b. Too easy?! Of course! I specially designed the problem for acm beginners. You must have found that some problems have the same titles with this one, yes, all these problems were designed for the same aim
Input
The input will consist of a series of pairs of integers a and b, separated by a space, one pair of integers per line.
Output
For each pair of input integers a and b you should output the sum of a and b in one line, and with one line of output for each line in input.
Sample Input
1 6 1 20
Sample Output
7 21