数据结构 第八章节 排序

news/2025/1/15 21:52:30/

参考：1.数据结构C语言版|第2版；2.力扣；3.2024年数据结构考研复习指导。三个参考分别依次对应文章三个部分。

文章目录

  • 第一部分
    • 基本概念
    • 插入排序
      • 直接插入排序
      • 折半插入排序
      • 希尔排序(缩小增量排序)
    • 交换排序
      • 冒泡排序
      • 快速排序
    • 选择排序
      • 简单选择排序
      • 堆排序
    • 归并排序
  • 第二部分
      • 268. 丢失的数字
      • 448. 找到所有数组中消失的数字
      • 506. 相对名次
      • 645. 错误的集合
      • 953. 验证外星语词典
      • 1051. 高度检查器
      • 75. 颜色分类
      • 215. 数组中的第K个最大元素
      • 229. 多数元素II
      • 41. 缺失的第一个正数
  • 第三部分

第一部分

基本概念

排序定义：排序是按关键字的非递减或非递增的顺序重新排列记录序列。排序的稳定性：当两个记录的关键字相同并且排序没有改变这两个记录的原有顺序，那我们就说排序是稳定的，反之，排序是不稳定的。内部排序和外部排序：内部排序：完全在内存中完成的排序；外部排序：不完全在内存中完成的排序。

插入排序

插入排序的基本思想是：每一次排序将一个新的记录插入到已经排序好的子序列当中。

直接插入排序

稳定排序
时间复杂度：O ( n 2 ) \left(n^2\right) (n2)
空间复杂度：O ( 1 ) \left(1\right) (1)

#include<iostream>
using namespace std;
void InsertSort(int *,int);
void print(int *,int);
int main()
{int n;cin>>n;int * lb=new int [n];for (int i=0;i<n;i++)cin>>lb[i];InsertSort(lb,n);print(lb,n);delete [] lb;return 0;
}
void InsertSort(int * lb,int len)
{for (int i=1;i<len;i++){if (lb[i]>=lb[i-1]) continue;int temp=lb[i],j=i-1;for (;j>=0 and temp<lb[j];j--)lb[j+1]=lb[j];lb[j+1]=temp;}
}
void print(int * lb,int len)
{for (int i=0;i<len;i++)cout<<lb[i]<<" ";cout<<endl;
}

折半插入排序

稳定排序
时间复杂度：O ( n 2 ) \left(n^2\right) (n2)
空间复杂度：O ( 1 ) \left(1\right) (1)

#include<iostream>
using namespace std;
void BinaryInsertSort(int *,int);
void print(int *,int);
int main()
{int n;cin>>n;int * lb=new int [n];for (int i=0;i<n;i++)cin>>lb[i];BinaryInsertSort(lb,n);print(lb,n);delete [] lb;return 0;
}
void BinaryInsertSort(int * lb,int len)
{for (int i=1;i<len;i++){if (lb[i]>=lb[i-1]) continue;int l=0,r=i-1,m;while (l<=r){m=l+(r-l)/2;if (lb[m]<lb[i]) l=m+1;else if (m==0 or lb[m-1]<=lb[i]) break;else r=m-1;}int temp=lb[i];for (int j=i;j>m;j--)lb[j]=lb[j-1];lb[m]=temp;}
}
void print(int * lb,int len)
{for (int i=0;i<len;i++)cout<<lb[i]<<" ";cout<<endl;
}

希尔排序(缩小增量排序)

不稳定排序
时间复杂度：未知
空间复杂度：O(1)

#include<iostream>
using namespace std;
void ShellInsert(int,int,int *);
void ShellSort(int,int *,int,int *);
void print(int *,int);
int main()
{int n;cin>>n;int * lb1=new int [n];for (int i=0;i<n;i++)cin>>lb1[i];int m;cin>>m;int * lb2=new int [m];for (int i=0;i<m;i++)cin>>lb2[i];ShellSort(n,lb1,m,lb2);print(lb1,n);delete [] lb1,lb2;return 0;
}
void ShellInsert(int delta,int len,int * lb)
{for (int i=0;i<delta;i++)for (int j=i+delta;j<len;j+=delta){if (lb[j]>=lb[j-delta]) continue;int temp=lb[j],k=j-delta;for (;k>=0 and temp<lb[k];k-=delta)lb[k+delta]=lb[k];lb[k+delta]=temp;}
}
void ShellSort(int n,int * lb1,int m,int * lb2)
{for (int i=0;i<m;i++)ShellInsert(lb2[i],n,lb1);
}
void print(int * lb,int len)
{for (int i=0;i<len;i++)cout<<lb[i]<<" ";cout<<endl;
}

