C语言中排序相关的面试题有哪些？
这篇文章给大家分享的是C语言中排序相关的面试题，对大家学习或者工作都有一定的帮助，因此分享给大家做个参考，文中介绍的很详细，感兴趣的朋友接下来一起跟随小编看看吧。
排序算法有两块比较重要的知识点
- 内存消耗 ：算法的内存消耗可以通过空间复杂度来衡量，排序算法也不例外。不过，针对排序算法的空间复杂度，有一个概念是原地排序。原地排序算法是指空间复杂度是O(1)的排序算法。其中冒泡排序，插入排序、选择排序都属于原地排序算法
- 稳定性：针对排序算法，我们还有一个衡量指标是稳定性。这个概念是说，如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。
例如我们有一组数据 2 9 3 4 8 3 按照从小到大的排序是 2 3 3 4 8 9，经过某种排序算法之后，如果两个3的前后顺序没有改变，就称为稳定的排序算法，否则就是不稳定的排序算法
| 算法名称 | 时间复杂度 | 是否稳定排序 | 是否原地排序 |
| 冒泡排序 | O(N^2) | 是 | 是 |
| 插入排序 | O(N^2) | 是 | 是 |
| 选择排序 | O(N^2) | 否 | 是 |
| 归并排序 | O(nlogn) | 是 | 否 |
| 快速排序 | O(nlogn) | 否 | 是 |
| 堆排序 | O(nlogn) | 是 | 是 |
冒泡排序
- 平均复杂度是O(N^2)
- 最好情况是O(1) 本身就是排好序的
- 最坏就是倒序O(N^2)
- 空间复杂度是O(1)
冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作。
class Sort{
public:
void MaoPao_Sort(vectorint>
&
arr){
//1.判断溢出条件
if(arr.size() 2) return;
int length =arr.size();
for(int i =0;
i length;
i++){
for(int j=0;
j length -i -1 ;
j++){
if(arr[j] >
arr[j+1]){
int temp = arr[j];
arr[j]= arr[j+1];
arr[j+1]=temp;
}
}
}
}
}
;
插入排序
插入排序思想的由来，其实就是按照在一个有序的数组中插入一个元素的思想，找到合适的位置进行插入并迁移后面的元素
首先，我们将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。
class Sort{
public:
void Insert_Sort(vectorint>
&
arr){
//1.判断溢出条件
if(arr.size() 2) return;
int length =arr.size();
int j =0;
//初始的已排序区间的下标
for(int i =1;
i length ;
i++){
//从未排序的区间里面取元素
int temp =arr[i];
j =i-1;
//不断更新已排序区间
while(j >
= 0 &
&
temp a[j]){
//如果小的话就往后移动，找到合适的插入位置
arr[j+1]=arr[j];
j--;
}
arr[j+1]=temp;
//插入元素
}
}
}
;
选择排序
选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾
class Sort{
public:
void Select_Sort(vectorint>
&
arr ,int length){
for(int i =0;
i length -1;
i++){
int min_number =arr[i];
int flag = i;
for(int j =i;
j length ;
j++){
if(min_number >
arr[j]){
min_number = arr[j];
flag =j;
}
}
//交换数字
arr[flag] =arr[i];
arr[i]=min_number;
}
}
}
;
归并排序
归并排序是由下而上，采用分治的思想，把数据先拆分在合并，并把合并后的数据存入临时数组中，保证原先的数据位置不发生变化，是一种稳定的排序但不是原地排序，时间复杂度是O(nlogn)，空间复杂度是O(N)
class Sort{
public:
//归并排序
void MergeSort(vectorint>
&
arr){
if(arr.size() 2){
return ;
}
//拆分函数
Merge_Process(arr,0,arr.size())-1);
}
//先拆分，这是拆分函数
void Merge_Process(vectorint>
&
arr,int start,int end){
//递归拆分，首先需要递归的终止条件
if(end -start == 0) return;
int mid =((end -start)/2) +start;
Merge_Process(arr,start,mid);
Merge_Process(arr,mid+1,end);
//在合并
Merge(arr,start,mid,end);
}
//合并函数
void Merge(vectorint>
&
arr,int start,int mid, int end){
vectorint>
temp(end-start+1,0);
//初始化一个临时数组
int tempIndex =0;
//辅助空间索引
int leftIndex =start;
int rightIndex =mid+1;
while(leftIndex = mid &
&
rightIndex = end){
if(leftIndex rightIndex){
temp[tempIndex++] =arr[leftIndex++];
}
else{
temp[tempIndex++] =arr[rightIndex++];
}
}
while(leftIndex = mid){
temp[tempIndex++]=arr[leftIndex++];
}
while(rightIndex = end){
temp[tempIndex++]=arr[rightIndex++];
}
for(int i =0;
i temp.size();
i++){
arr[start+i]=temp[i];
}
}
}
;
快速排序
快速排序是先分区，在处理子问题，通过找到区间后取得任意一个分区点，小的放分区点左边，大的放分区点右边，时间复杂度是O(nlong),空间复杂度是O(1),是原地排序但不是稳定排序
快排优化的话，有：三数取中法，和随机法，都是为了防止要排序的数组中有重复元素，这块我演示的是随机法
class Sort{
public:
void quickSort(vectorint>
&
arr,int begin, int low){
if(begin end){
//产生一个随机值
int index =rand()%(end-begin+1)+begin;
//然后把产生的这个随机值，替换到数组的首位
swap(arr[begin],arr[index]);
int i =begin;
int j =end;
int base =arr[i];
//基准位
while(i j){
while(ij&
&
arr[j] >
= base){
j--;
}
num[i]=num[j];
while(ij &
&
arr[i] base){
i++;
}
num[j]=num[i];
}
//回归基准位
num[i]=base;
//递归开始处理子问题
quickSort(arr,begin,i-1);
quickSort(arr,i+1,end);
}
}
}
;
关于C语言中排序相关的面试题就介绍到这，有需要的朋友可以参考，希望能对大家有帮助。最后，想要了解更多c语言面试题，大家可以关注其它的相关文章。
文本转载自脚本之家
声明：本文内容由网友自发贡献，本站不承担相应法律责任。对本内容有异议或投诉，请联系2913721942#qq.com核实处理，我们将尽快回复您，谢谢合作！
若转载请注明出处： C语言中排序相关的面试题有哪些？
本文地址： https://pptw.com/jishu/655284.html