算法

非递归式快排模板：

  1. void quick_sort(int q[], int l, int r)
  2. void quick_sort(vector<int> q, int l, int r)
  3. {
  4.     if (l >= r) return;
  5.     stack<int> stk;
  6.     stk.push(l), stk.push(r); // 将 left 和 right两个元素指针压进栈里；
  7.     while (stk.size())
  8.     {
  9.         int rr = stk.top();
  10.         stk.pop(); // poll() 操作；
  11.         int ll = stk.top();
  12.         stk.pop(); //取出并推出左右指针；
  13.         if (ll < rr)
  14.         {
  15.             int i = ll - 1, j = rr + 1, x = q[ll + rr >> 1];  // 将中间元素取做；            
  16.             while (i < j)
  17.             {
  18.                 do ++i; while (q[i] < x); //对元素的移动会优先执行； 
  19.                 do --j; while (q[j] > x);  // 略过符合增序的两端元素；
  20.                 if (i < j) swap(q[i], q[j]); // 交换不符合两端切分的元素；
  21.             }            
  22.             stk.push(ll), stk.push(j);  // 依次压入左，中左，中右，右；
  23.             stk.push(j + 1), stk.push(rr);
  24.         }
  25.      // 下一次循环会优从右半边到左半边，因为取值的时候会先取右边，所以压栈的时候要先从左边压到右边；
  26.     }
  27. }

使用C++ 的 STL 库排序：

  1. void quick_sort(int q[], int n)
  2. {
  3.     sort(q, q+n);
  4. }

归并算法模板：

  1. using namespace std;
  2. void merge (vector<int> &nums, int l1, int r1, int l2, int r2 ) {
  3.     int i = l1, j = l2;
  4.     vector<int> tmp(nums. size() );
  5.     int index=0;
  6.     while(i<=r1 && j<=r2){
  7.     if(nums[i]<=nums[j]){
  8.     tmp[index++] = nums[i++];
  9. }else{
  10.     tmp[index++] = nums[j++];
  11.     }
  12. }
  13. while(i <= r1)
  14.     tmp[index++]=nums[i++];
  15. while(j <= r2)
  16.     tmp[index++]=nums[j++];
  17. for(inti=0; i<index; i++){
  18.     nums[l1+i]=tmp[i];
  19.     }
  20. }
  21. void mergeSort(vector<int> &nums, int left, int right){
  22.     if(left < right){
  23.     int mid = (left+right)/2;
  24.     mergeSort(nums, left, mid);
  25.     mergeSort(nums, mid+1, right);
  26.     merge(nums, left, mid, mid+1, right);
  27.     }
  28. }

堆排序

  1. using namespace std;
  2. void adjust(vector<int> &nums, int i, int n){// i为待调整的节点，n为nums数组元素的个数，从上往下调整
  3. int j = 2*i + 1;// 左子节点
  4. while(j<n){
  5.    if(j+1 < n && nums[j+1] > nums[j])
  6.         j++;// 比较左右孩子谁更大
  7.     if(nums[j] < nums[i])
  8.         break;// 都比父节点小就停止
  9.     else{
  10.         swap(nums[i],nums[j]);
  11.         i = j;// 继续往下调整
  12.         j= 2*i + 1;
  13.         }
  14.     }
  15. }
  16. void HeapSort(vector<int> &nums){
  17.     int n= nums.size();
  18.     for(int i=n/2-1; i>=0; i--){// 从第一个非叶子节点开始（从下往上看第一个）
  19.          adjust(nums ,i,n);
  20.     }
  21.     for(int i=n-1; i>=1; i--){
  22.               swap(nums[0], nums[i]);// 交换堆顶和最末一个元素
  23.               adjust(nums,0,i);// 将最末一个元素去除，再进行调整
  24.      }
  25. }

素数筛

  1. /*
  2.     |埃式筛法|
  3.     |快速筛选素数|
  4. */
  5. int prime[maxn];  
  6. bool is_prime[maxn];
  8. int sieve(int n){
  9.     int p = 0;
  10.     for(int i = 0; i <= n; ++i)
  11.         is_prime[i] = true;
  12.     is_prime[0] = is_prime[1] = false;
  13.     for (int i = 2; i <= n; ++i){   //  注意数组大小是n
  14.         if(is_prime[i]){
  15.             prime[p++] = i;
  16.             for(int j = i + i; j <= n; j += i)  //  轻剪枝，j必定是i的倍数
  17.                 is_prime[j] = false;
  18.         }
  19.     }
  20.     return p;   //  返回素数个数
  21. }

快速幂

/*
    |快速幂|
*/
typedef long long LL;   //  视数据大小的情况而定

LL powerMod(LL x, LL n, LL m)
{
    LL res = 1;
    while (n > 0){
        if  (n & 1) //  判断是否为奇数，若是则true
            res = (res * x) % m;
        x = (x * x) % m;
        n >>= 1;    //  相当于n /= 2;
    }
    return res;
}

全排列

/*
    |求1到n的全排列, 有条件|
    |16/11/05ztx, thanks to wangqiqi|
*/
void Pern(int list[], int k, int n) {   //  k表示前k个数不动仅移动后面n-k位数
    if (k == n - 1) {
        for (int i = 0; i < n; i++) {
            printf("%d", list[i]);
        }
        printf("\n");
    }else {
        for (int i = k; i < n; i++) {   //  输出的是满足移动条件所有全排列
            swap(list[k], list[i]);
            Pern(list, k + 1, n);
            swap(list[k], list[i]);
        }
    }
}