各类排序算法总结

时间复杂度(平均时间复杂度)

O(nlog2n) :快速排序、堆排序、归并排序

O(n2):直接插入、直接选择、冒泡排序

O(n1.3):希尔排序


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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
// 快速排序 时间复杂度O(nlog2n)
void QucikSort(int R[],int l,int r)
{
    int temp=R[l],i=l,j=r;
    while(i!=j)
    {
        while(i<j&&R[i]>temp) --j;//从后之前找小于中心点
        if(i<j)
        {
            R[i]=R[j];
            i++;
        }
        while(i<j&&R[i]<temp) ++i;//从前往后找大于中心点的值
        if(i<j)
        {
            R[j]=R[i];
            j--;
        }
    }
    R[i]=temp;
    QuickSort(R,l,i-1);
    QuickSort(R,i+1,r);
}

//堆排序 时间复杂度 O(nlog2n)
void heapSort(int R[],int n)
{
    int i;
    int temp;
    for(i=n/2;i>=1;--i)//建立初始堆
        Sift(R,i,n);
    for(i=n;i>=2;--i)//进行n-1次循环完成堆排序
    {
        temp=R[1];
        R[1]=R[i];
        R[i]=temp;
        Sift(R,l,i-1)//在减少了1个元素的无序序列中进行调整
    }
}
//本函数完成对在数组R[low]到R[high]范围内对在位置low上的节点进行调整呢过
void Sift(int R[],int low ,int high)
{
    int i=low,j=2*i;
    int temp=R[i];
    while(j<=high)
    {
        if(j<high&&R[j]<R[j+1])//找到左右孩子最大的节点
            ++j;
        if(temp<R[j])
        {
            R[i]=R[j]
            i=j;
            j=2*i;
        }
        else
            break;
    }
    R[i]=temp;
}

// 二路归并排序 时间复杂度 O(nlog2n)

// 直接插入排序 时间复杂度 O(n2)
void insertSort(int R[],int n)
{
    int temp,i,j;
    for(i=2;i<=n;++i)
    {
        temp=R[i];//待插入元素
        j=i-1;//从后往前找插入点
        while(j>=1&&temp<R[j])
        {
            R[j+1]=R[j];//插入点后的元素后移
            --j;
        }
        R[++j]=temp;//++j修正while循环条件
    }
}

// 直接选择排序 时间复杂度 O(n2)
void selectSort(int R[],int n)
{
    int i,j,k;
    int temp;
    for(i=1;i<=n;++i)
    {
        k=i;
        for(j=i+1;j<=n;++j)
        {
            if(R[k]>R[j]) k=j;
        }
        temp=R[i];
        R[i]=R[k];
        R[k]=temp;
    }
}

// 冒泡选择排序 时间复杂度 O(n2)
void bubbleSort(int R[],int n)
{
    int i,j,flag;
    int temp;
    for(i=n;i>=2;--i)
    {
        flag=0;
        for(j=2;j<=i;++j)
        {
            if(R[j-1]>R[j])
            {
                temp=R[j];
                R[j-1]=temp;
                flag=1;//发生交换
            }
        }
        if(flag==0) return;
    }
}

外网访问通过远程桌面访问校园内(端口受限)主机

今天,学校的网站又有修改,同样是小伙伴把程序传给我,我在学校内网操作~~。

突然感觉好麻烦,虽然已经很多次了。灵机一动,我既然通过我控制的服务器,都可以绕过锐捷为什么不可以给小伙伴开个代理,通过代理操作呢?

想法是好的,可是遇到了几个问题:

1.windows远程桌面不支持代理(PS:我还是Linux的粉)

2.校园网禁止外网访问

3.开启远程桌面提示协议错误

 

解决方案:

1.查了一些资料后发现这个软件可以解决。SocksCap64是由Taro Labs开发的一款免费的应用程序外壳代理软件. SocksCap64可以使Windows应用程序通过SOCKS代理服务器来访问网络而不需要对这些应用程序做任何修改, 即使某些本身不支持SOCKS代理的应用程序通过SocksCap64之后都可以完美的实现代理访问. 例如: Web Browsers, IM程序, FTP Clients, e-mail programs or games.

https://www.sockscap64.com/

