六安手机网站建设,做电子商务网站实验总结,做网站模块,去哪个网站可以接单做ps等等面试浅谈之十大排序算法
HELLO#xff0c;各位博友好#xff0c;我是阿呆 #x1f648;#x1f648;#x1f648;
这里是面试浅谈系列#xff0c;收录在专栏面试中 #x1f61c;#x1f61c;#x1f61c;
本系列将记录一些阿呆个人整理的面试题 #x1f3c3;…面试浅谈之十大排序算法
HELLO各位博友好我是阿呆
这里是面试浅谈系列收录在专栏面试中
本系列将记录一些阿呆个人整理的面试题
OK兄弟们废话不多直接开冲 一 概述
排序定义
对一序列对象根据某个关键字进行排序 术语 稳定如果 a 在 b 前且 a b排序后 a 仍在 b 前不稳定如果 a 在 b 前且 a b排序后 a 可能在 b 后内排序所有排序操作在内存中完成外排序数据太大因此放在磁盘中排序通过磁盘和内存数据传输进行时间复杂度 算法执行所耗费时间空间复杂度算法执行所耗费内存 算法总结 名词解释 n : 数据规模k : 桶个数In-place : 占用常数内存不占用额外内存Out-place : 占用额外内存 算法分类 比较和非比较区别
常见的快速排序、归并排序、堆排序、冒泡排序等属于比较排序。在排序的最终结果里元素之间的次序依赖于它们之间的比较。每个数都必须和其他数进行比较才能确定自己的位置
在冒泡排序之类的排序中问题规模为 n又因为需要比较n次所以平均时间复杂度为O(n²)。在归并排序、快速排序之类的排序中问题规模通过分治法消减为logN次所以时间复杂度平均O(nlogn)
比较排序的优势是适用于各种规模的数据也不在乎数据的分布都能进行排序。可以说比较排序适用于一切需要排序的情况
计数排序、基数排序、桶排序则属于非比较排序。非比较排序是通过确定每个元素之前应该有多少个元素来排序。针对数组arr计算arr[i]之前有多少个元素则唯一确定了arr[i]在排序后数组中的位置。非比较排序只要确定每个元素之前的已有的元素个数即可所有一次遍历即可解决。算法时间复杂度O(n)
非比较排序时间复杂度底但由于非比较排序需要占用空间来确定唯一位置。所以对数据规模和数据分布有一定的要求 二 核心
冒泡排序Bubble Sort
冒泡排序重复地走访过要排序的数列一次比较两个元素如果它们的顺序错误就把它们交换过来
算法描述
比较相邻的元素如果第一个比第二个大就交换它们两个对每一对相邻元素作同样的工作从开始第一对到结尾的最后一对这样在最后的元素应该会是最大的数针对所有的元素重复以上的步骤除了最后一个重复步骤1~3直到排序完成
代码实现
// 两数交换
void mySwap(int a, int b) {int tmp a;a b;b tmp;
}// 冒泡排序
void BubbleSort(vectorint num) {bool sortFlag; //某趟排序后已有序, 则不需要再空跑趟int len num.size();for (int i 0; i len; i) {for (int j 0; j len - i - 1; j) {if (num[j 1] num[j])mySwap(num[j 1], num[j]);}if (!sortFlag) return vec;}
}选择排序Selection Sort
首先找到数组最小元素将它和数组第一个元素交换位置。在剩下元素中找到最小元素将它与数组第二个元素交换位置如此往复直至 n - 1 结束
算法描述
初始状态 无序区为 R[1…n]有序区为空第 i 趟排序 (i 1, 2, 3 … n - 1) 开始时当前有序区和无序区分别为R [1 … i - 1] 和 R (i … n。该趟排序从当前无序区中选出关键字最小的记录 R[k]将它与无序区的第 1 个记录 R 交换使 R[1 … i] 和 R[i1 … n) 分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区n - 1 趟结束数组有序化了
代码实现
// 选择排序
void SelectionSort(vectorint num) {int len num.size();for (int i 0; i len - 1; i) {int minPos i;for (int j i 1; j len; j) {if (num[j] num[minPos])minPos j;}mySwap(num[i], num[minPos]);}
}算法分析
时间复杂度O ( n 2 )
空间复杂度O ( 1 )
稳定性不稳定排序 直接插入排序Insertion Sort
把第一个元素作为有序部分从第二个元素开始将剩余元素逐个插入有序部分的合适位置
算法描述
从第一个元素开始该元素可以认为已经被排序取出下一个元素在已经排序的元素序列中从后向前扫描如果该元素已排序大于新元素将该元素移到下一位置重复步骤 3直到找到已排序的元素小于或者等于新元素的位置将新元素插入到该位置后重复步骤2~5
代码实现
// 直接插入排序
void InsertionSort(vectorint num) {int len num.size();for (int i 1; i len; i) {int tmp num[i];int j i - 1;while (j 0 num[j] tmp) { //在找合适位置num[j 1] num[j]; //移动元素位置--j; //移动索引}num[j 1] tmp; //插入合适位置}
}算法分析
时间复杂度O ( n 2 )
空间复杂度O ( 1 )
稳定性稳定排序 希尔排序Shell Sort
希尔排序是简单插入排序改进后的版本
把记录按增量分组对每组使用直接插入排序当增量减至 1 时整个文件恰被分成一组
算法描述
选择一个增量序列 t1t2…tk其中 ti tjtk 1按增量序列个数 k对序列进行 k 趟排序每趟排序根据对应的增量 ti将待排序列分割成若干长度为 m 的子序列分别对各子表进行直接插入排序。仅增量因子为 1 时整个序列作为一个表来处理表长度即为整个序列的长度。
动图演示 代码实现
void ShellSort(vectorint num) {int len num.size();// 逐渐缩小间隔最终为1for (int step len / 2; step 0; step / 2) {for (int i step; i len; i) {int tmp num[i];int j i - step;while (j 0 tmp num[j]) {num[j step] num[j];j - step;}num[j step] tmp;}}
}算法分析
时间复杂度O ( n 2 )
空间复杂度O ( 1 ) O(1)O(1)
稳定性不稳定排序 归并排序Merge Sort
即先使子序列有序再使子序列段间有序
算法描述
长度为 n 输入序列分成两个长度为 n/2 子序列对两个子序列分别采用归并排序将两个排序好子序列合并成一个最终序列
代码实现
void Merge(int *arr, int n) {int temp[n]; // 辅助数组int b 0; // 辅助数组的起始位置int mid n / 2; // mid将数组从中间划分前一半有序后一半有序int first 0, second mid; // 两个有序序列的起始位置while (first mid second n) {if (arr[first] arr[second]) // 比较两个序列temp[b] arr[first];elsetemp[b] arr[second];}while(first mid) temp[b] arr[first]; // 将剩余子序列复制到辅助序列中 while(second n) temp[b] arr[second];for (int i 0; i n; i) // 辅助序列复制到原序列arr[i] temp[i];
}void MergeSort(int *arr, int n) {if (n 1) return; // 递归出口if (n 1) {MergeSort(arr, n / 2); // 对前半部分进行归并排序MergeSort(arr n / 2, n - n / 2); // 对后半部分进行归并排序Merge(arr, n); // 归并两部分}
}算法分析
时间复杂度O ( n ∗ l o g n )
空间复杂度O ( n )
稳定性稳定排序 快速排序Quick Sort
从数组中选择一个元素称为 基准。把数组中所有小于 基准 元素放左边所有大于或等于 基准 元素放右边此时 基准 元素位置有序即无需再移动 基准 位置
以 基准 为界把大数组切割成两个小数组分割操作partition对 基准 左右两边数组进行递归操作直到数组大小为1。此时每个元素都处于有序位置 算法描述
从数列中挑出一个元素称为 基准pivot重新排序数列比基准值小在前比基准值大在后递归把小于基准值子数列和大于基准值子数列排序
代码实现
// 分割操作
int Partition(vectorint num, int left, int right) {int pivot num[left];int i left 1, j right;while (true) {// 向右找到第一个小于等于 pivot 的元素位置while (i j num[i] pivot)i;// 向左找到第一个大于等于 pivot 的元素位置while(i j num[j] pivot ) --j;if(i j)break;// 交换两个元素的位置使得左边的元素不大于pivot,右边的不小于pivotmySwap(num[i], num[j]);}// 使中轴元素处于有序的位置num[left] num[j]; num[j] pivot; //经过上面的循环, j 后面就全是大于或等于 pivot 的数return j;
}// 快速排序
void QuickSort(vectorint num, int left, int right) {if (left right) {// 获取中轴元素所处的位置并进行分割int mid Partition(num, left, right);// 递归处理QuickSort(num, left, mid - 1);QuickSort(num, mid 1, right);}
}算法分析
时间复杂度O ( n ∗ l o g n )
空间复杂度O ( l o g n )
稳定性不稳定排序 堆排序Heap Sort
堆的定义
本文的堆是指数据结构堆不是内存模型的堆。堆是树型结构满足 ① 堆是一棵完全树 ② 堆中任意节点值总不大于(不小于)其子节点值 大顶堆的堆顶是最大值小顶堆则是最小值 常见堆有二叉堆、左倾堆、斜堆、二项堆、斐波那契堆等 二叉堆定义
堆通过 数组 实现父节点和子节点位置存在一定关系
有时将二叉堆第一个元素放在数组索引 0 位置有时放在 1 位置 若第一个元素放在数组索引 0 位置则父节点和子节点关系如下 1、索引为 i 的左孩子的索引是 (2 * i 1) 2、索引为 i 的左孩子的索引是 (2 * i 2) 3、索引为 i 的父结点的索引是 floor(( i - 1) / 2) 向下取整 若第一个元素放在数组索引 1 位置则父节点和子节点关系如下 1、索引为 i 左孩子的索引是 2*i 2、索引为 i 右孩子的索引是 2 * i 1 3、索引为 i 父结点的索引是 floor( i / 2) 二叉堆的图文解析
二叉堆核心是 添加 和 删除以 最大堆 举例 添加
在最大堆 [90, 80, 70, 60, 40, 30, 20, 10, 50] 种添加 85步骤如下 向最大堆添加数据时 先将数据加到最大堆末尾然后尽可能把这个元素往上挪直至挪不动 删除
在最大堆 [90, 85, 70, 60, 80, 30, 20, 10, 50, 40] 中删除 90步骤如下 从最大堆中删除数据先删除该数据然后用最大堆中最后一个元素插入这个空位接着把这个 空位 尽量往上挪直到剩余数据变成一个最大堆替换后树仍要是最大堆 堆排把堆顶元素与最后一个元素交换交换后破坏堆特性把堆中元素再次构成大顶堆然后把堆顶元素与最后第二个元素交换循环至剩余元素只有一个
// 下沉操作
void downAdjust(vectorint num, int parent, int n) { // 临时保存要下沉的元素 int temp num[parent]; // 定位左孩子节点的位置int child 2 * parent 1; // 开始下沉while (child n) {// 如果右孩子节点比左孩子大则定位到右孩子if (child 1 n num[child] num[child 1])child;// 如果孩子节点小于或等于父节点则下沉结束if (num[child] temp) break;// 父节点进行下沉num[parent] num[child];parent child;child 2 * parent 1;}num[parent] temp; //更新当前下沉值
}void HeapSort(vectorint num) {int len num.size();// 构建大顶堆for (int i (len - 2) / 2; i 0; --i) {downAdjust(num, i, len - 1);}// 进行堆排序for (int i len - 1; i 1; --i) {// 把堆顶元素与最后一个元素交换mySwap(num[0], num[i]);// 把打乱的堆进行调整恢复堆的特性downAdjust(num, 0, i - 1);}
}算法分析
时间复杂度O ( n ∗ l o g n )
空间复杂度O ( 1 )
稳定性不稳定排序 计数排序Counting Sort
适合最大值和最小值差值不是很大的情况。把数组元素作为数组的下标然后用一个临时数组统计该元素出现的次数例如 temp[i] m, 表示元素 i 一共出现了 m 次。最后再把临时数组统计的数据从小到大汇总起来此时汇总起来是数据是有序的
代码实现
// 计数排序
void CountingSort(vectorint num) { int len num.size();// 得到数列的最大和最小值int max num[0], min num[0]; for (int i 1; i len; i) { if(num[i] max) max num[i]; if (num[i] min)min num[i];}// 根据数列最大值确定统计数组的长度vectorint countArray(max - min 1, 0);// 遍历数列填充统计数组for (int i 0; i len; i) {countArray[num[i] - min];}// 遍历统计数组输出结果 int index 0; for (int i 0; i countArray.size(); i) {for (int j 0; j countArray[i]; j) {num[index] i min;}}
}算法分析
时间复杂度O ( n k ) 其中 k 为临时数组大小
空间复杂度O ( k )
稳定性稳定排序 桶排序Bucket Sort
把最大值和最小值之间数进行瓜分例如分成 10 个区间10个区间对应10个桶把各元素放到对应区间桶中再对每个桶中的数进行排序可以采用归并排序、快速排序等方法。之后每个桶里面的数据就是有序的了按顺序遍历各桶即可得到排序序列桶排序也可用于浮点数排序
动图演示 代码实现
// 桶排序
// 有负数的话需要进行预处理, 本函数包含预处理部分
void BucketSort(vectorint num) { int len num.size();// 得到数列的最大最小值int max num[0], min num[0]; for(int i 1; i len; i) { if(num[i] max) max num[i]; if (num[i] min)min num[i];}// 计算桶的数量并初始化int bucketNum (max - min) / len 1;vectorint vec;vectorvectorint bucket;for (int i 0; i bucketNum; i)bucket.push_back(vec);// 将每个元素放入桶for (int i 0; i len; i) {// 减去最小值处理后均为非负数int pos (num[i] - min) / len;bucket[pos].push_back(num[i]);}// 对每个桶进行排序此处可选择不同排序方法for (int i 0; i bucket.size(); i) sort(bucket[i].begin(), bucket[i].end());// 将桶中的元素赋值到原序列int index 0;for (int i 0; i bucketNum; i)for(int j 0; j bucket[i].size(); j)num[index] bucket[i][j];
}算法分析
时间复杂度O ( n k )
空间复杂度O ( k )
稳定性稳定排序 基数排序Radix Sort
先以个位数的大小来对数据进行排序接着以十位数的大小来进行排序接着以百位数的大小 ……
以某位数进行排序时用 桶 来排序由于某位数个位/十位….不是一整个数的大小范围为0~9所以我们需要10个桶然后把具有相同数值数放进同一个桶里之后再把桶里的数按照 0 号桶到 9 号桶的顺序取出来。一趟下来按照某位数的排序就完成了
代码实现
// 基数排序
// 有负数的话需要进行预处理本函数不包含预处理部分
void RadixSort(vectorint num) {int len num.size();// 得到数列的最大值int max num[0]; for (int i 1; i len; i) { if(num[i] max) max num[i];}// 计算最大值是几位数int times 1;while (max / 10 0) {times;max / 10;}// 创建10个桶vectorint vec;vectorvectorint bucket;for (int i 0; i 10; i) {bucket.push_back(vec);}// 进行每一趟的排序从个位数开始排for (int i 1; i times; i) {for (int j 0; j len; j) {// 获取每个数最后第 i 位对应桶的位置int radio (num[j] / (int)pow(10,i-1)) % 10;// 放进对应的桶里bucket[radio].push_back(num[j]);}// 合并放回原数组int k 0;for (int j 0; j 10; j) {for (int t : bucket[j]) {num[k] t;}//合并之后清空桶bucket[j].clear();} }
}算法分析
时间复杂度O ( k ∗ n )
空间复杂度O ( k n )
稳定性稳定排序 三 结语
身处于这个浮躁的社会却有耐心看到这里你一定是个很厉害的人吧
各位博友觉得文章有帮助的话别忘了点赞 关注哦你们的鼓励就是我最大的动力
博主还会不断更新更优质的内容加油吧技术人
