关键词:
深处开发岗,其实排序也是绕不开的环节,其中冒泡排序,选择排序,插入排序,归并排序,快速排序,堆排序也是我在秋招以来频繁问到的技术点
排序算法有两块比较重要的知识点
- 内存消耗 :算法的内存消耗可以通过空间复杂度来衡量,排序算法也不例外。不过,针对排序算法的空间复杂度,有一个概念是原地排序。原地排序算法是指空间复杂度是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);
;
基本排序算法(冒泡排序选择排序插入排序快速排序归并排序基数排序希尔排序)
冒泡排序publicstaticvoidbubbleSort(int[]arr){intlgn=arr.length;for(inti=0;i<lgn-1;i++){for(intj=0;j<lgn-1-i;j++){if(arr[j]>arr[j+1]){inttemp=arr[j+1];arr[j+1]=arr[j];arr[j]=temp;}}}}选择排序publicsta 查看详情
八大基础排序中(直接插入排序,希尔排序,冒泡排序,快速排序,归并排序,简单选择排序)
packagecom.wang.sort;importjava.util.Arrays;publicclassSort{ /** *1.直接插入排序 *思想:当前数与前面已经排好顺序的数进行比较,插入到合适的位置 *@paramarra */ publicvoidsimpleSort(int[]arra){ for(inti=1;i<arra.length;i++){ intte 查看详情
插入排序(直接插入排序希尔排序);交换排序(冒泡排序快速排序);选择排序(简单选择排序堆排序);归并排序和基数排序;基于关键词比较的排序算法下界分析
...排序(直接插入排序、希尔排序)交换排序(冒泡排序、快速排序)选择排序(简单选择排序、堆排序)归并排序和基数排序排序算法分析分治排序的一般方法、基于关键词比较的排序算法下界分析相邻交... 查看详情
七种基本排序算法(希尔排序,直接插入排序,冒泡排序,快速排序,简单选择排序,归并排序,堆排序)
classSortAlgorithm{staticvoidMain(string[]args){int[]arr1={1,4,2,7,9,8,3,6};//ShellSort(arr1);//DirectInsertSort(arr1);//BubbleSort(arr1);//QuickSort(arr1,0,arr1.Length-1);//SimpleSelectSort(arr1);//M 查看详情
冒泡排序,快速排序,归并排序,插入排序,希尔排序,堆排序,计数排序,桶排序,基数排序(代码片段)
选择排序,冒泡排序,快速排序,归并排序,插入排序,希尔排序,计数排序,桶排序,基数排序以上是一些常用的排序算法。选择排序for(inti=0;i<n;i++)intminval=a[i];intminid=i;for(intj=i+1;j<n;j++)if(a[j]<minval)minid=j;minval=a[j];swap(a[i],... 查看详情
所有排序算法汇总,冒泡,选择,插入,快速,优化快速,归并,希尔,堆排序
冒泡排序,不多说,两次for循环比较相邻两个元素的大小,然后进行交换。选择排序,我们第一次for循环遍历所有元素,并把当前元素假设为最小的元素,然后再一个for循环去寻找真正最小的元素进行交换,这样每次我们都能找... 查看详情
内排序方法的比较
...序插入排序直接插入排序折半插入排序希尔排序交换排序冒泡排序快速排序选择排序简单选择排序堆排序归并排序基数排序内部排序\\begincases插入排序\\begincases直接插入排序\\\\折半插入排序\\\\希尔排序\\\\\\endcases\\\\\\\\交换排序... 查看详情
c#各种内部排序方法的实现(直接插入排序希尔排序冒泡排序快速排序直接选择排序堆排序归并排序基数排序)(代码片段)
...种内部排序方法的实现(直接插入排序、希尔排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序、基数排序)以下代码为我在学习数据结构时自己敲出来的,除了主函数中的代码外没有做其他的测试... 查看详情
8大排序算法-我熟知(冒泡直接插入)
...1)插入排序(直接插入排序、希尔排序)2)交换排序(冒泡排序、快速排序)3)选择排序(直接选择排序、堆排序)4)归并排序5)分配排序(基数排序)所需辅助空间最多:归并排序所需辅助空间最少:堆排序平均速度最快... 查看详情
javascript实现常见排序算法:冒泡,插入,选择,归并,快速,堆排序(代码片段)
1.冒泡排序转自百度百科:冒泡排序,这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端,故名“冒泡排序”。冒泡排序算法的运作如下:(从后往前) 比较相邻的元素。如果第... 查看详情
常见的排序算法
插入排序直接插入排序,折半插入排序,2-路插入排序,希尔排序快速排序冒泡排序,快速排序(冒泡排序改进),选择排序简单选择排序,树形选择排序,堆排序归并排序基数排序 查看详情
排序算法整理:冒泡排序堆排序插入排序归并操作快速排序希尔排序选择排序(代码片段)
SortUtils.javapackageprms.utils.sort;importjava.util.Arrays;/***@ClassName:SortUtils*@Description:<p>排序算法工具类</p>*@authoredgar*@email【[email protected]】*@versionV1.0*@date2017-3-2815:35:12*/publicclassSortUtils/***@Title:SortUtils*@Description:私有... 查看详情
数据结构与算法从零开始系列:冒泡排序选择排序插入排序希尔排序堆排序快速排序归并排序基数排序
欢迎Star,本文的所有示例源码都在Github:https://github.com/AndroidHensen/Arithmetic本篇内容包含排序的介绍排序的C的实现排序的Java的实现排序的时间复杂度的计算1、基本思想:两个数比较大小,较大的数下沉,较小的数冒起来2、实现... 查看详情
排序算法时间复杂度o(n^2)冒泡排序选择排序插入排序时间复杂度o(nlogn)快速排序堆排序归并排序其他排序希尔排序计数排序
排序算法时间复杂度o(n^2)冒泡排序选择排序插入排序时间复杂度o(nlogn)快速排序堆排序归并排序其他排序希尔排序计数排序
总结:大厂面试常考手撕代码——javascript排序算法(冒泡排序选择排序插入排序快速排序)(代码片段)
文章目录1.冒泡排序2.选择排序3.插入排序4.快速排序1.冒泡排序//冒泡排序letarr=[2,4,1,6,3]functionbubbled(arr)for(leti=0;i<arr.length-1;i++)//【!!注意】这里不是j=i,因为回回都必须重头遍历,才能不漏一个... 查看详情
冒泡排序,插入排序,归并排序,快速排序的学习笔记
这几个很基础的排序非常有用,我重新整理了下代码 1#include<iostream>2#include<algorithm>34usingnamespacestd;56voidBouble_Sort(int*Arry,intLenth)//冒泡排序7{8inti,k;910intflag=0;1112for(i=Lenth-1;i>=0;i--)13{14 查看详情
常用排序的应用场景
...法分类1.插入排序法 直接插入排序,希尔排序(面试最常问)2.交换排序 冒泡排序,快速排序(面试最常问)3.选择排序 直接选择排序,堆排序(面试最常问)4.归并排序 归并排序5.基数排... 查看详情