LintCode 464 · 整数排序 II
2023-03-14 22:52:36 时间
整数排序 II 题解集合
归并排序
class Solution {
public:
//合并两个有序子序列
void merge(vector<int>& A,int begin,int mid,int end,vector<int>& temp)
{
//第一个子序列起点和第二个子序列起点,以及temp数组起点
int i = begin, j = mid + 1, k = 0;
while (i <= mid && j <= end)
{
if (A[i] < A[j])
temp[k++] = A[i++];
else
temp[k++] = A[j++];
}
//对剩余没合并的部分进行归并
while (i <= mid)
temp[k++] = A[i++];
while (j <= end)
temp[k++] = A[j++];
//最后把temp里面存放的合并后为有序的左右序列倒回原数组a
//注意a的起点
for (int i = 0; i < k; i++)
A[begin + i] = temp[i];
}
//归并排序
void mergeSort(vector<int>& A,int begin,int end)
{
static vector<int> temp(A.size(), 0);
//拆分到只剩一个元素的极小序列,结束递归
if (begin < end)
{
int mid = (begin + end) / 2;
//将数组左半部分合并成有序序列
mergeSort(A, begin, mid);
//将数组的右半部分合并成有序序列
mergeSort(A, mid + 1, end);
//将两个有序序列合并
merge(A, begin, mid, end, temp);
}
}
void sortIntegers2(vector<int>& A)
{
mergeSort(A, 0, A.size()-1);
}
};
题目要求的是nlogn的复杂度,因此这里归并排序用递归不满足条件会超时
归并排序迭代版本
class Solution {
public:
//合并两个有序子序列
void merge(vector<int>& A,int begin,int mid,int end,vector<int>& temp)
{
//第一个子序列起点和第二个子序列起点,以及temp数组起点
int i = begin, j = mid + 1, k = 0;
while (i <= mid && j <= end)
{
if (A[i] < A[j])
temp[k++] = A[i++];
else
temp[k++] = A[j++];
}
//对剩余没合并的部分进行归并
while (i <= mid)
temp[k++] = A[i++];
while (j <= end)
temp[k++] = A[j++];
//最后把temp里面存放的合并后为有序的左右序列倒回原数组a
//注意a的起点
for (int i = 0; i < k; i++)
A[begin + i] = temp[i];
}
//归并排序
void mergeSort(vector<int>& A, int first, int last)
{
vector<int> temp(A.size(), 0);
//迭代的实现是直接从最小子序列(含一个元素)开始往上两两合并
int k = 1;//子序列长度
int Last = 0;
int First = 0;
int mid = 0;
while (k < last)
{
First = 0;
//3.剩余大于等于两个子序列的元素个数
while (First <= (last - 2 * k + 1))//加一的原因是因为下标从0算起
{
mid = First + k - 1;
Last = First + 2 * k - 1;
merge(A, First, mid, Last, temp);
First += 2 * k;
}
//当剩下的没有合并处理过的元素数量不足2k,即无法构成两个子序列进行合并操作时,要分类处理
//1.剩下小于等于一个子序列的元素个数
if (last - First <= k)
{
mid = First + (last - First) / 2;
merge(A, First, mid, last, temp);
}
//2.剩下大于一个小于两个的子序列元素个数
else
{
mid = First + k - 1;;
merge(A, First, mid, last, temp);
}
k *= 2;
}
//说明此时是特殊奇数情况,数组末尾还单着一个元素没有于前面一个完整的子序列合并
if (First == last)
{
merge(A, first, last - 1, last, temp);
}
}
void sortIntegers2(vector<int>& A)
{
mergeSort(A, 0, A.size() - 1);
}
};
快速排序
class Solution {
public:
void sortIntegers2(vector<int>& A) {
if (A.size() <= 1) return;
quick_sort(A,0,A.size() - 1);
}
//快速排序:end填入的是数组中最后一个元素的下标
void quick_sort(vector<int>& r, int begin, int end)
{
int pos = 0;//接收当前键值的在数组中下标的位置
if (begin < end)
{
pos = swap_sort(r, begin, end);
quick_sort(r, begin, pos - 1);
quick_sort(r, pos + 1, end);
}
}
//交换排序---每一次返回当前键值的在数组中的下标
int swap_sort(vector<int>& r, int begin, int end)
{
//我们设置begin位置的元素为键值
int i = begin;
int j = end;
//当退出循环时,i==j,i和j都指向当前键值所在下标位置
while (i < j)
{
while (i < j && r[i] <= r[j])
{
j--;
}
if (i < j)
{
swap(r[i], r[j]);//交换完后,r[j]的位置存储的是键值
i++;//调整i的位置
}
while (i < j && r[j] >= r[i])
{
i++;
}
if (i < j)
{
swap(r[i], r[j]);//交换完后,r[i]的位置存储的是键值
j--;//调整j的位置
}
}
return i;
}
};
相关文章
- 写给大数据从业者:数据科学的5个陷阱与缺陷
- 7个原因告诉你数据科学家为什么“供不应求”
- 海量样本无从下手?五种抽样算法分分钟搞定
- nuclio:新的无服务器化超级英雄
- 数据科学家为什么这么贵?
- 常用的几种大数据架构剖析
- 6个用于大数据分析的优秀工具
- 人工智能是一种改进数据控制和处理的好方法
- 用Go语言编写一门工具的终极指南
- 企业数据是如何“养成”的?
- 一个著名的日志系统是怎么设计出来的?
- PHP代码简洁之道——SOLID原则
- 从韩国的大数据之殇,看技术的产业价值与功能价值
- 令人抓狂的代码 - 万能正则表达式.*陷阱
- 真正的大数据问题以及为什么只有机器学习才能解决它
- 民生银行数据中台体系的构建与实践
- 云数据管理会成为DataOps的未来吗?
- 企业可以不要大数据,但必须要有“数据中台”
- PHP 源码探秘 - 为什么 trim 会导致乱码
- 态牛-Tech Neo 9月刊:基于算法的IT运维