2.代理服务器是安装在校园网内一台服务器上,安装的是ccpory8.0这个软件非常不错。

http://www.ccproxy.com/

问题是默认socket端口是1080,经过测试(PS:因为在内网,用手机走流量测的~~)发现1080这个端口被学校封了。查了一些资料发现学校除了80端口还开了443端口,哈哈,改成443发现OK啦!

3.当然开启远程桌面是客户机加上外壳代理软件通过socket5协议可访问的443端口连接到学校的一台服务器,然后与内网的另一台主机通信。但是通过这种方式链接时会报协议错误,经过几台机器测试,发现是由于服务器的网络配置引起的,百度有很多解决方案,主要是添加一些协议使远程桌面允许socket协议通信!

配置php拓展memcached(xampp集成环境)

重新安装了memcached,把配置记录一下

下载解压、进入目录

首先下载 memcached-2.2.0 、 libmemcached-1.0.18

先安装libmemcached-1.0.18 后安装

进入libmemcached下载后目录解压、进入解压后的目录

./configure -prefix=/opt/lampp/libmemcached –with-memcached(安装位置/opt/lampp/libmemcached)

make && make install(建议分两步执行)

进入memcached下载后目录解压、进入解压后的目录

/opt/lampp/bin/phpize (xampp默认位置、生成configure文件)

./configure –with-php-config=/opt/lampp/bin/php-config –with-libmemcached-dir=/opt/lampp/libmemcached
(php-config路径不知道 采用 find / -name php-config 查找位置、libmemcached刚刚的安装位置)

会报一个错误configure: error: no, sasl.h is not available. Run configure with –disable-memcached-sasl to disable this check

按照提示解决方法:
./configure –with-php-config=/opt/lampp/bin/php-config –with-libmemcached-dir=/opt/lampp/libmemcached –disable-memcached-sasl

make && make install

Installing shared extensions: /opt/lampp/lib/php/extensions/no-debug-non-zts-20131226/(复制路径)

在php.ini(xampp默认路径/opt/lampp/etc/php.ini)中末尾添加

extension=/opt/lampp/lib/php/extensions/no-debug-non-zts-20131226/memcached.so

保存重启服务

Cannot find autoconf

Configuring for:
PHP Api Version: 20131106
Zend Module Api No: 20131226
Zend Extension Api No: 220131226
Cannot find autoconf. Please check your autoconf installation and the
$PHP_AUTOCONF environment variable. Then, rerun this script.

解决方案:
sudo apt-get install autoconf

configure: error: xml2-config not found. Please check your libxml2 installation.

切换PHP版本,编译安装时出现从错误。

提示libxml2没有安装

dpkg -s libxml2 后提示

Package: libxml2
Status: install ok installed

继续研究了一下发现

libxml2-devel 是开发库,包含编译使用 libxml2 所需要的头文件、静态库和一些相关工具。Ubuntu给单独拆出去了。

解决方案:

apt-get install libxml2-dev

ubuntu上安装zsh

今天想美化一下Ubuntu,装了一个zsh

安装步骤:

1.安装zsh、Git和wget:

1
sudo apt-get install zsh git wget

2.安装oh-my-zsh:

1
wget --no-check-certificate https://github.com/robbyrussell/oh-my-zsh/raw/master/tools/install.sh -O - | sh

3.把默认的bash切换到zsh

1
chsh -s /bin/zsh

4.安装完zsh后,在/home下会有一个名为.zshrc的隐藏文件,如果你还想更个性一些,可以修改配置文件
5.重启后就可以看到zsh是不是比bash好看,嘿嘿。

规范

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
//线性表的单链表的存储结构
typedef struct LNode{//结点类型
    ElemType data;
    struct LNode *next;
} LNode,*LinkList;

//线性表的双向链表的存储结构
typedef struct DuLNode{
    ElemType data;
    struct DuLNode *prior;
    struct DuLNode *next;
} DuLNode *DuLinkList;

//一个带头结点的线性链表类型定义如下:
typedef struct LNode{//结点类型
    ElemType data;
    struct LNode *next;
} *Link,*Position;

typedef struct{
    Link head,tail;//分别指向线性链表的头结点和最后一个结点
    int len;//指示线性链表中数据元素的个数
}LinkList;


