排序
冒泡排序
平均时间复杂度为$O(n^2)$，在最好情况下的时间复杂度为$O(n)$，在最坏情况下的时间复杂度为$O(n^2)$，在原地修改，所以空间复杂度为$O(1)$。
代码实现如下所示：
template<typename T>
void pop_sort(vector<T> & nums){
for(int i=0; i<nums.size()-1; i++){
for(int j=0; j<nums.size()-i-1; j++){
if(nums[j]>nums[j+1]){
T buffer = nums[j+1];
nums[j+1] = nums[j];
nums[j] = buffer;
}
}
}
}选择排序
选择排序整体思路与冒泡排序的思路相似，都是在依次排序之后将最小的元素放在最前面，不同的是，冒泡排序是两个相邻元素之间的比较，而选择排序进行的是整体的选择，即在每一趟都查出无序区的最小元素，将最小的元素追加至有序区的末尾。
选择排序的平均时间复杂度为$O(n^2)$，在最好情况下的时间复杂度为$O(n^2)$，在最坏情况下的时间复杂度为$O(n^2)$，在原地修改，所以空间复杂度为$O(1)$。
代码实现如下：
template<typename T>
void select_sort(vector<T> & nums){
int min;
for(int i = 0; i < nums.size()-1; i++){
min = i;
for(int j = i+1; j < nums.size(); j++){
if(nums[j] < nums[min]){
min = j;
}
}
T buffer = nums[i];
nums[i] = nums[min];
nums[min] = buffer;
}
}插入排序
插入排序的思路是构建一个有序数列，对于未排序的数据，在已排序的序列中从前往后扫描，找到正确的位置并插入。
平均时间复杂度为$O(n^2)$，在最好情况下的时间复杂度为$O(n)$，在最坏情况下的时间复杂度为$O(n^2)$，在原地修改，所以空间复杂度为$O(1)$。
代码实现如下：
template<typename T>
void insert_sort(vector<T> & nums){
for(int i = 1; i < nums.size(); i++){
int key = nums[i];
int j = i-1;
while(j>=0 && key<nums[j]){
nums[j+1] = nums[j];
j--;
}
nums[j+1] = key;
}
}希尔排序
希尔排序是对插入排序的一种修改。希尔排序的基本思想是将待排序的数据分为若干个子序列进行插入排序，等到整个序列都基本有序时，在对整个序列直接进行插入排序。
希尔排序的时间复杂度与子序列的选取有关，当子序列的步长设为1时，希尔排序退化为插入排序，时间复杂度为$O(n^2)$。希尔排序的平均时间复杂度为$O(n \log n)$
代码实现如下：
template<typename T>
void shell_sort(vector<T> & nums){
int h = 1;
int l = 3; // 步长，将原序列分为l个子序列
while(h<nums.size()/l){
h = l * h + 1;
}
while(h>=1){
for(int i = 0; i<nums.size(); i++){
for(int j = i; j>=h && nums[j] < nums[j-h]; j -= h){
T buffer = nums[j];
nums[j] = nums[j-h];
nums[j-h] = buffer;
}
}
h = h / l;
}
}归并排序
归并排序是一种建立在归并操作上的有效的排序算法。是一种使用分治法思想的典型应用。基本步骤为，将$n$个元素分成含$\frac{n}{2}$个元素的子序列，用合并排序法对两个子序列递归的排序，合并两个已排序的子序列得到排序的结果
归并排序的实现由两种方法：自上而下的递归；自下而上的迭代。
归并排序的时间复杂度为$O(n \log n)$，由于使用了额外的内存空间，空间复杂度为$O(n)$。
代码实现如下：
//1、使用自上而下的递归的实现
template<typename T>
vector<T> merge(vector<T> left, vector<T> right){
vector<T> res;
size_t l = 0, r = 0;
while(l<left.size() && r<right.size()){
if(left[l] <= right[r]) res.push_back(left[l++]);
else res.push_back(right[r++]);
}
if(l == left.size()) res.insert(res.end(), right.begin() + r, right.end());
else if (r == right.size()) res.insert(res.end(), left.begin() + l, left.end());
return res;
}
template<typename T>
vector<T> merge_sort_recursion(vector<T> nums){
if (nums.size()<2) return nums;
const size_t mid = nums.size() / 2;
vector<T> left(nums.begin(), nums.begin() + mid);
vector<T> right(nums.begin() + mid, nums.end());
return merge(merge_sort_recursion<T>(left), merge_sort_recursion<T>(right));
}
//2、使用自下而上的迭代的实现
template<typename T>
void merge_sort_interation(vector<T> & nums){
// 枚举步长
for(int seg = 1; seg<nums.size(); seg += seg){
// 合并两个相邻的区间
for(int i = 0; i<nums.size(); i += seg + seg){
vector<T> temp;
int low = i, mid = min(i + seg, nums.size()), high = min(i + seg + seg, nums.size());
int start1 = low, end1 = mid;
int start2 = mid, end2 = high;
while(start1 < end1 && start2 < end2){
temp.push_back(nums[start1]<nums[start2]? nums[start1++] : nums[start2++]);
}
while(start1 < end1){
temp.push_back(nums[start1++]);
}
while(start2 < end2){
temp.push_back(nums[start2++]);
}
for (int j = 0; j < temp.size(); j++) {
nums[low + j] = temp[j];
}
}
}
}快速排序
快速排序也是分治思想在排序中的一种应用，快速排序是在冒泡排序的基础上的递归分治法。快速排序是处理大数据的最快的排序算法。
快排的基本算法步骤为：从数列中挑出一个元素，成为基准；重新排序数列，将所有元素中比基准值小的放在基准的前面，将所有元素中比基准值大的放在基准的后边；递归的将小于基准值元素的子数列和大于基准值元素的子数列进行排序。
快速排序的时间复杂度为$O(n \log n)$，空间复杂度为$O(\log n)$。
// 1、迭代实现
struct Range{
int start, end;
Range(int s = 0, int e = 0){
start = s, end = e;
}
};
template<typename T>
void quick_sort(vector<T> & nums){
if(nums.size()<=0) return;
vector<Range> r(nums.size());
int p = 0;
r[p++] = Range(0, nums.size()-1);
while(p){
Range range(0, nums.size()-1);
if(range.start >= range.end) break;
T mid = nums[range.end];
int left = range.start, right = range.end;
while(left < right){
while(nums[left] < mid && left < right) left++;
while(nums[right] >= mid && left < right) right--;
T temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
}
if(nums[left] >= nums[range.end]){
T temp = nums[left];
nums[left] = nums[range.end];
nums[range.end] = temp;
}
else left++;
r[p++] = Range(range.start, left - 1);
r[p++] = Range(left + 1, range.end);
}
}
// 2、 递归实现
template<typename T>
void quick_sort(vector<T> & nums, int begin, int end){
if(begin > end) return;
T temp = nums[begin];
int i = begin, j = end;
while(i != j){
while(nums[i] >= temp && j > i){
j--;
}
while(nums[i] <= temp && j > i){
i++;
}
if(j > i){
T t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}
}
nums[begin] = nums[i];
nums[i] = temp;
quick_sort(nums, begin, i-1);
quick_sort(nums, i+1, end);
}堆排序
堆排序是指，利用堆数据结构的排序算法。堆积是一个近似完全二叉树的结构，同时满足堆积的性质，即子节点的键值或索引总是小于或大于它的父节点，分为两种方法：
- 大顶堆(最大堆)：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
- 小顶堆(最小堆)：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列。
堆排序的平均时间复杂度为$O(n \log n)$，空间复杂度为$O(1)$。
代码实现如下：
void max_heapify(vector<int> &nums, int start, int end)
{
int dad = start;
int son = dad * 2 + 1;
while (son <= end)
{
if (son + 1 <= end && nums[son] < nums[son + 1])
{
son++;
}
if (nums[dad] > nums[son])
{
return;
}
else
{
swap(nums[dad], nums[son]);
dad = son;
son = dad * 2 + 1;
}
}
}
void heap_sort(vector<int> &nums, int len)
{
for (int i = len / 2 - 1; i >= 0; i--)
{
max_heapify(nums, i, len - 1);
}
for (int i = len - 1; i > 0; i--)
{
swap(nums[0], nums[i]);
max_heapify(nums, 0, i - 1);
}
}
