一些常见的基础算法(未完待续)
PHP 网络编程技术与实例(曹衍龙)
下载
PHP网络编程技术详解由浅入深，全面、系统地介绍了PHP开发技术，并提供了大量实例，供读者实战演练。另外，笔者专门为本书录制了相应的配套教学视频，以帮助读者更好地学习本书内容。这些视频和书中的实例源代码一起收录于配书光盘中。本书共分4篇。第1篇是PHP准备篇，介绍了PHP的优势、开发环境及安装；第2篇是PHP基础篇，介绍了PHP中的常量与变量、运算符与表达式、流程控制以及函数；第3篇是进阶篇，介绍
快速排序
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;
}
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;
}
堆排序
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;
}
插入排序
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";
}
}
选择排序
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";
}
}
按层打印二叉树
#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);
}
}
后序遍历二叉树
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 < 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"}
求字符数组全排列
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");
二分查找
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;
}
字符串反转
#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);
}
}
字符串复制
void copy(char *s, char *d)
{
while(*s!='\0'){
*d++ = *s++;
}
*d = '\0';
}
以上就介绍了常见基础算法笔记，包括了方面的内容，希望对PHP教程有兴趣的朋友有所帮助。
