欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  后端开发

常见基础算法笔记

程序员文章站 2022-05-12 09:06:02
...
一些常见的基础算法(未完待续)

快速排序

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]  i)
        {
            arr[j] = arr[i];
            j--;
        }
    }
    //i=j时代表所有比value大的值都到了右边,比value小的到了左边
    arr[i] = value;
    return i;
}
void quickSort(int arr[], int left, int right)
{
    if (left 

堆排序

include 
//假设第i个节点的左右子树已经是最大堆,加入第
//i个节点后重新调整堆
void heapAdjust(int arr[], int i, int size)
{
    int l = 2*i;
    int r = l+1;
    int max = i;
    if(iarr[max])
        max = l;
    if(rarr[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++

插入排序

void insertSort()
{
    int arr[10] = { 1, 34, 5, 6, 8, 12, 5, 9, 345, 0 };
    int n = 10;
    cout = 0 && arr[j] > temp; j--)
        {
            arr[j + 1] = arr[j];
        }
        //最后将最初的arr[i]值放到空出的位置
        arr[j + 1] = temp;
    }

    for (int i = 0; i 

选择排序

void selectSort()
{
    int arr[10] = { 1, 34, 5, 6, 8, 12, 5, 9, 345, 0 };
    int n = 10;
    cout 

按层打印二叉树

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

后序遍历二叉树

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;
            }
        }
    }
}

单链表相关(待完善)

//单链表反转
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);
    }
}

数组去重

function cleanArray(arr){
    var hash = {};
    var len = arr.length;
    for (var i = 0; i 

求字符数组全排列

function permute(strpre, str)
{
  if(str.length==0){
    console.log(strpre);
  }else{
        var l = str.length;
    for(var i=0;i

二分查找

int binarySearch(int arr[], int l, int r, int k)
{
    while(lk) 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;
}

字符串反转

#include 
#include 
void reverse1(char *s)
{
    char *p1,*p2;
    char c;
    p1 = s;
    p2 = s+strlen(s)-1;
    while(p11){
        char c = *s;
        *s = *(s+tail-1);
        *(s+tail-1) = c;
        reverse4(s+1,tail-2);
    }
}

字符串复制

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

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