常见基础算法笔记
程序员文章站
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教程有兴趣的朋友有所帮助。