交换排序

交换排序的基本思想是：两两比较两个记录的关键字，一旦发现两个记录不满足要求，则交换两个记录的顺序，直到序列满足要求为止。

冒泡排序

稳定排序
时间复杂度：O ( n 2 ) \left(n^2\right) (n2)
空间复杂度：O(1)

#include<iostream>
using namespace std;
void BubbleSort(int *,int);
void print(int *,int);
int main()
{int n;cin>>n;int * lb=new int [n];for (int i=0;i<n;i++)cin>>lb[i];BubbleSort(lb,n);print(lb,n);delete [] lb;return 0;
}
void BubbleSort(int * lb,int len)
{for (int i=1;i<len;i++){bool flag=true;for (int j=0;j<len-i;j++)if (lb[j]>lb[j+1]){flag=false;int temp=lb[j];lb[j]=lb[j+1];lb[j+1]=temp;}if (flag) break;}
}
void print(int * lb,int len)
{for (int i=0;i<len;i++)cout<<lb[i]<<" ";cout<<endl;
}

快速排序

不稳定排序
时间复杂度：O ( n l o g 2 n ) \left(nlog_2n\right) (nlog2​n)
空间复杂度：最好O ( l o g 2 n ) \left(log_2n\right) (log2​n)，最坏O(n)

#include<iostream>
using namespace std;
int Partition(int *,int,int);
void func(int *,int,int);
void QuickSort(int *,int);
void print(int *,int);
int main()
{int n;cin>>n;int * lb=new int [n];for (int i=0;i<n;i++)cin>>lb[i];QuickSort(lb,n);print(lb,n);delete [] lb;return 0;
}
int Partition(int * lb,int left,int right)
{int pivotkey=lb[left];while (left<right){while (left<right and lb[right]>=pivotkey) right-=1;lb[left]=lb[right];while (left<right and lb[left]<=pivotkey) left+=1;lb[right]=lb[left];}lb[left]=pivotkey;return left;
}
void func(int * lb,int left,int right)
{if (left<right){int pivotloc=Partition(lb,left,right);func(lb,left,pivotloc-1);func(lb,pivotloc+1,right);}
}
void QuickSort(int * lb,int len)
{func(lb,0,len-1);
}
void print(int * lb,int len)
{for (int i=0;i<len;i++)cout<<lb[i]<<" ";cout<<endl;
}

选择排序

选择排序的基本思想是：每次排序选出关键字最小或最大的记录放在已经排序好的子序列最后或最前。

简单选择排序

不稳定排序但是可以稍加修改变为稳定排序。具体来说，只需将“交换”策略更改为“平移”策略即可。
时间复杂度：O ( n 2 ) \left(n^2\right) (n2)
空间复杂度：O ( 1 ) \left(1\right) (1)

#include<iostream>
using namespace std;
void SelectSort(int *,int);
void print(int *,int);
int main()
{int n;cin>>n;int * lb=new int [n];for (int i=0;i<n;i++)cin>>lb[i];SelectSort(lb,n);print(lb,n);delete [] lb;return 0;
}
void SelectSort(int * lb,int len)
{for (int i=1;i<len;i++){int min_value=lb[i-1],min_value_index=i-1;for (int j=i;j<len;j++)if (lb[j]<min_value){min_value=lb[j],min_value_index=j;}int temp=lb[i-1];lb[i-1]=min_value;lb[min_value_index]=temp;}
}
void print(int * lb,int len)
{for (int i=0;i<len;i++)cout<<lb[i]<<" ";cout<<endl;
}

堆排序

不稳定排序
时间复杂度：O ( n l o g 2 n ) \left(nlog_2n\right) (nlog2​n)
空间复杂度：O ( 1 ) \left(1\right) (1)

