C语言 排序
悟道xn 人气:0排序算法有两块比较重要的知识点
- 内存消耗 :算法的内存消耗可以通过空间复杂度来衡量,排序算法也不例外。不过,针对排序算法的空间复杂度,有一个概念是原地排序。原地排序算法是指空间复杂度是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(vector<int> &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(vector<int> &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(vector<int> &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(vector<int> & arr){ if(arr.size() < 2){ return ; } //拆分函数 Merge_Process(arr,0,arr.size())-1); } //先拆分,这是拆分函数 void Merge_Process(vector<int> &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(vector<int> &arr,int start,int mid, int end){ vector<int> 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(vector<int> &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(i<j&& arr[j] >= base){ j--; } num[i]=num[j]; while(i<j && arr[i] < base){ i++; } num[j]=num[i]; } //回归基准位 num[i]=base; //递归开始处理子问题 quickSort(arr,begin,i-1); quickSort(arr,i+1,end); } } };
加载全部内容