qq_28778507的博客

Sort a linked list in O(n log n) time using constant space complexity. Example 1:Input: 4->2->1->3 Output: 1->2->3->4 Example 2:Input: -1->5->3->4->0 Output: -1->0-&gt...

//生成n个元素的随机数组，每个元素的随机范围为[rangeL,rangeR] int *generateRandomArray(int n, int rangeL, int rangeR){ assert(rangeL<=rangeR); int *arr = new int[n]; srand(time(NULL));//用当前时间用作随机种子的设置 for(int i=0; ...

O(n2)的排序算法编码简单，易于实现，是一些简单场景的首选，反而更有效。 排序过程 template<typename T> void selectionSort(T arr[], int n){ for(int i=0; i<n; i++){ int minIndex=i; for(int j=i+1; j<n; j++) if(arr[j]&l...

O(n2) 以此类推 初版本的插入排序： template<typename T> void insertSort(T arr[], int n){ for(int i=1; int<n; i++){ //因为默认第0个元素已经有序了 //寻找第i个元素合适的插入位置 for(int j=i; j>0 && arr[j]<arr[j

template <typename T> void bubbleSort(T arr[], int n){ for(int i=0;i<n-1;i++){ for(int j=0; j<n-i;j++) if(arr[j]>arr[j+1]) swap(arr[j],arr[j+1]); } }

//将arr[l...mid]和arr[mid...r]两部分进行归并 template<typename T> void _merge(T arr[], int l, int mid, int r) { T aux[r - l + 1]; for (int i = l; i <= r; i++) aux[i - l] = arr[i]; int i = l, j = ...

//arr[l...r]部分进行partition操作 //返回p，使得arr[l...p-1]<arr[p];arr[p+1...r]>arr[p] template<typename T> int _partition(T arr[], int l, int r) { T v = arr[l]; //arr[l+1...j]<v;arr[j+1......

堆和优先队列 什么是优先队列 普通队列：先进先出，后进后出 优先队列：出队顺序和入队顺序无关，和优先级相关 优先队列的主要操作 入队 出队（取出优先级最高的元素） 堆的基本实现 堆中某个节点的值总是不大于其父节点的值（最大堆） 总是一颗完全二叉树（允许最后一层可以不完全，但是必须全都集中在左侧） 0节点为空 parent(i)=i/2parent(i)=i/2parent(i)=i/2 ...