//p46 栈相关操作
InitStack(S);//构造一个空栈
Push(S,e);//插入元素e为新的栈顶元素
Pop(S,e);//若栈不空,则删除S的栈顶元素,用e返回其值

StackEmpty(S)//若栈S为空栈则返回TRUE,否则反回FALSE
StackLength(S)//返回S的元素个数,即栈的长度
GetTop(S,e);//若栈不空,则用e返回S的栈顶元素

//p64 队列相关操作
InitQueue(Q);//构造一个空队列Q
EnQueue(Q,e);//插入元素e为Q的新的队尾元素
DeQueue(Q,e);//若队列不空,则删除Q的队头元素,用e返回其值

QueueEmpty(Q);//若队列为空返回TRUE否则返回FALSE
QueueLength(Q);//返回队列元素个数,即为队列的长度
GetHead(Q,e);//若队列不空,用e返回Q的队头元素

2006-一-4

1
2
3
4
5
6
7
8
9
int main()
{
    char *p[2][3]={"Hello","world","student","computer","end","the"};
    printf("%c\n",***(p+1));
    printf("%c\n",**p[0]);
    printf("%c\n",(*(*(p+1)+1))[2]);
    printf("%c\n",*(p[1][2]+1));
    printf("%s\n",**(p+1));
}

模拟一-三-3

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
#include<stdio.h>
int main()
{
  char i,j,k;//i是A的对手,j是B的对手,k是C的对手
  for (i = 'x'; i <= 'z'; i++)
  {
    for (j = 'x'; j <= 'z'; j++)
    {
      if (i != j)
      {
        for (k = 'x'; k <= 'z'; k++)
        {
          if (i != k&&j != k)
          {
            if (i != 'x'&&k != 'x'&&k != 'z')
            {
              printf("A——%c\nB——%c\nC——%c\n", i, j, k);
            }
          }
        }
      }
    }
  }
  return 0;
}

二叉树(先、中、后)非递归遍历实现

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
//先序非递归遍历
void preOrder(BiTree *root)
{
   BiTree *stack[maxSize],top=0;//定义一个栈
   BiTree *p=root;//p工作指针
   
   while(p!=NULL || top>0)//此处当p==NULL时,继续出栈
   {
       while(p!=NULL)
       {
           printf("%d",p->data);//仅仅与中序遍历输出位置不同
           stack[++top]=p;
           p=p->lchild;//指向左孩子
       }
       if(top>0)//栈不空,此时p==NULL
       {
           p=stack[top--];//出栈
           p=p->rchild;//指向右孩子
       }
   }
}


//中序非递归遍历
void inOrder(BiTree *root)
{
   BiTree *stack[maxSize],top=0;//定义一个栈
   BiTree *p=root;//p工作指针
   
   while(p!=NULL || top>0)//此处当p==NULL时,继续出栈
   {
       while(p!=NULL)
       {
           stack[++top]=p;
           p=p->lchild;//指向左孩子
       }
       if(top>0)//栈不空,此时p==NULL
       {
           p=stack[top--];//出栈
           printf("%d",p->data);//仅仅与先序遍历输出位置不同
           p=p->rchild;//指向右孩子
       }
   }
}


//后序非递归遍历

void afterOrder(BiTree *root)
{
   struct Tree
   {
       BiTree *bt;
       int tag;//1-第一次访问(左孩子)、2-非第一次访问(右孩子)
   };
   
   Tree stack[maxSize],top=0;//定义一个栈
   Tree p; p.bt=root; p.tag=1;//根结点入栈
   
   while(p!=NULL || top>0)//此处当p==NULL时,继续出栈
   {
       while(p.bt!=NULL)
       {
           ++top;
           stack[top].bt=p;
           stack[top].tag=1;
           p.bt=p.bt->lchild;//指向左孩子
       }
       if(top>0)//栈不空,此时p==NULL
       {
           p=stack[top--];//出栈
           if(p.tag==1)//只访问过一次
           {
               p.tag=2;//标记第二次访问
               stack[++top]=p;
               
               p.bt=p.bt->rchild;
           }
           else
           {
               printf("%d",p->data);
               p.bt=NULL; //令下一元素直接出栈,
                         //可省略,但是需要在循环判断一次
           }
       }
   }
}