博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
我要好offer之 排序算法大总结
阅读量:5106 次
发布时间:2019-06-13

本文共 6889 字,大约阅读时间需要 22 分钟。

1. 插入排序

(1) 直接插入排序

void StraightInsertionSort(std::vector
& num) { if (num.size() == 0 || num.size() == 1) return; for (int i = 1; i < num.size(); ++i) { int tmp = num.at(i); int j = i - 1; for (; j >= 0 && num.at(j) > tmp; --j) { num.at(j + 1) = num.at(j); } num.at(j + 1) = tmp; }}

(2) 折半插入排序

void BinaryInsertionSort(std::vector
& num) { if (num.size() == 0 || num.size() == 1) return; for (int i = 1; i < num.size(); ++i) { int tmp = num.at(i); int first = 0; // 最终的first值即为插入位置 int last = i - 1; while (first <= last) { int mid = first + (last - first) / 2; if (num.at(mid) < tmp) { first = mid + 1; } else if (num.at(mid) > tmp) { last = mid - 1; } else { first = mid; break; } } for (int t = i - 1; t >= first; --t) { num.at(t + 1) = num.at(t); } num.at(first) = tmp; }}

 

2. 希尔排序

void ShellSort(std::vector
& num) { if (num.size() == 0 || num.size() == 1) return; for (int gap = num.size() / 2; gap > 0; gap /= 2) { for (int i = gap; i < num.size(); ++i) { for (int j = i - gap; j >= 0 && num.at(j) > num.at(j + gap); j -= gap) { std::swap(num.at(j), num.at(j + gap)); } } }}

 

3. 冒泡排序

void BubbleSort(std::vector
& num) { if (num.size() == 0 || num.size() == 1) return; for (int i = 0; i < num.size(); ++i) { for (int j = 0; j < num.size() - i - 1; ++j) { if (num.at(j) > num.at(j + 1)) { std::swap(num.at(j), num.at(j + 1)); } } }}

 

4. 快速排序

(1) 递归版

// 划分int Partition(std::vector
& num, int first, int last) { assert(first >= 0 && first < num.size() && last >= 0 && last < num.size() && first <= last); int mid = first + (last - first) / 2; 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
& num, int first, int last) { if (first < last) { int pivotPos = Partition(num, first, last); quickSort(num, first, pivotPos - 1); quickSort(num, pivotPos + 1, last); }}void QuickSort(std::vector
& num) { quickSort(num, 0, num.size() - 1);}

 

(2) 非递归版

int Partition(std::vector
& num, int first, int last) { assert(first >= 0 && first < num.size() && last >= 0 && last < num.size() && first <= last); int mid = first + (last - first) / 2; 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
& num, int first, int last) { if (first < last) { std::stack
stk; int pivotPos = Partition(num, first, last); if (first < pivotPos - 1) { stk.push(first); stk.push(pivotPos - 1); } if (last > pivotPos + 1) { stk.push(pivotPos + 1); 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 - 1) { stk.push(left); stk.push(pivotPos - 1); } if (right > pivotPos + 1) { stk.push(pivotPos + 1); stk.push(right); } } }}

 

5. 简单选择排序

void SimpleSelectSort(std::vector
& num) { if (num.size() == 0 || num.size() == 1) return; for (int i = 0; i < num.size(); ++i) { for (int j = i + 1; 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
& num, int kth, int vecSize) { int left = 2 * kth; int right = 2 * kth + 1; int largest = INT_MIN; if (left <= vecSize && num.at(left - 1) > num.at(kth - 1)) { largest = left; } else { largest = kth; } if (right <= vecSize && num.at(right - 1) > num.at(largest - 1)) { largest = right; } if (largest != kth) { std::swap(num.at(kth - 1), num.at(largest - 1)); HeapAdjust(num, largest, vecSize); }}// 建堆void BuildHeap(std::vector
& num) { for (int i = num.size() / 2; i >= 0; --i) { HeapAdjust(num, i + 1, num.size()); }}// 堆排序void HeapSort(std::vector
& num) { BuildHeap(num); int vecSize = num.size(); while (vecSize > 1) { std::swap(num.at(0), num.at(vecSize - 1)); --vecSize; HeapAdjust(num, 1, vecSize); }}

 

7. 归并排序

void merge(std::vector
& num, int first, int mid, int last) { std::vector
tmp(last - first + 1, 0); int i = first; int j = mid + 1; int idx = 0; 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
& num, int first, int last) { if (first < last) { int mid = first + (last -first) / 2; MergeSort(num, first, mid); MergeSort(num, mid + 1, last); merge(num, first, mid, last); }}

 

8. 计数排序

void CountSort(std::vector
& num) { if (num.size() == 0 || num.size() == 1) return; int minVal = *(std::min_element(num.begin(), num.end())); int maxVal = *(std::max_element(num.begin(), num.end())); int valRange = maxVal - minVal + 1; std::vector
count(valRange, 0); for (int i = 0; i < num.size(); ++i) { count.at(num.at(i) - minVal)++; } for (int i = 1; i < count.size(); ++i) { count.at(i) = count.at(i) + count.at(i - 1); } std::vector
tmp(num); for (int i = tmp.size() - 1; i >= 0; --i) { int lessNum = count.at(tmp.at(i) - minVal); num.at(lessNum - 1) = tmp.at(i); count.at(tmp.at(i) - minVal)--; }}

 

小结: 

 

 

转载于:https://www.cnblogs.com/wwwjieo0/p/3915717.html

你可能感兴趣的文章
struts.convention.classes.reload配置为true,tomcat启动报错
查看>>
MySQL的并行复制多线程复制MTS(Multi-Threaded Slaves)
查看>>
好玩的-记最近玩的几个经典ipad ios游戏
查看>>
PyQt5--EventSender
查看>>
Sql Server 中由数字转换为指定长度的字符串
查看>>
Java 多态 虚方法
查看>>
Unity之fragment shader中如何获得视口空间中的坐标
查看>>
万能的SQLHelper帮助类
查看>>
tmux的简单快捷键
查看>>
[Swift]LeetCode922.按奇偶排序数组 II | Sort Array By Parity II
查看>>
Html5 离线页面缓存
查看>>
《绿色·精简·性感·迷你版》易语言,小到不可想象
查看>>
Android打包key密码丢失找回
查看>>
VC6.0调试技巧(一)(转)
查看>>
类库与框架,强类型与弱类型的闲聊
查看>>
webView添加头视图
查看>>
php match_model的简单使用
查看>>
在NT中直接访问物理内存
查看>>
Intel HEX 文件格式
查看>>
SIP服务器性能测试工具SIPp使用指导(转)
查看>>