Notes on common basic algorithms

一些常见的基础算法(未完待续)

快速排序

<code>int partition(int left,int right,int arr[])
{
    int i = left;
    int j = right;
    int value = arr[left];
    while (j > i)
    {
        //从右边j开始找到一个比value小的值
        while (j > i && arr[j] >= value)
            j--;
        if (j > i)
        {
            arr[i] = arr[j];
            i++;
        }

        //从左边i开始找到一个比value大的值
        while (j > i && arr[i] <= value)
            i++;
        if (j > i)
        {
            arr[j] = arr[i];
            j--;
        }
    }
    //i=j时代表所有比value大的值都到了右边，比value小的到了左边
    arr[i] = value;
    return i;
}
</code>

<code>void quickSort(int arr[], int left, int right)
{
    if (left < right)
    {
        int i = partition(left, right,arr);
        quickSort(arr, left, i - 1);
        quickSort(arr, i + 1, right);
    }
}

void quickSortTest()
{
    int arr[10] = { 1, 34, 5, 6, 8, 12, 5, 9, 345, 0 };
    int n = 10;
    cout << "==================quickSort====================" << endl;
    for (int i = 0; i <= n - 1; i++)
    {
        cout << arr[i] << "\t";
    }
    cout << endl;

    quickSort(arr, 0, 9);

    for (int i = 0; i <= n - 1; i++)
    {
        cout << arr[i] << "\t";
    }
    cout << endl;
}
</code>

堆排序

<code>include <stdio.h>
//假设第i个节点的左右子树已经是最大堆，加入第
//i个节点后重新调整堆
void heapAdjust(int arr[], int i, int size)
{
    int l = 2*i;
    int r = l+1;
    int max = i;
    if(i<=(size/2)){  //非叶子节点才需调整
        if(l<=size&&arr[l]>arr[max])
        max = l;
    if(r<=size&&arr[r]>arr[max])
        max = r;
    if(max!=i){
        arr[max] ^= arr[i];
        arr[i] ^= arr[max];
        arr[max] ^= arr[i];
        //int temp = arr[i];
        //arr[i] = arr[max];
        //arr[max] = temp;
        heapAdjust(arr, max, size);
    }
    }
}
//建立最大堆
void buildHeap(int arr[], int heapsize)
{
    int middle = heapsize/2;
    for(int i=middle;i>=1;i--)
        heapAdjust(arr,i,heapsize);
}
//堆排序
void heapSort(int arr[], int size)
{
    buildHeap(arr,size);
    for(int i=size;i>=2;i--){
        //arr[i] ^= arr[1];
    //arr[1] ^= arr[i];
    //arr[i] ^= arr[1];
    arr[i] += arr[1];
    arr[1] = arr[i]-arr[1];
    arr[i] = arr[i]-arr[1];
    heapAdjust(arr,1,i-1);
    }
}
void printArr(int arr[], int n)
{
    int i = -1;
    while(i++<n-1)
        printf("%d\t",arr[i]);
    printf("\n");
}

int main(int argc, char **argv)
{
    int arr[9] = {0,1,3,45,2,56,345,6,778};
    printArr(arr,9);
    heapSort(arr,8);
    printArr(arr,9);
    return 0;
}
</code>

插入排序

<code>void insertSort()
{
    int arr[10] = { 1, 34, 5, 6, 8, 12, 5, 9, 345, 0 };
    int n = 10;
    cout << "==================insertSort====================" << endl;
    for (int i = 0; i <= n - 1; i++)
    {
        cout << arr[i] << "\t";
    }
    cout << endl;

    for (int i = 1; i <= n - 1; i++)
    {
        int j;
        int temp = arr[i];
        //内循环将已排序的且比arr[i]大的往前挪
        for (j = i - 1; j >= 0 && arr[j] > temp; j--)
        {
            arr[j + 1] = arr[j];
        }
        //最后将最初的arr[i]值放到空出的位置
        arr[j + 1] = temp;
    }

    for (int i = 0; i <= n - 1; i++)
    {
        cout << arr[i] << "\t";
    }
}
</code>

选择排序

<code>void selectSort()
{
    int arr[10] = { 1, 34, 5, 6, 8, 12, 5, 9, 345, 0 };
    int n = 10;
    cout << "==================selectSort====================" << endl;
    for (int i = 0; i <= n - 1; i++)
    {
        cout << arr[i] << "\t";
    }
    cout << endl;

    for (int i = 0; i <= n - 2; i++)
    {
        int key = i;
        //内循环找到第i大的值的下标
        for (int j = i + 1; j <= n - 1; j++)
        {
            if (arr[j] < arr[key])
            {
                key = j;
            }
        }
        int value = arr[i];
        arr[i] = arr[key];
        arr[key] = value;
    }

    for (int i = 0; i <= n - 1; i++)
    {
        cout << arr[i] << "\t";
    }
}
</code>