#include<iostream>
using namespace std;
void HeapAdjust(int *,int,int);
void CreatHeap(int *,int);
void HeapSort(int *,int);
void print(int *,int);
int main()
{int n;cin>>n;int * lb=new int [n];for (int i=0;i<n;i++)cin>>lb[i];HeapSort(lb,n);print(lb,n);delete [] lb;return 0;
}
/*数学推导重中之重*/
void HeapAdjust(int * lb,int begin,int end)
{int temp=lb[begin];for (int i=2*begin+1;i<=end;i=2*begin+1){if (i+1<=end and lb[i+1]>lb[i]) i+=1;if (temp>lb[i]) break;lb[begin]=lb[i];begin=i;}lb[begin]=temp;
}
/*数学推导重中之重*/
void CreatHeap(int * lb,int len)
{for (int i=len/2-1;i>=0;i--)HeapAdjust(lb,i,len-1);
}
void HeapSort(int * lb,int len)
{CreatHeap(lb,len);for (int i=len-1;i>=1;i--){int temp=lb[i];lb[i]=lb[0];lb[0]=temp;HeapAdjust(lb,0,i-1);}
}
void print(int * lb,int len)
{for (int i=0;i<len;i++)cout<<lb[i]<<" ";cout<<endl;
}

归并排序

归并排序的基本思想是：将两个或两个以上的有序表合并成一个有序表的过程。2-路归并(故名思意)。
稳定排序
时间复杂度：O ( n l o g 2 n ) \left(nlog_2n\right) (nlog2​n)
空间复杂度：O ( n ) \left(n\right) (n)

#include<iostream>
using namespace std;
void Merge(int *,int,int,int);
void func(int *,int,int);
void MergeSort(int *,int);
void print(int *,int);
int main()
{int n;cin>>n;int * lb=new int [n];for (int i=0;i<n;i++)cin>>lb[i];MergeSort(lb,n);print(lb,n);delete [] lb;return 0;
}
void Merge(int * lb,int left,int middle,int right)
{int * lb_temp=new int [right-left+1];int begin1=left,begin2=middle+1,iter=0;while (begin1<=middle and begin2<=right)if (lb[begin1]<=lb[begin2]) {lb_temp[iter]=lb[begin1];begin1+=1;iter+=1;}else {lb_temp[iter]=lb[begin2];begin2+=1;iter+=1;}while (begin1<=middle) {lb_temp[iter]=lb[begin1];begin1+=1;iter+=1;}while (begin2<=right) {lb_temp[iter]=lb[begin2];begin2+=1;iter+=1;}for (int i=0;i<right-left+1;i++)lb[left+i]=lb_temp[i];delete [] lb_temp;
}
void func(int * lb,int left,int right)
{if (left<right){int middle=left+(right-left)/2;func(lb,left,middle);func(lb,middle+1,right);Merge(lb,left,middle,right);}
}
void MergeSort(int * lb,int len)
{func(lb,0,len-1);
}
void print(int * lb,int len)
{for (int i=0;i<len;i++)cout<<lb[i]<<" ";cout<<endl;
}

基数排序
只需留个印象就好
稳定排序
时间复杂度：O ( n ) \left(n\right) (n)
空间复杂度：O ( m ) \left(m\right) (m)

第二部分

268. 丢失的数字

学习习题
已经最优

class Solution {
public:int missingNumber(vector<int>& nums) {sort(nums.begin(),nums.end());for (int i=0;i<nums.size();i++)if (nums[i]!=i) return i;return nums.size();}
};

448. 找到所有数组中消失的数字

学习习题
已经最优

class Solution {
public:vector<int> findDisappearedNumbers(vector<int>& nums) {vector<int> result;sort(nums.begin(),nums.end());for (int i=1;i<nums[0];i++)result.push_back(i);for (int i=1;i<nums.size();i++)if (nums[i]-nums[i-1]>1)for (int j=nums[i-1]+1;j<nums[i];j++)result.push_back(j);for (int i=nums[nums.size()-1]+1;i<=nums.size();i++)result.push_back(i);return result;}
};

506. 相对名次

学习习题
已经最优

