排序算法总结
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了排序算法总结,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2532字,纯文字阅读大概需要4分钟。
内容图文
![排序算法总结](/upload/InfoBanner/zyjiaocheng/832/423bbf72fecd481994e2017267f344b1.jpg)
O(n^2)
为什么要学习O(n^2)的排序算法?
- 编码简单,易于实现
- 在某些特殊情况,简单的算法更有效
- 简单算法的思想衍生出复杂的排序算法(如插入排序 -> 希尔排序)
- 作为子过程,改进更复杂的排序算法
选择排序
template<typename T>
void selectSort(T arr[], int len){
for (int i = 0; i < len; ++i) {
int minIndex = i;
for (int j = i; j < len; ++j) {
if (arr[j] < arr[minIndex]){
minIndex = j;
}
}
swap(arr[i],arr[minIndex]);
}
}
插入排序: 从后面选一个元素,插入前面已经有序的元素中
原始版:
template <typename T>
void insertSort(T arr[], int len){
for (int i = 0; i <len ; ++i) {
for (int j = i; j > 0 && arr[j-1]>arr[j] ; --j) {
swap(arr[j],arr[j-1]);
}
}
}
改进版,不需要多次交换
template <typename T>
void insertSort(T arr[], int len){
for (int i = 0; i <len ; ++i) {
T tmp = arr[i];
int j;
for (j = i ; j > 0 && arr[j-1] > tmp ; --j) {
arr[j] = arr[j-1];
}
arr[j] = tmp;
}
}
改进后的插入排序速度快于选择排序
插入排序对于近乎有序的序列,性能非常高(o(n)),所以在实际生产环境中,用的也挺多,也会作为子过程加入后面介绍的算法中。
冒泡排序:
速度很慢的一个排序算法
template <typename T>
void bubbleSort(T arr[], int len){
for (int i = 0; i < len; ++i) {
for (int j = 1; j < len-i; ++j) {
if (arr[j-1] > arr[j]){
swap(arr[j-1],arr[j]);
}
}
}
}
O(nlogn)
归并排序
非原地排序,需要O(n)的空间复杂度
红色索引元素比较,小的放上去
使用自顶向下的方式排序
template <typename T>
void merge(T arr[],int l,int m,int r){
T aux[r-l+1];
for (int i = l; i <= r ; ++i) {
aux[i-l] = arr[i];
}
int i = l,j = m+1;
for (int k = l; k <= r; ++k) {
if (i > m){
arr[k] = aux[j-l];
}else if(j > m){
arr[k] = aux[i-l];
}else if (arr[i] <= arr[j]){
arr[k] = aux[i-l];
}else{
arr[k] = aux[j-l];
}
}
}
//对[l,r]之间的元素进行排序
template <typename T>
void mergeSortCore(T arr[],int l,int r){
if (l >= r){
return;
}
int m = (l + r) / 2;
mergeSortCore(arr,l,m);
mergeSortCore(arr,m+1,r);
if (arr[m] > arr[m+1]) //优化
merge(arr,l,m,r);
}
template <typename T>
void mergeSort(T arr[], int len){
mergeSortCore(arr,0,len-1);
}
快速排序
单路快拍(多路不写)
using namespace std;
int partition(vector<int>& vec, int low, int high){
int pivokey = vec[low];
while (low < high){
while (low < high && vec[high] >= pivokey)
high--;
swap(vec[low],vec[high]);
while (low < high && vec[low] < pivokey)
low++;
swap(vec[low],vec[high]);
}
}
void quickSort(vector<int>& vec,int start,int end){
if (start >= end){
return;
}
int pivot = partition(vec,start,end);
quickSort(vec,start,pivot-1);
quickSort(vec,pivot+1,end);
}
int main(){
vector<int> vec = {1,3,45,1,2,3,65,1,3,6};
quickSort(vec,0,vec.size()-1);
for (int i = 0; i < vec.size(); ++i) {
cout << vec[i] << " ";
}
cout << endl;
}
内容总结
以上是互联网集市为您收集整理的排序算法总结全部内容,希望文章能够帮你解决排序算法总结所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。