按层打印二叉树

<code>#include <iostream>
Queue q = new Queue();
void printBinaryTree(Node *n)
{
    q.put(n);
    Node *next = NULL;
    while(NULL!=(next=q.get()))
    {
        if(next->val!=NULL)
        std::cout<<next->value;
        if(next->left!=NULL)
            q.put(next->left);
        if(next->right!=NULL)
            q.put(next->right);
    }
}
</code>

后序遍历二叉树

<code>void postorder(Node root)
{
    if(root == NULL)
        return;
    postorder(root->left);
    postorder(root->right);
    visit(root);
}

void postOrder(Node root)
{
    Stack stack = new Stack();
    Node tmp = root;

    while(tmp!=NULL || !stack.empty())
    {
        if(tmp!=NULL)
        {
            stack.push(tmp,"left");
            tmp = tmp->left;
        }
        else
        {
            s = stack.pop();
            tmp = s.tmp;
            tag = s.tag;
            if(tag=="right")
            {
                visit(tmp);
                tmp = NULL;
            }
            else
            {
                stack.push(tmp,"right");
                tmp = tmp->right;
            }
        }
    }
}
</code>

单链表相关(待完善)

<code>//单链表反转
void reverse1(node **head)
{
    node *temp;
    node *op;
    temp = *head;
    op = temp->next;
    (*head)->next = NULL;
    while(op)
    {
        //保存原始op的下一个
        temp = op->next;
        //拆开链表
        op->next = *head;
        //移动head
        *head = op;
        //移动op
        op = temp;
    }
}

void reverse2(node **head)
{
    //使用栈先进后出
}

//反向打印单链表
void reversePrint(node *head)
{
    if (head->next != NULL)
    {
        reversePrint(head->next);
        printf("%d\n",head->next->data);
    }
}
</code>

数组去重

<code>function cleanArray(arr){
    var hash = {};
    var len = arr.length;
    for (var i = 0; i < len; i++) {
        if(undefined == hash[arr[i]])
            hash[arr[i]] = arr[i];
    };
    return hash;
}
//testcase
var arr = [1,2,3,'1','3',45,123,2,3,45,9,9,"test","fadsa","test"];
console.log(cleanArray(arr));
//output Object {1: 1, 2: 2, 3: 3, 9: 9, 45: 45, 123: 123, test: "test", fadsa: "fadsa"}
</code>

求字符数组全排列

<code>function permute(strpre, str)
{
  if(str.length==0){
    console.log(strpre);
  }else{
        var l = str.length;
    for(var i=0;i<l;i++)
      permute(strpre+str[i], str.slice(0,i)+str.slice(i+1,l));
  }
}
    permute("", "abcd");
</code>

二分查找

<code>int binarySearch(int arr[], int l, int r, int k)
{
    while(l<=r){
        int m = l+(r-l)/2;
        if(arr[m]==k) return m;
        if(arr[m]>k) r = m+1;
        else l = m-1;
    }
    return -1;
}
int binarySearch1(int arr[], int l, int r, int k)
{
    if(r>=l){
        int m = l+(r-l)/2;
        if(arr[m]==k) return m;
        if(arr[m]>k) binarySearch1(arr, l, m-1, k);
        else binarySearch1(arr, m+1, r, k);    
    }   
    return -1;
}
</code>

字符串反转

<code>#include <stdio.h>
#include <string.h>
void reverse1(char *s)
{
    char *p1,*p2;
    char c;
    p1 = s;
    p2 = s+strlen(s)-1;
    while(p1<p2){
        c = *p1;
    *p1 = *p2;
    *p2 = c;
    p1++;
    p2--;
    }
}
void reverse2(char *s)
{
    char *p1,*p2;
    p1 = s;
    p2 = s+strlen(s)-1;
    while(p1<p2){      //此处用异或交换一定p1!=p2
    *p2 ^= *p1;
    *p1 ^= *p2;
    *p2 ^= *p1;
    p1++;
    p2--;
    }
}
void reverse3(char *s)
{
    char *p1,*p2;
    p1 = s;
    p2 = s+strlen(s)-1;
    while(p1<p2){      
    *p1 += *p2;
    *p2 = *p1-*p2;
    *p1 = *p1-*p2;
    p1++;
    p2--;
    }
}
void reverse4(char *s, int tail)
{
    if(tail>1){
        char c = *s;
        *s = *(s+tail-1);
        *(s+tail-1) = c;
        reverse4(s+1,tail-2);
    }
}
</code>

字符串复制

<code>void copy(char *s, char *d)
{
    while(*s!='\0'){
        *d++ = *s++;
    }
    *d = '\0';
}
</code>

以上就介绍了常见基础算法笔记，包括了方面的内容，希望对PHP教程有兴趣的朋友有所帮助。