现有1G数据需要排序，计算资源只有1G内存可用，下列排序方法

[单选题]

现有1G数据需要排序，计算资源只有1G内存可用，下列排序方法中最可能出现性能问题的是____。

```
堆排序
```
```
插入排序
```
```
归并排序
```
```
快速排序
```
```
选择排序
```
```
冒泡排序
```

查看答案及解析

我是谁谁谁呢

排序法	平均时间	最差情形	稳定度	额外空间
冒泡	O(n2)	O(n2)	稳定	O(1)
交换	O(n2)	O(n2)	不稳定	O(1)
选择	O(n2)	O(n2)	不稳定	O(1)
插入	O(n2)	O(n2)	稳定	O(1)
基数	O(logRB)	O(logRB)	稳定	O(n)
Shell	O(nlogn)	O(ns) 1<s<2	不稳定	O(1)
快速	O(nlogn)	O(n2)	不稳定	O(logn)
归并	O(nlogn)	O(nlogn)	稳定	O(n)

发表于 2015-09-08 13:42:16 回复(6)

牛客418787号

#include <bits/stdc++.h>

using namespace std;

void Merge(int A[], int p, int q, int r){
    //We need extra O(n) space here!
    int* L = new int[q-p+2];
    int* R = new int[r-q+1];
    for(int i = p; i <= q; i++) L[i-p] = A[i];
    for(int i = q + 1; i <= r; i++) R[i-q-1] = A[i];
    L[q-p+1] = INT_MAX;
    R[r-q] =  INT_MAX;
    
    int i = 0, j = 0;    
    for(int k = p; k <= r; k++){
        A[k] = L[i] <= R[j]? L[i++] : R[j++];
    }
    delete[] L;
    delete[] R;
}

void MergeSort(int A[], int p, int r){
    if(p >= r) return;
    int q = p + (r - p)/2;
    MergeSort(A, p, q);
    MergeSort(A, q + 1, r);
    Merge(A, p, q, r);
}

int main()
{
   int arr[] = {33,12,19,9,34,32,27,51,8,11,42,29,18,65,5,38,14};
   int len = sizeof(arr)/sizeof(arr[0]);
   //printf("%d\n", len);
   MergeSort(arr, 0, len-1);
   for(int i = 0; i < len; i++){
       printf("%d ", arr[i]);
   }
   return 0;
}

在Merge函数里要用到额外的空间存储已经排好序的左子数组和右子数组。所以选择归并排序。

发表于 2016-04-13 13:38:56 回复(0)

任是无情也动人

冒泡排序,简单选择排序,堆排序,直接插入排序,希尔排序的空间复杂度为O(1),因为需要一个临时变量来交换元素位置,(另外遍历序列时自然少不了用一个变量来做索引)

快速排序空间复杂度为O(logn)~O(n)(因为递归调用了) ,

归并排序空间复杂是O(n),需要一个大小为n的临时数组.

基数排序的空间复杂是O(n),桶排序的空间复杂度不确定

发表于 2016-10-13 02:07:40 回复(0)

karaysn

归并排序需要0(n)的辅助空间

发表于 2017-11-03 11:35:59 回复(0)

Hepsilion

外部排序中的归并排序呢?

发表于 2017-04-27 11:15:50 回复(1)

小白再不学习就找不到工作啦

多路归并不行吗？

发表于 2017-03-08 11:53:35 回复(0)

河湖之恋

正确答案选C。

这道题主要是考察各种排序方法的空间复杂度

快速排序的空间复杂度为O(logn);归并排序的空间复杂度为O(n)；

其他选项的空间复杂度均为O(1)。

发表于 2015-08-24 10:50:05 回复(6)

***HW

归并是外排序啊，快排而且需要额外栈调用，所用空间是1G+Log（1G），归并可以避免空间问题啊

发表于 2016-07-08 16:34:33 回复(4)

雨芊儿

主要是考察各种排序方法的空间复杂度

请见下表，比较可知中最可能出现性能问题的是归并排序的辅助空间为O（n）

排序法	平均时间	最差情形	稳定度	额外空间
冒泡	O(n2)	O(n2)	稳定	O(1)
交换	O(n2)	O(n2)	不稳定	O(1)
选择	O(n2)	O(n2)	不稳定	O(1)
插入	O(n2)	O(n2)	稳定	O(1)
基数	O(logRB)	O(logRB)	稳定	O(n)
Shel l	O(nlogn)	O(ns) 1<s<2	不稳定	O(1)
快速	O(nlogn)	O(n2)	不稳定	O(nlogn)
归并	O(nlogn)	O(nlogn)	稳定	O(n)
堆	O(nlogn)	O(nlogn)	不稳定	O(1)

发表于 2015-08-30 22:15:42 回复(3)

牛客726231979号

在内存限制为1GB且需要排序的数据也达到了1GB时，最可能出现性能问题的排序算法是那些不是原地排序的，需要大量额外内存的算法。在此情况下，最可能出现性能问题的排序方法是**归并排序（Merge Sort）**，因为它需要与原始数据集大小相等的额外内存来进行合并操作。

传统的归并排序在每次合并步骤中需要一个大小与被合并的数据块一样大的额外空间来存放合并后的结果，这将导致在只有1GB内存而需要排序1GB数据的限制条件下，额外内存的需求无法得到满足，除非实现特别的外部合并排序，这种方法允许排序操作在磁盘上进行，能够处理比内存大的数据集。

然而，使用外部存储设施（如磁盘）会大大降低排序速度，因为它不得不进行频繁的磁盘读写操作，这些操作比内存操作要慢得多。尽管如此，外部归并排序可能是唯一一种可用的选项，因为其他需要更多内存的排序算法（如快速排序、堆排序等）在这种限制下都无法执行。

事实上，如果有1GB数据需要排序，并且计算资源只有1GB内存可用，那么一个通常的选择是使用外部排序算法，如外部归并排序（External Merge Sort），它将数据分成多个块，每个块大小小于或等于内存大小，分别对每个块进行排序，然后再将这些已排序的块合并成最终排序好的数据集。这种算法适用于数据量大于可用内存的情况。

发表于 2023-12-11 23:11:29 回复(0)