> 백엔드 개발 > PHP 튜토리얼 > 일반적인 기본 알고리즘에 대한 참고 사항

일반적인 기본 알고리즘에 대한 참고 사항

WBOY
풀어 주다: 2016-08-08 09:29:05
원래의
1068명이 탐색했습니다.

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

快速排序

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

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

로그인 후 복사

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

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

로그인 후 복사

堆排序

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

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

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

로그인 후 복사

插入排序

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

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

로그인 후 복사

选择排序

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

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

로그인 후 복사

按层打印二叉树

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

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

로그인 후 복사

后序遍历二叉树

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

39

40

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

로그인 후 복사

单链表相关(待完善)

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

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

로그인 후 복사

数组去重

1

2

3

4

5

6

7

8

9

10

11

12

13

14

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

로그인 후 복사

求字符数组全排列

1

2

3

4

5

6

7

8

9

10

11

12

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

로그인 후 복사

二分查找

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

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

로그인 후 복사

字符串反转

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

39

40

41

42

43

44

45

46

47

48

49

50

51

52

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

로그인 후 복사

字符串复制

1

2

3

4

5

6

7

8

<code>void copy(char *s, char *d)

{

    while(*s!='\0'){

        *d++ = *s++;

    }

    *d = '\0';

}

</code>

로그인 후 복사

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

관련 라벨:
원천:php.cn
본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
인기 튜토리얼
더>
최신 다운로드
더>
웹 효과
웹사이트 소스 코드
웹사이트 자료
프론트엔드 템플릿