最近为了准备面试，看到许多帖子说考这考那的，我总了一些出现频率比较高的算法。
希望能帮到大家，当然也为以后复习做准备，免得再次找来找去的，另外大家也可多提提意见，我再梳理梳理。
一、常见排序算法：
1、快速排序：例如，若对100个数排序，则 QuickSort(array,0,99)，另外为了整体美观，swap 函数就不写，相信大家都会。
void QuickSort(int num[], int start,int end){ if(start >= end){ return; } int base = num[start]; int i = start; int j = start + 1; while(j <= end){ if(num[j] < base){ i++; swap(num,i,j); } j++; } swap(num,start,i); QuickSort(num,start,i-1); QuickSort(num,i+1,end); }
2、归并排序：例如，若对100个数排序，则 QuickSort(array,0,99);
void Merge(int num[],int start, int middle, int end){ int ln = middle - start + 1; int rn = end - middle; int *left_num = new int[ln]; //记得释放内存，避免内存泄漏 int *right_num = new int[rn]; //记得释放内存，避免内存泄漏 for(int i = 0; i < ln; i++){ left_num[i] = num[start+i]; } for(int j = 0; j < rn; j++){ right_num[j] = num[middle+j+1]; } int i = 0,j = 0,k = start; while(i < ln && j < rn){ if(left_num[i] <= right_num[j]){ num[k++] = left_num[i++]; }else{ num[k++] = right_num[j++]; } } while(i < ln){ num[k++] = left_num[i++]; } while(j < rn){ num[k++] = right_num[j++]; } delete[] left_num; delete[] right_num; } void MergeSort(int num[],int start, int end){ if(start >= end){ return; } int middle = (start + end) / 2; MergeSort(num,start,middle); // 拆分 MergeSort(num,middle+1,end); // 拆分 Merge(num,start,middle,end); // 归并 }
3、堆排序(升序)：例如，若对100个数排序，则 HeapSort(array,100); swap 函数同样省略。
void HeapAdjust(int num[], int i, int length){ for(int j = 2*i + 1; j < length; j = 2*j + 1){ if(j + 1 < length && num[j] < num [j+1]){ j++; } if(num[j] > num[i]){ swap(num,i,j); i = j; } } } void HeapSort(int num[], int length){ for(int i = length / 2 - 1; i >= 0; i--){ // 构建初始堆 HeapAdjust(num,i,length); } for(int i = length - 1; i > 0; i--){ swap(num,0,i); // 利用堆顶性质，交换堆顶与末尾元素 HeapAdjust(num,0,i); } }
二、二叉树常用算法：膜拜一下 大佬
三、单链表常用算法：再膜拜一下 大佬
原文：https://www.cnblogs.com/M-Anonymous/p/13039515.html