大家好, 一个刷不动算法的程序员。排序算法相关题目尽管在力扣中不是很多,但是面试中动不动要手撕一下。接下来,我们看一下十大基本排序,
什么是排序算法的稳定性呢?
当待排序记录的关键字均不相同时,排序结果是惟一的,否则排序结果不惟一[1]。
在待排序的文件中,若存在多个关键字相同的记录,经过排序后这些具有相同关键字的记录之间的相对次序保持不变,该排序方法是稳定的:
若具有相同关键字的记录之间的相对次序发生变化,则称这种排序方法是不稳定的。
排序算法的稳定性
排序算法的稳定性是针对所有输入实例而言的。即在所有可能的输入实例中,只要有一个实例使得算法不满足稳定性要求,那么这种排序算法就是不稳定的。
按在排序过程中是否涉及数据的内、外存交换来分类,排序大致分为两类:内部排序
和外部排序
。
按照是否通过比较来决定元素间的相对次序,排序可以分为比较类排序
和非比较类排序
。
排序分类
柿子挑软的捏,先从最简单的开始。
冒泡排序有着好听的名字,也有着最好理解的思路。
冒泡排序的基本思想是,从一端到另一端遍历,两两比较相邻元素的大小,如果是反序则交换。
动图如下(来源参考[4]):
冒泡排序
先简单实现以下,很简单,两层循环,相邻元素比较:
public void sort(int[] nums) {
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
//升序
if (nums[i] > nums[j]) {
//交换
int temp = nums[i];
nums[j] = nums[i];
nums[i] = temp;
}
}
}
}
上面的代码实现还存在一个问题,什么问题呢?
哪怕数组有序,它还是会接着遍历。
所以可以用一个标志位来标志数组是否有序,假如有序,就跳出遍历。
public void sort(int[] nums) {
//标志位
boolean flag = true;
for (int i = 0; i < nums.length; i++) {
for (int j = 0; j < nums.length - i - 1; j++) {
//升序
if (nums[j] > nums[j + 1]) {
//交换
int temp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = temp;
}
}
//如果是有序的,结束循环
if (flag) {
break;
}
}
}
大小相同的元素没有交换位置,所以冒泡排序是稳定的。
算法名称 | 最好时间复杂度 | 最坏时间复杂度 | 平均时间复杂度 | 空间复杂度 | 是否稳定 |
---|---|---|---|---|---|
是否稳定 | O(n) | O(n²) | O(n²) | O(1) | 稳定 |
选择排序为什么叫选择排序?原理是怎么样的呢?
它的思路:首先在未排序的序列中找到最小或者最大的元素,放到排序序列的起始位置,然后再从未排序的序列中继继续寻找最小或者最大元素,然后放到已经排序序列的末尾。以此类推,直到所有元素排序完毕。
来看一个例子,用选择排序的方式排序数组[2,5,4,1,3]
。
选择排序1
选择排序2
选择排序-3
选择排序4那么到这,我们的数组就是有序的了。
选择排序5
选择排序的思路很简单,实现起来也不难。
public void sort(int[] nums) {
int min = 0;
for (int i = 0; i < nums.length - 1; i++) {
for (int j = i + 1; j < nums.length; j++) {
//寻找最小的数
if (nums[j] < min) {
min = j;
}
}
//交换
int temp = nums[i];
nums[i] = nums[min];
nums[min] = temp;
}
}
选择排序稳定吗?
答案是不稳定的,因为在未排序序列中找到最小值之后,和排序序列的末尾元素交换。
算法名称 | 最好时间复杂度 | 最坏时间复杂度 | 平均时间复杂度 | 空间复杂度 | 是否稳定 |
---|---|---|---|---|---|
选择排序 | O(n²) | O(n²) | O(n²) | O(1) | 不稳定 |
关于插入排序,有一个非常形象的比喻。斗地主——摸到的牌都是乱的,我们会把摸到的牌插到合适的位置。
它的思路:将一个元素插入到已经排好序的有序序列中,从而得到一个新的有序序列。
动图如下(来源参考3):
插入排序
还是以数组[2,5,4,1,3]
为例:
插入排序1
插入排序2
插入排序4
插入排序5
OK,排序结束。
找到插入元素的位置,移动其它元素。
public void sort(int[] nums) {
//无序序列从1开始
for (int i = 1; i < nums.length; i++) {
//需要插入有序序列的元素
int value = nums[i];
int j = 0;
for (j = i - 1; j >= 0; j--) {
//移动数据
if (nums[j] > value) {
nums[j + 1] = nums[j];
} else {
break;
}
}
//插入元素
nums[j + 1] = value;
}
}
插入排序智慧移动比插入元素大的元素,所以相同元素相对位置不变,是稳定的。
从代码里我们可以看出,如果找到了合适的位置,就不会再进行比较了,所以最好情况时间复杂度是O(n)。
算法名称 | 最好时间复杂度 | 最坏时间复杂度 | 平均时间复杂度 | 空间复杂度 | 是否稳定 |
---|---|---|---|---|---|
插入排序 | O(n) | O(n²) | O(n²) | O(1) | 稳定 |
希尔排序,名字来自它的发明者Shell。它是直接插入排序的改进版。
希尔排序的思路是:把整个待排序的记录序列分割成若干个子序列,分别进行插入排序。
我们知道直接插入排序在面对大量无序数据的时候不太理想,希尔排序就是通过跳跃性地移动,来达到数组元素地基本有序,再接着用直接插入排序。
希尔排序动图(动图来源参考[1]):
希尔排序
还是以数组[2,5,6,1,7,9,3,8,4]
为例,我们来看一下希尔排序的过程:
希尔排序-1
希尔排序-2
希尔排序3
希尔排序4
希尔排序5
可以看看前面的插入排序,希尔排序
只是一个有步长的直接插入排序。
public void sort(int[] nums){
//下标差
int step=nums.length;
while (step>0){
//这个是可选的,也可以是3
step=step/2;
//分组进行插入排序
for (int i=0;i<step;i++){
//分组内的元素,从第二个开始
for (int j=i+step;j<nums.length;j+=step){
//要插入的元素
int value=nums[j];
int k;
for (k=j-step;k>=0;k-=step){
if (nums[k]>value){
//移动组内元素
nums[k+step]=nums[k];
}else {
break;
}
}
//插入元素
nums[k+step]=value;
}
}
}
}
希尔排序是直接插入排序的变形,但是和直接插入排序不同,它进行了分组,所以不同组的相同元素的相对位置可能会发生改变,所以它是不稳定的。
希尔排序的时间复杂度跟增量序列的选择有关,范围为 O(n^(1.3-2)) 在此之前的排序算法时间复杂度基本都是 O(n²),希尔排序是突破这个时间复杂度的第一批算法之一。
算法名称 | 时间复杂度 | 空间复杂度 | 是否稳定 |
---|---|---|---|
希尔排序 | O(n^(1.3-2)) | O(1) | 不稳定 |
归并排序是建立在归并操作上的一种有效的排序算法,归并,就是合并的意思,在数据结构上的定义就是把把若干个有序序列合并成一个新的有序序列
。
归并排序是分治法的典型应用,分治什么意思呢?就是把一个大的问题分解成若干个小的问题来解决。
归并排序的步骤,是把一个数组切分成两个,接着递归,一直到单个元素,然后再合并,单个元素合并成小数组,小数组合并成大数组。
动图如下(来源参考[4]):
归并排序
我们以数组[2,5,6,1,7,3,8,4]
为例,来看一下归并排序的过程:
归并排序
拆分就不用多讲了,我们看看怎么合并
。
这里使用递归来实现归并排序:
递归起始位置小于终止位置
直接对传入的数组序列进行排序,所以无返回值
将当前数组分成两组,分别分解两组,最后归并
代码如下:
public class MergeSort {
public void sortArray(int[] nums) {
sort(nums, 0, nums.length - 1);
}
/**
* 归并排序
*
* @param nums
* @param left
* @param right
*/
public void sort(int[] nums, int left, int right) {
//递归结束条件
if (left >= right) {
return;
}
int mid = left + (right - left) / 2;
//递归当前序列左半部分
sort(nums, left, mid);
//递归当前序列右半部分
sort(nums, mid + 1, right);
//归并结果
merge(nums, left, mid, right);
}
/**
* 归并
*
* @param arr
* @param left
* @param mid
* @param right
*/
public void merge(int[] arr, int left, int mid, int right) {
int[] tempArr = new int[right - left + 1];
//左边首位下标和右边首位下标
int l = left, r = mid + 1;
int index = 0;
//把较小的数先移到新数组中
while (l <= mid && r <= right) {
if (arr[l] <= arr[r]) {
tempArr[index++] = arr[l++];
} else {
tempArr[index++] = arr[r++];
}
}
//把左边数组剩余的数移入数组
while (l <= mid) {
tempArr[index++] = arr[l++];
}
//把右边剩余的数移入数组
while (r <= right) {
tempArr[index++] = arr[r++];
}
//将新数组的值赋给原数组
for (int i = 0; i < tempArr.length; i++) {
arr[i+left] = tempArr[i];
}
}
}
一趟归并,我们需要把遍历待排序序列遍历一遍,时间复杂度O(n)。
而归并排序的过程,需要把数组不断二分,这个时间复杂度是O(logn)。
所以归并排序的时间复杂度是O(nlogn)。
使用了一个临时数组来存储合并的元素,空间复杂度O(n)。
归并排序是一种稳定的排序方法。
算法名称 | 最好时间复杂度 | 最坏时间复杂度 | 平均时间复杂度 | 空间复杂度 | 是否稳定 |
---|---|---|---|---|---|
归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定 |
快速排序是面试最高频的排序算法。
快速排序和上面的归并排序一样,都是基于分治思想的,大概过程:
快速排序动图如下:
快速排序动图
我们来看一个完整的快速排序图示:
快速排序
选择一个数作为基准数pivot,同时设定一个标记 mark 代表左边序列最右侧的下标位置,接下来遍历数组,如果元素大于基准值,无操作,继续遍历,如果元素小于基准值,则把 mark + 1 ,再将 mark 所在位置的元素和遍历到的元素交换位置,mark 这个位置存储的是比基准值小的数据,当遍历结束后,将基准值与 mark 所在元素交换位置。
public class QuickSort0 {
public void sort(int[] nums) {
quickSort(nums, 0, nums.length - 1);
}
public void quickSort(int[] nums, int left, int right) {
//结束条件
if (left >= right) {
return;
}
//分区
int partitonIndex = partion(nums, left, right);
//递归左分区
quickSort(nums, left, partitonIndex - 1);
//递归右分区
quickSort(nums, partitonIndex + 1, right);
}
//分区
public int partion(int[] nums, int left, int right) {
//基准值
int pivot = nums[left];
//mark标记初始下标
int mark = left;
for (int i = left + 1; i <= right; i++) {
if (nums[i] < pivot) {
//小于基准值,则mark+1,并交换位置
mark++;
int temp = nums[mark];
nums[mark] = nums[i];
nums[i] = temp;
}
}
//基准值与mark对应元素调换位置
nums[left] = nums[mark];
nums[mark] = pivot;
return mark;
}
}
还有另外一种双边扫描的做法。
选择一个数作为基准值,然后从数组左右两边进行扫描,先从左往右找到一个大于基准值的元素,将它填入到right指针位置,然后转到从右往左扫描,找到一个小于基准值的元素,将他填入到left指针位置。
public class QuickSort1 {
public int[] sort(int[] nums) {
quickSort(nums, 0, nums.length - 1);
return nums;
}
public void quickSort(int[] nums, int low, int high) {
if (low < high) {
int index = partition(nums, low, high);
quickSort(nums, low, index - 1);
quickSort(nums, index + 1, high);
}
}
public int partition(int[] nums, int left, int right) {
//基准值
int pivot = nums[left];
while (left < right) {
//从右往左扫描
while (left < right && nums[right] >= pivot) {
right--;
}
//找到第一个比pivot小的元素
if (left < right) nums[left] = nums[right];
//从左往右扫描
while (left < right && nums[left] <= pivot) {
left++;
}
//找到第一个比pivot大的元素
if (left < right) nums[right] = nums[left];
}
//基准数放到合适的位置
nums[left] = pivot;
return left;
}
}
快速排序的时间复杂度和归并排序一样,都是O(nlogn),但是这是最优的情况,也就是每次都能把数组切分到两个差不多大小的子数组。
如果出现极端情况,例如一个有序的序列[5,4,3,2,1] ,选基准值为5,那么需要切分n-1次才能完成整个快速排序的过程,这种情况时间复杂度就退化到了O(n²)。
快速排序是一种原地排序的算法,空间复杂度是O(1)。
快排的比较和交换是跳跃进行的,所以快排是一种不稳定的排序算法。
算法名称 | 最好时间复杂度 | 最坏时间复杂度 | 平均时间复杂度 | 空间复杂度 | 是否稳定 |
---|---|---|---|---|---|
快速排序 | O(nlogn) | O(n²) | O(nlogn) | O(1) | 不稳定 |
还记得我们前面的简单选择排序吗?堆排序是简单选择排序的一种升级版。
在学习堆排序之前,什么是堆呢?
完全二叉树是堆的一个比较经典的堆实现。
我们先来了解一下什么是完全二叉树。
简答说,如果节点不满,那它不满的部分只能在最后一层的右侧。
我们来看几个示例。
完全二叉树和非完全二叉树
相信看了这几个示例,就清楚什么是完全二叉树
,什么是非完全二叉树
。
那堆
又是什么呢?
❝- 最大值时,称为“最大堆”,也称大顶堆;
- 最小值时,称为“最小堆”,也称小顶堆。
大、小顶堆
因为堆是完全二叉树,所以堆可以用数组存储。
按层来将元素存储到数组对应位置,从下标1开始存储,可以省略一些计算。
大顶堆存储
好了,我们现在对堆已经有一些了解了,我们来看一下堆排序是什么样的呢?[2]
动图如下(来源参考[1]):
堆排序动图(来自参考[1])
关于建堆,有两种方式,一种是上浮,一种是下沉。
上浮是什么呢?就是把子节点一层层上浮到合适的位置。
下沉是什么呢?就是把堆顶元素一层层下沉到合适的位置。
上面的动图,使用的就是下沉的方式。
public class HeapSort {
public void sort(int[] nums) {
int len = nums.length;
//建堆
buildHeap(nums, len);
for (int i = len - 1; i > 0; i--) {
//将堆顶元素和堆末元素调换
swap(nums, 0, i);
//数组计数长度减1,隐藏堆尾元素
len--;
//将堆顶元素下沉,使最大的元素浮到堆顶来
sink(nums, 0, len);
}
}
/**
* 建堆
*
* @param nums
* @param len
*/
public void buildHeap(int[] nums, int len) {
for (int i = len / 2; i >= 1; i--) {
//下沉
sink(nums, i, len);
}
}
/**
* 下沉操作
*
* @param nums
* @param index
* @param end
*/
public void sink(int[] nums, int index, int end) {
//左子节点下标
int leftChild = 2 * index + 1;
//右子节点下标
int rightChild = 2 * index + 2;
//要调整的节点下标
int current = index;
//下沉左子树
if (leftChild < end && nums[leftChild] > nums[current]) {
current = leftChild;
}
//下沉右子树
if (rightChild < end && nums[rightChild] > nums[current]) {
current = rightChild;
}
//如果下标不相等,证明调换过了
if (current!=index){
//交换值
swap(nums,index,current);
//继续下沉
sink(nums,current,end);
}
}
public void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
堆排的时间复杂度和快排的时间复杂度一样,都是O(nlogn)。
堆排没有引入新的空间,原地排序,空间复杂度O(1)。
堆顶的元素不断下沉,交换,会改变相同元素的相对位置,所以堆排是不稳定的。
算法名称 | 时间复杂度 | 空间复杂度 | 是否稳定 |
---|---|---|---|
堆排序 | O(nlogn) | O(1) | 不稳定 |
文章开始我们说了,排序分为比较类和非比较类,计数排序是一种非比较类的排序方法。
计数排序是一种线性时间复杂度的排序,利用空间来换时间,我们来看看计数排序是怎么实现的吧。
计数排序的大致过程[4]:
我们看一下动图演示(来自参考[4]):
计数排序动图,来自参考[4]
我们拿一个数组来看一下完整过程:[6,8,5,1,2,2,3]
计数排序-1
计数排序-2
计数排序-3
public class CountSort {
public void sort(int[] nums) {
//查找最大值
int max = findMax(nums);
//创建统计次数新数组
int[] countNums = new int[max + 1];
//将nums元素出现次数存入对应下标
for (int i = 0; i < nums.length; i++) {
int num = nums[i];
countNums[num]++;
nums[i] = 0;
}
//排序
int index = 0;
for (int i = 0; i < countNums.length; i++) {
while (countNums[i] > 0) {
nums[index++] = i;
countNums[i]--;
}
}
}
public int findMax(int[] nums) {
int max = nums[0];
for (int i = 0; i < nums.length; i++) {
if (nums[i] > max) {
max = nums[i];
}
}
return max;
}
}
OK,乍一看没啥问题,但是仔细想想,其实还是有些毛病的,毛病在哪呢?
如果我们要排序的元素有0怎么办呢?例如[0,0,5,2,1,3,4]
,arr初始都为0,怎么排呢?
这个很难解决,有一种办法,就是计数的时候原数组先加10,[-1,0,2],排序写回去的时候再减,但是如果刚好碰到有-10这个元素就凉凉。
如果元素的范围很大呢?例如[9992,9998,9993,9999]
,那我们申请一个10000个元素的数组吗?
这个可以用偏移量解决,找到最大和最小的元素,计算偏移量,例如[9992,9998,9993,9999]
,偏移量=9999-9992=7,我们只需要建立一个容量为8的数组就可以了。
解决第二个问题的版本如下:
public class CountSort1 {
public void sort(int[] nums) {
//查找最大值
int max = findMax(nums);
//寻找最小值
int min = findMin(nums);
//偏移量
int gap = max - min;
//创建统计次数新数组
int[] countNums = new int[gap + 1];
//将nums元素出现次数存入对应下标
for (int i = 0; i < nums.length; i++) {
int num = nums[i];
countNums[num - min]++;
nums[i] = 0;
}
//排序
int index = 0;
for (int i = 0; i < countNums.length; i++) {
while (countNums[i] > 0) {
nums[index++] = min + i;
countNums[i]--;
}
}
}
public int findMax(int[] nums) {
int max = nums[0];
for (int i = 0; i < nums.length; i++) {
if (nums[i] > max) {
max = nums[i];
}
}
return max;
}
public int findMin(int[] nums) {
int min = nums[0];
for (int i = 0; i < nums.length; i++) {
if (nums[i] < min) {
min = nums[i];
}
}
return min;
}
}
我们整体运算次数是n+n+n+k=3n+k,所以使劲复杂度是O(n+k)。
引入了辅助数组,空间复杂度O(n)。
我们的实现实际上是不稳定的,但是计数排序是有稳定的实现的,可以查看参考[1]。
同时我们通过实现也发现,计数排序实际上不适合有负数的,元素偏移值过大的数组。
桶数组可以看做计数排序的升级版,它把元素分到若干个桶
中,每个桶中的元素再单独排序。
桶排序大概的过程:
桶排序动图如下(动图来源参考[1]):
桶排序动图(来源参考[1])
我们上面说了,计数排序不适合偏移量过大的数组,我们拿一个偏移量非常大的数组[2066,566,166,66,1066,2566,1566]
为例,来看看桶排序的过程。
桶排序-1
桶排序-2
桶排序-3
桶排序-4
桶排序的实现我们要考虑几个问题:
我们来看一下代码:
public class BucketSort {
public void sort(int[] nums) {
int len = nums.length;
int max = nums[0];
int min = nums[0];
//获取最大值和最小值
for (int i = 1; i < len; i++) {
if (nums[i] > max) {
max = nums[i];
}
if (nums[i] < min) {
min = nums[i];
}
}
//计算步长
int gap = max - min;
//使用列表作为桶
List<List<Integer>> buckets = new ArrayList<>();
//初始化桶
for (int i = 0; i < gap; i++) {
buckets.add(new ArrayList<>());
}
//确定桶的存储区间
int section = gap / len - 1;
//数组入桶
for (int i = 0; i < len; i++) {
//判断元素应该入哪个桶
int index = nums[i] / section - 1;
if (index < 0) {
index = 0;
}
//对应的桶添加元素
buckets.get(index).add(nums[i]);
}
//对桶内的元素排序
for (int i = 0; i < buckets.size(); i++) {
//这个底层调用的是 Arrays.sort
// 这个api不同情况下可能使用三种排序:插入排序,快速排序,归并排序,具体看参考[5]
Collections.sort(buckets.get(i));
}
//将桶内的元素写入原数组
int index = 0;
for (List<Integer> bucket : buckets) {
for (Integer num : bucket) {
nums[index] = num;
index++;
}
}
}
}
桶排序最好的情况,就是元素均匀分配到了每个桶,时间复杂度O(n),最坏情况,是所有元素都分配到一个桶中,时间复杂度是O(n²)。平均的时间复杂度和技术排序一样,都是O(n+k)。
桶排序,需要存储n个额外的桶,桶中又要存储k个元素,所以空间复杂度是O(n+k)。
稳定性得看桶中排序用的什么排序算法,桶中用的稳定排序算法,那么就是稳定的。用的不稳定的排序算法,那么就是不稳定的。
基数排序是一种非比较型的排序方法。
它的基本原理是将元素按照位数切割成不同的数字,然后按照每个位数进行比较。
大概过程:
动图图示如下(来源参考[4]):
基数排序-来源参考[4]
基数排序可以说是桶排序的一个进化,我们以[ 892, 846, 821, 199, 810,700 ]
来看一下基数排序的过程:
桶排序-1
基数排序-2
基数排序-3
基数排序-3
基数排序-4
public class RadixSort {
public void sort(int[] nums) {
int len = nums.length;
//最大值
int max = nums[0];
for (int i = 0; i < len; i++) {
if (nums[i] > max) {
max = nums[i];
}
}
//当前排序位置
int location = 1;
//用列表实现桶
List<List<Integer>> buckets = new ArrayList<>();
//初始化size为10的一个桶
for (int i = 0; i < 10; i++) {
buckets.add(new ArrayList<>());
}
while (true) {
//元素最高位数
int d = (int) Math.pow(10, (location - 1));
//判断是否排完
if (max < d) {
break;
}
//数据入桶
for (int i = 0; i < len; i++) {
//计算余数 放入相应的桶
int number = ((nums[i] / d) % 10);
buckets.get(number).add(nums[i]);
}
//写回数组
int nn = 0;
for (int i = 0; i < 10; i++) {
int size = buckets.get(i).size();
for (int ii = 0; ii < size; ii++) {
nums[nn++] = buckets.get(i).get(ii);
}
buckets.get(i).clear();
}
location++;
}
}
}
时间复杂度O(n+k),其中n数组元素个数,k为数组元素最高位数。
和桶排序一样,因为引入了桶的存储空间,所以空间复杂度O(n+k)。
因为基数排序过程,每次都是将当前位数是哪个相同数值的元素统一分配到桶中,并不交换位置,所以基数排序是稳定的。
这篇文章,我们学习了十大基本排序,来简单总结一下。
首先最简单的冒泡排序
:两层循环,相邻交换;
选择排序
:未排序和排序两分,从未排序序列中寻找最小的元素,放在排序序列末尾;
插入排序
:斗地主摸牌思维,把一个元素插入到有序序列合适位置;
希尔排序
:插入排序plus,先把序列分割,再分别插入排序;
归并排序
:分治思想第一弹,先将序列切分,再在合并过程排序;
快速排序
:分治思想第二弹,基准数分区原序列,小的放左边,大的放右边;
堆排序
:选择排序plus,建立大顶堆,堆顶元素(最大值)插入序列末尾,再让新的元素上浮。
计数排序
:空间换时间第一弹,利用新数组,统计对应元素出现次数,输出新数组下标,原数组完成排序;
桶排序
:空间换时间第二弹,将原数组的元素分到若干个桶,每个桶单独排序,再把桶里元素拼起来;
基数排序
:空间换时间第三弹,桶排序plus,根据数位,把元素分桶,然后按每个位数比较。
十大基本排序性能汇总:
排序方法 | 时间复杂度(平均) | 时间复杂度(最坏) | 时间复杂度(最好) | 空间复杂度 | 稳定性 |
---|---|---|---|---|---|
冒泡排序 | O(n²) | O(n²) | O(n) | O(1) | 稳定 |
选择排序 | O(n²) | O(n²) | O(n²) | O(1) | 不稳定 |
插入排序 | O(n²) | O(n²) | O(n) | O(1) | 稳定 |
希尔排序 | O(n^(1.3-2)) | O(n²) | O(n) | O(1) | 不稳定 |
归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定 |
快速排序 | O(nlogn) | O(n²) | O(nlogn) | O(nlogn) | 不稳定 |
堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不稳定 |
计数排序 | O(n+k) | O(n+k) | O(n+k) | O(n) | 稳定 |
桶排序 | O(n+k) | O(n²) | O(n) | O(n+k) | 稳定 |
基数排序 | O(n*k) | O(n*k) | O(n*k) | O(n+k) | 稳定 |
❝简单的事情重复做,重复的事情认真做,认真的事情有创造性地去做。
参考:
本文由哈喽比特于2年以前收录,如有侵权请联系我们。
文章来源:https://mp.weixin.qq.com/s/9GCvB3W9Bq2VPsZavUlP8w
京东创始人刘强东和其妻子章泽天最近成为了互联网舆论关注的焦点。有关他们“移民美国”和在美国购买豪宅的传言在互联网上广泛传播。然而,京东官方通过微博发言人发布的消息澄清了这些传言,称这些言论纯属虚假信息和蓄意捏造。
日前,据博主“@超能数码君老周”爆料,国内三大运营商中国移动、中国电信和中国联通预计将集体采购百万台规模的华为Mate60系列手机。
据报道,荷兰半导体设备公司ASML正看到美国对华遏制政策的负面影响。阿斯麦(ASML)CEO彼得·温宁克在一档电视节目中分享了他对中国大陆问题以及该公司面临的出口管制和保护主义的看法。彼得曾在多个场合表达了他对出口管制以及中荷经济关系的担忧。
今年早些时候,抖音悄然上线了一款名为“青桃”的 App,Slogan 为“看见你的热爱”,根据应用介绍可知,“青桃”是一个属于年轻人的兴趣知识视频平台,由抖音官方出品的中长视频关联版本,整体风格有些类似B站。
日前,威马汽车首席数据官梅松林转发了一份“世界各国地区拥车率排行榜”,同时,他发文表示:中国汽车普及率低于非洲国家尼日利亚,每百户家庭仅17户有车。意大利世界排名第一,每十户中九户有车。
近日,一项新的研究发现,维生素 C 和 E 等抗氧化剂会激活一种机制,刺激癌症肿瘤中新血管的生长,帮助它们生长和扩散。
据媒体援引消息人士报道,苹果公司正在测试使用3D打印技术来生产其智能手表的钢质底盘。消息传出后,3D系统一度大涨超10%,不过截至周三收盘,该股涨幅回落至2%以内。
9月2日,坐拥千万粉丝的网红主播“秀才”账号被封禁,在社交媒体平台上引发热议。平台相关负责人表示,“秀才”账号违反平台相关规定,已封禁。据知情人士透露,秀才近期被举报存在违法行为,这可能是他被封禁的部分原因。据悉,“秀才”年龄39岁,是安徽省亳州市蒙城县人,抖音网红,粉丝数量超1200万。他曾被称为“中老年...
9月3日消息,亚马逊的一些股东,包括持有该公司股票的一家养老基金,日前对亚马逊、其创始人贝索斯和其董事会提起诉讼,指控他们在为 Project Kuiper 卫星星座项目购买发射服务时“违反了信义义务”。
据消息,为推广自家应用,苹果现推出了一个名为“Apps by Apple”的网站,展示了苹果为旗下产品(如 iPhone、iPad、Apple Watch、Mac 和 Apple TV)开发的各种应用程序。
特斯拉本周在美国大幅下调Model S和X售价,引发了该公司一些最坚定支持者的不满。知名特斯拉多头、未来基金(Future Fund)管理合伙人加里·布莱克发帖称,降价是一种“短期麻醉剂”,会让潜在客户等待进一步降价。
据外媒9月2日报道,荷兰半导体设备制造商阿斯麦称,尽管荷兰政府颁布的半导体设备出口管制新规9月正式生效,但该公司已获得在2023年底以前向中国运送受限制芯片制造机器的许可。
近日,根据美国证券交易委员会的文件显示,苹果卫星服务提供商 Globalstar 近期向马斯克旗下的 SpaceX 支付 6400 万美元(约 4.65 亿元人民币)。用于在 2023-2025 年期间,发射卫星,进一步扩展苹果 iPhone 系列的 SOS 卫星服务。
据报道,马斯克旗下社交平台𝕏(推特)日前调整了隐私政策,允许 𝕏 使用用户发布的信息来训练其人工智能(AI)模型。新的隐私政策将于 9 月 29 日生效。新政策规定,𝕏可能会使用所收集到的平台信息和公开可用的信息,来帮助训练 𝕏 的机器学习或人工智能模型。
9月2日,荣耀CEO赵明在采访中谈及华为手机回归时表示,替老同事们高兴,觉得手机行业,由于华为的回归,让竞争充满了更多的可能性和更多的魅力,对行业来说也是件好事。
《自然》30日发表的一篇论文报道了一个名为Swift的人工智能(AI)系统,该系统驾驶无人机的能力可在真实世界中一对一冠军赛里战胜人类对手。
近日,非营利组织纽约真菌学会(NYMS)发出警告,表示亚马逊为代表的电商平台上,充斥着各种AI生成的蘑菇觅食科普书籍,其中存在诸多错误。
社交媒体平台𝕏(原推特)新隐私政策提到:“在您同意的情况下,我们可能出于安全、安保和身份识别目的收集和使用您的生物识别信息。”
2023年德国柏林消费电子展上,各大企业都带来了最新的理念和产品,而高端化、本土化的中国产品正在不断吸引欧洲等国际市场的目光。
罗永浩日前在直播中吐槽苹果即将推出的 iPhone 新品,具体内容为:“以我对我‘子公司’的了解,我认为 iPhone 15 跟 iPhone 14 不会有什么区别的,除了序(列)号变了,这个‘不要脸’的东西,这个‘臭厨子’。