bool func(pair<int,int> p1,pair<int,int> p2)
{if (p1.first>p2.first) return true;return false;
}
class Solution {
public:vector<string> findRelativeRanks(vector<int>& score) {vector<string> result(score.size());vector<pair<int,int>> lb;for (int i=0;i<score.size();i++)lb.push_back(make_pair(score[i],i));sort(lb.begin(),lb.end(),func);for (int i=0;i<lb.size();i++)if (i==0) result[lb[i].second]="Gold Medal";else if (i==1) result[lb[i].second]="Silver Medal";else if (i==2) result[lb[i].second]="Bronze Medal";else result[lb[i].second]=to_string(i+1);return result;}
};

645. 错误的集合

学习习题
已经最优

class Solution {
public:vector<int> findErrorNums(vector<int>& nums) {sort(nums.begin(),nums.end());int a=-1,b=nums[0]==1?-1:1;for (int i=1;i<nums.size();i++){if (nums[i]==nums[i-1]) a=nums[i];if (nums[i]-nums[i-1]==2) b=nums[i]-1;}if (b==-1) b=nums.size();vector<int> result={a,b};return result;}
};

953. 验证外星语词典

学习习题
已经最优

class Solution {
public:string s;bool isAlienSorted(vector<string>& words, string order) {s=order;for (int i=1;i<words.size();i++)if (!func(words[i-1],words[i]))return false;return true;}bool func(const string & s1,const string & s2){if (s1.find(s2)==0 and s1.size()>s2.size()) return false;int size=min(s1.size(),s2.size());for (int i=0;i<size;i++){int x=s.find(s1[i]),y=s.find(s2[i]);if (x<y) return true;if (x>y) return false;}return true;}
};

1051. 高度检查器

学习习题
已经最优

class Solution {
public:int heightChecker(vector<int>& heights) {int result=0;vector<int> my_vector=heights;sort(my_vector.begin(),my_vector.end());for (int i=0;i<heights.size();i++)result+=heights[i]==my_vector[i]?0:1;return result;}
};

75. 颜色分类

练习习题
已经最优

class Solution {
public:void sortColors(vector<int>& nums) {int lb[3] {};for (int i=0;i<nums.size();i++)lb[nums[i]]+=1;int iter=0;for (int i=0;i<3;i++)for (int j=0;j<lb[i];j++){nums[iter]=i;iter+=1;}}
};

215. 数组中的第K个最大元素

练习习题
已经最优

class Solution {
public:int findKthLargest(vector<int>& nums, int k) {return HeapSort(nums,k);}void HeapAdjust(vector<int> & nums,int begin,int end){int temp=nums[begin];for (int i=begin*2+1;i<=end;i=begin*2+1){if (i+1<=end and nums[i+1]>nums[i]) i+=1;if (temp>nums[i]) break;nums[begin]=nums[i];begin=i;}nums[begin]=temp;}void CreateHeap(vector<int> & nums){for (int i=nums.size()/2-1;i>=0;i--)HeapAdjust(nums,i,nums.size()-1);}int HeapSort(vector<int> & nums,int k){CreateHeap(nums);for (int i=1;i<=k;i++){int temp=nums[0];nums[0]=nums[nums.size()-i];nums[nums.size()-i]=temp;HeapAdjust(nums,0,nums.size()-i-1);}return nums[nums.size()-k];}
};

229. 多数元素II

练习习题
已经最优

class Solution {
public:vector<int> majorityElement(vector<int>& nums) {vector<int> result;sort(nums.begin(),nums.end());int level=nums.size()/3,count=1,iter=0;if (count>level){int temp=nums[iter];result.push_back(temp);while (iter+1<nums.size() and nums[iter+1]==nums[iter]) iter+=1;}iter+=1;while (iter<nums.size()){if (nums[iter]==nums[iter-1]) count+=1;else count=1;if (count>level){int temp=nums[iter];result.push_back(temp);while (iter+1<nums.size() and nums[iter+1]==nums[iter]) iter+=1; }iter+=1;}return result;}
};

41. 缺失的第一个正数

进阶习题
已经最优

