我要好offer之 排序算法大总结
2024-09-02 17:10:52
1. 插入排序
(1) 直接插入排序
void StraightInsertionSort(std::vector<int>& num) {
if (num.size() == || num.size() == ) return;
for (int i = ; i < num.size(); ++i) {
int tmp = num.at(i);
int j = i - ;
for (; j >= && num.at(j) > tmp; --j) {
num.at(j + ) = num.at(j);
}
num.at(j + ) = tmp;
}
}
(2) 折半插入排序
void BinaryInsertionSort(std::vector<int>& num) {
if (num.size() == || num.size() == ) return;
for (int i = ; i < num.size(); ++i) {
int tmp = num.at(i);
int first = ; // 最终的first值即为插入位置
int last = i - ;
while (first <= last) {
int mid = first + (last - first) / ;
if (num.at(mid) < tmp) {
first = mid + ;
} else if (num.at(mid) > tmp) {
last = mid - ;
} else {
first = mid;
break;
}
}
for (int t = i - ; t >= first; --t) {
num.at(t + ) = num.at(t);
}
num.at(first) = tmp;
}
}
2. 希尔排序
void ShellSort(std::vector<int>& num) {
if (num.size() == || num.size() == ) return;
for (int gap = num.size() / ; gap > ; gap /= ) {
for (int i = gap; i < num.size(); ++i) {
for (int j = i - gap; j >= && num.at(j) > num.at(j + gap); j -= gap) {
std::swap(num.at(j), num.at(j + gap));
}
}
}
}
3. 冒泡排序
void BubbleSort(std::vector<int>& num) {
if (num.size() == || num.size() == ) return;
for (int i = ; i < num.size(); ++i) {
for (int j = ; j < num.size() - i - ; ++j) {
if (num.at(j) > num.at(j + )) {
std::swap(num.at(j), num.at(j + ));
}
}
}
}
4. 快速排序
(1) 递归版
// 划分
int Partition(std::vector<int>& num, int first, int last) {
assert(first >= && first < num.size() && last >= && last < num.size() && first <= last);
int mid = first + (last - first) / ;
std::swap(num.at(first), num.at(mid));
int pos = first;
for (int i = first; i <= last; ++i) {
if (num.at(i) < num.at(first)) {
std::swap(num.at(++pos), num.at(i));
}
}
std::swap(num.at(first), num.at(pos));
return pos;
} // 快速排序
void quickSort(std::vector<int>& num, int first, int last) {
if (first < last) {
int pivotPos = Partition(num, first, last);
quickSort(num, first, pivotPos - );
quickSort(num, pivotPos + , last);
}
} void QuickSort(std::vector<int>& num) {
quickSort(num, , num.size() - );
}
(2) 非递归版
int Partition(std::vector<int>& num, int first, int last) {
assert(first >= && first < num.size() && last >= && last < num.size() && first <= last);
int mid = first + (last - first) / ;
std::swap(num.at(first), num.at(mid));
int pos = first;
for (int i = first; i <= last; ++i) {
if (num.at(i) < num.at(first)) {
std::swap(num.at(++pos), num.at(i));
}
}
std::swap(num.at(first), num.at(pos));
return pos;
}
void QuickSort(std::vector<int>& num, int first, int last) {
if (first < last) {
std::stack<int> stk;
int pivotPos = Partition(num, first, last);
if (first < pivotPos - ) {
stk.push(first);
stk.push(pivotPos - );
}
if (last > pivotPos + ) {
stk.push(pivotPos + );
stk.push(last);
}
while (!stk.empty()) {
int right = stk.top();
stk.pop();
int left = stk.top();
stk.pop();
pivotPos = Partition(num, left, right);
if (left < pivotPos - ) {
stk.push(left);
stk.push(pivotPos - );
}
if (right > pivotPos + ) {
stk.push(pivotPos + );
stk.push(right);
}
}
}
}
5. 简单选择排序
void SimpleSelectSort(std::vector<int>& num) {
if (num.size() == || num.size() == ) return;
for (int i = ; i < num.size(); ++i) {
for (int j = i + ; j < num.size(); ++j) {
if (num.at(j) < num.at(i)) {
std::swap(num.at(i), num.at(j));
}
}
}
}
6. 堆排序
// 堆调整，注意结点编号kth从1开始
void HeapAdjust(std::vector<int>& num, int kth, int vecSize) {
int left = * kth;
int right = * kth + ;
int largest = INT_MIN;
if (left <= vecSize && num.at(left - ) > num.at(kth - )) {
largest = left;
} else {
largest = kth;
} if (right <= vecSize && num.at(right - ) > num.at(largest - )) {
largest = right;
}
if (largest != kth) {
std::swap(num.at(kth - ), num.at(largest - ));
HeapAdjust(num, largest, vecSize);
}
} // 建堆
void BuildHeap(std::vector<int>& num) {
for (int i = num.size() / ; i >= ; --i) {
HeapAdjust(num, i + , num.size());
}
} // 堆排序
void HeapSort(std::vector<int>& num) {
BuildHeap(num);
int vecSize = num.size();
while (vecSize > ) {
std::swap(num.at(), num.at(vecSize - ));
--vecSize;
HeapAdjust(num, , vecSize);
}
}
7. 归并排序
void merge(std::vector<int>& num, int first, int mid, int last) {
std::vector<int> tmp(last - first + , );
int i = first;
int j = mid + ;
int idx = ;
while (i <= mid && j <= last) {
if (num.at(i) <= num.at(j)) {
tmp.at(idx++) = num.at(i++);
} else {
tmp.at(idx++) = num.at(j++);
}
}
while (i <= mid) {
tmp.at(idx++) = num.at(i++);
}
while (j <= last) {
tmp.at(idx++) = num.at(j++);
}
for (int i = first; i <= last; ++i) {
num.at(i) = tmp.at(i - first);
}
}
void MergeSort(std::vector<int>& num, int first, int last) {
if (first < last) {
int mid = first + (last -first) / ;
MergeSort(num, first, mid);
MergeSort(num, mid + , last);
merge(num, first, mid, last);
}
}
8. 计数排序
void CountSort(std::vector<int>& num) {
if (num.size() == || num.size() == ) return;
int minVal = *(std::min_element(num.begin(), num.end()));
int maxVal = *(std::max_element(num.begin(), num.end()));
int valRange = maxVal - minVal + ;
std::vector<int> count(valRange, );
for (int i = ; i < num.size(); ++i) {
count.at(num.at(i) - minVal)++;
}
for (int i = ; i < count.size(); ++i) {
count.at(i) = count.at(i) + count.at(i - );
}
std::vector<int> tmp(num);
for (int i = tmp.size() - ; i >= ; --i) {
int lessNum = count.at(tmp.at(i) - minVal);
num.at(lessNum - ) = tmp.at(i);
count.at(tmp.at(i) - minVal)--;
}
}
小结：
最新文章
- linux系统的初化始配置（包括网络，主机名，关闭firewalld与selinux）
- day5----模块
- 【转】在C#用HttpWebRequest中发送GET/HTTP/HTTPS请求
- [css] 浏览器字体和css设置字体之间的关系
- 汇编学习笔记(3)[bx]和loop
- Android中的TextView实现多行显示省略号
- JS关闭当前页面的方法
- 2DSprite添加Light照射（Unity3D开发之十六）
- 一入OI深似海 3 —— 纪念我最后一次PJ（上）
- js every some 遍历函数理解
- [Linux] Linux的环境变量
- 第二章 基础查询 2-1 SQL语句基础
- Mastering Markdown
- C++ 函数模板默认的模板参数
- python 2与python3 区别
- 2018.11.06 bzoj1097: [POI2007]旅游景点atr（最短路+状压dp）
- Java基础——Servlet（二）
- Excel 怎样去掉单元格中的回车符号
- 按键精灵对APP自动化测试（上）
- c#利用SWIG调用c++dll学习总结【转】