算法

后端 2019年04月18日 13:04 Misaka 0 评论 301 阅读

常见算法

写在这里，以便查阅, 有时间的话在 leetcode 上刷个 100-200 道 easy 和 medium 的题

排序算法

快速排序

快速排序是冒泡排序的改进算法

递归式

左右指针法

void QuickSort(int* array,int left,int right)
{
    assert(array);
    if(left >= right)//表示已经完成一个组
    {
        return;
    }
    int index = PartSort(array,left,right);//枢轴的位置
    QuickSort(array,left,index - 1);
    QuickSort(array,index + 1,right);
}

代码

int PartSort(int* array,int left,int right)
{
    int& key = array[right];
    while(left < right)
    {
        while(left < right && array[left] <= key)
        {
            ++left;
        }
        while(left < right && array[right] >= key)
        {
            --right;
        }
        swap(array[left],array[right]);
    }
    swap(array[left],key);
    return left;
}

非递归式

递归的算法主要是在划分子区间，如果要非递归实现快排，只要使用一个栈来保存区间就可以了。一般将递归程序改成非递归首先想到的就是使用栈，因为递归本身就是一个压栈的过程。

void QuickSortNotR(int* array,int left,int right)
{
    assert(array);
    stack<int> s;
    s.push(left);
    s.push(right);// 后入的 right，所以要先拿 right
    while(!s.empty)// 栈不为空
    {
        int right = s.top();
        s.pop();
        int left = s.top();
        s.pop();

        int index = PartSort(array,left,right);
        if((index - 1) > left) // 左子序列
        {
            s.push(left);
            s.push(index - 1);
        }
        if((index + 1) < right) // 右子序列
        {
            s.push(index + 1);
            s.push(right);
        }
    }
}

二分法

    public static Integer search(int[] a, int x) {
        int low = 0, high = a.length - 1;
//        0 1 2 4 5
        int mid = (low + high) / 2;
        while (a[mid] != x) {
            if(a[mid] > x) {
                high = mid;
            }
            else {
                low = mid;
            }
            mid = (low + high) / 2;
        }
        // 此时 mid 下标的值对 x, 但还不能保证这是最小的下标
        while (a[mid] == x) mid--;
        // 减过头了得加 1
        mid++;
        return mid;
    }

堆排序

斐波那数列

0 1 1 2 3 5 8...

使用递归会导致栈溢出，此处使用尾递归，或者称之为迭代

public static int foo(int n, int x, int y){
    if(n == 0) {
        return x;
    }
    return foo(n - 1, y, x + y);
}
public static void main(String[] args) {
    // F(n) = foo(n, 0, 1);
    foo(n, 0, 1);
}

String 转 double

主要思路是以整数形式分别记录整数部分和小数部分

    public static Double toDouble(String s) {
        if(s == null) {
            return null;
        }
        int len = s.length();
        int I = 0;
        int S = 0;
        int index = -1;
        int smallLen = 0;
        for(int i = 0; i < len; i++) {
            if(index == -1 && s.charAt(i) != '.') {
                if(I != 0) {
                    I *= 10;
                }
                I += (s.charAt(i)-'0');
            }
            else if(index != -1) {
                if(S != 0) {
                    S *= 10;
                }
                S += (s.charAt(i)-'0');
                smallLen++;
            }
            else {
                index = i;
            }
        }
        System.out.println(I);
        System.out.println(S);
        return I + S * Math.pow(10, -smallLen);
    }

算法