class Solution {
public:int firstMissingPositive(vector<int>& nums) {sort(nums.begin(),nums.end());if (nums[nums.size()-1]<=0) return 1;int l=0,r=nums.size()-1,m;while (l<=r){m=l+(r-l)/2;if (nums[m]<=0) l=m+1;else if (m==0 or nums[m-1]<=0) break;else r=m-1;}if (nums[m]!=1) return 1;int result=0;for (int i=m+1;i<nums.size();i++)if (nums[i]-nums[i-1]>=2){result=nums[i-1]+1;break;}if (result==0) result=nums[nums.size()-1]+1;return result;}
};

第三部分

有些题目特别傻逼，不要过多进行纠结。


http://www.ppmy.cn/news/1290607.html

相关文章

94. 二叉树的中序遍历

94. 二叉树的中序遍历

94. 二叉树的中序遍历 题目链接&#xff1a;94. 二叉树的中序遍历 代码如下&#xff1a; /*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr)…
阅读更多...
『番外篇六』SwiftUI 取得任意视图全局位置的三种方法

『番外篇六』SwiftUI 取得任意视图全局位置的三种方法

概览 在 SwiftUI 开发中，利用描述性代码我们可以很轻松的构建各种丰富多彩的视图。我们可以设置它们的大小、位置、颜色并应用不计其数的修改器。 但是，小伙伴们是否想过在 SwiftUI 中如何获取一个视图的全局位置坐标呢？ 在本篇博文中，您将学到如下内容： 概览1. SwiftU…
阅读更多...
普中STM32-PZ6806L开发板(HAL库函数实现-温度传感器DS18B20)

普中STM32-PZ6806L开发板(HAL库函数实现-温度传感器DS18B20)

简介 主芯片STM32F103ZET6, 通过引脚PG11 连接DS18B20, 读取DS18B20采集的温度数据;电路原理图 DS18B20电路图 DS18B20 与 主芯片连接引脚 其他知识 DS18B20资料 DS18B20数据手册 DS18B20 简介 单线通讯的温度传感器, 测量温度在-55℃ 到 125℃&#xff0c; 在-10C 到…
阅读更多...
Python----matplotlib库

Python----matplotlib库

目录 plt库的字体&#xff1a; plt的操作绘图函数&#xff1a; plt.figure(figsizeNone, facecolorNone): plt.subplot(nrows, ncols, plot_number)&#xff1a; plt.axes(rect)&#xff1a; plt.subplots_adjust(): plt的读取和显示相关函数&#xff1a; plt库的基础图…
阅读更多...
运行时错误‘53’文件未找到：MathPage.WLL，安装MathType后Word不能复制粘贴问题的解决

运行时错误‘53’文件未找到：MathPage.WLL，安装MathType后Word不能复制粘贴问题的解决

两步解决&#xff1a; 1. 打开Word-->文件-->选项-->信任中心-->信任中心设置-->受信任位置&#xff0c;解决宏问题 添加如下受信任位置&#xff0c; 我的路径&#xff1a;C:\Program Files\Microsoft Office\root\Office16\STARTUP\ 2. 找到MathType下的MathT…
阅读更多...
计算机系统基础

计算机系统基础

C 语言相关内容省略&#xff0c;复习自用&#xff0c;仅供参考~ 概述 冯诺伊曼结构 存储程序工作方式&#xff1a;将事先编好的程序和原始数据送入主存后才能执行程序&#xff0c;程序被启动执行后&#xff0c;计算机能在不需要操作人员干预下自动完成逐条指令取出和执行的任…
阅读更多...
ElasticSearch数据同步

ElasticSearch数据同步

文章目录 ElasticSearch数据同步1. 同步调用2. 异步通知3. 监听binlog4. 工作中处理同步的问题 ElasticSearch数据同步 ElasticSearch中酒店数据来自于mysql数据库&#xff0c;因此MySQL数据发生改变时&#xff0c;ElasticSearch也必须跟着改变&#xff0c;这个就是ElasticSear…
阅读更多...
61.本地缓存加载与使用实践

61.本地缓存加载与使用实践

文章目录 一、本地缓存理论最佳实践二、Go代码实践&#xff1a;1、本地缓存设计2、本地缓存加载 代码地址&#xff1a;https://gitee.com/lymgoforIT/golang-trick/tree/master/37-load-local-cache 一、本地缓存理论最佳实践 控制缓存大小&#xff1a;根据应用程序的需求和可…
阅读更多...
最新文章

Copyright @ 2022~2023