归并排序的递归、非递归写法和随机快排的递归写法

本文主要是介绍归并排序的递归、非递归写法和随机快排的递归写法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

归并排序

#include <bits/stdc++.h>
using namespace std;
void Merge(vector<int>& v, int L1, int R1, int L2, int R2)
{vector<int> tmp(R2 - L2 + R1 - L1 + 2);int i = L1, j = L2, index = 0;while (i <= R1 && j <= R2) {if (v[i] <= v[j])tmp[index++] = v[i++];elsetmp[index++] = v[j++];}while (i <= R1) tmp[index++] = v[i++];while (j <= R2) tmp[index++] = v[j++];// 放回v里面for (int i = 0; i < index; ++i) {v[L1 + i] = tmp[i];}
}
void MergeSort_1(vector<int>& v, int left, int right)
{if (left < right) {int mid = left + (right - left) / 2;MergeSort_1(v, left, mid);MergeSort_1(v, mid + 1, right);Merge(v, left, mid, mid + 1, right);for (auto& i : v) cout << i << " ";cout << endl;}
}
void MergeSort_2(vector<int>& v, int left, int right)
{for (int step = 2; step / 2 <= right - left; step *= 2) {for (int i = left; i <= right; i += step) {int mid = i + (step - 1) / 2;Merge(v, i, mid, mid + 1, min(right, i + step - 1));}for (auto& i : v) cout << i << " ";cout << endl;}
}
int main()
{vector<int> v = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};cout << "########    OriginArray    ########\n";for (auto& i : v) cout << i << " ";cout << "\n";cout << "########    MergeSort_1    ########\n";MergeSort_1(v, 0, v.size() - 1);cout << "########    MergeSort_2    ########\n";v = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};MergeSort_2(v, 0, v.size() - 1);
}

随机快排

#include <bits/stdc++.h>
using namespace std;
int RandPartition(vector<int>& A, int left, int right)
{// 生成[left,rihgt]区间内的随机数pint p = round(0.1 * rand() / RAND_MAX * (right - left) + left);std::swap(A[left], A[p]);int tmp = A[left];while (left < right) {// 注意下面两个while中的第一个条件，保证了所有数都大于或者小于主元时候不非法访问while (left < right && A[right] > tmp) --right;A[left] = A[right];while (left < right && A[left] <= tmp) ++left;A[right] = A[left];}// 退出时left==rightA[left] = tmp;return left;
}
void QuickSort(vector<int>& A, int left, int right)
{if (left < right) {  //当前区间长度大于1// 获取主元坐标int pos = RandPartition(A, left, right);// 区间通过主元坐标一分为二QuickSort(A, left, pos - 1);// 当 partition 过程使得主元左边的元素都小于主元时// 可以写成 QuickSort(A, left, pos);// 因为此时数组长度是单减的// 但 partition 过程使得主元左边的元素都小于等于主元时就不能这样写// 除此之外，也要保证主元不要每次都选到最右边的元素，否则也会死循环// 例如样例 {0,0} 会死循环，每次主元都是 1 位置上的元素。QuickSort(A, pos + 1, right);}
}
void QuickSort2(vector<int>& A, int left, int right)
{if (left >= right) return;int last = left;for (int i = left + 1; i <= right; ++i)if (A[i] < A[left])swap(A[++last], A[i]);swap(A[left], A[last]);QuickSort2(A, left, last - 1);QuickSort2(A, last + 1, right);
}
int main()
{srand((unsigned)time(NULL));vector<int> v = {0, 0};cout << "########    OriginArray    ########\n";for (auto& i : v) cout << i << " ";cout << "\n";cout << "#########    QuickSort    #########\n";QuickSort(v, 0, v.size() - 1);for (auto& i : v) cout << i << " ";cout << "\n";
}