十万个无序数字怎么快速排序

Question

• 另一个问题：十万个无序数字怎么平均分成两堆，保证前一堆的每个数字都比后一堆

怎么排快一点，随机选基准然后快排吗

Answer 1

• 思路：找出大小为n的数组vec的中位数，以中位数为基准对数组进行划分。
• 时间复杂度：O(n)。
• 空间复杂度：O(1)。

• 具体步骤

  • 以中位数为基准进行划分。
    当n为偶数，中位数在第n/2大的数和第(n/2)+1大的数中。因为是划分成相等的两堆，以第n/2大的数为基准划分即可，大的划分到右边，其余划分到左边。（当n为奇数，同理可推，就不再论述）
  • 寻找中位数。
    从上面可看出，寻找中位数即寻找数组中第K大的数。而寻找数组中第K大的数的算法有很多，而一种时间复杂度为O(n)且空间复杂度为O(1)的算法则是：类似于快排对数组进行划分，但与快排不同的是：因为寻找的是第K大的数，第K大的数只会在其中一组，所以只对第K大的数的那一组进行递归划分。时间复杂度是O(n)。算法的具体细节可见相关博客，搜索下关键词“寻找 第k大 数”就看见有很多博客具体分析了这个算法。
  • 实质上以类快排方式划分的过程中，就已经把大于中位数的数划分到数组右边，其余划分到数组左边了。找到中位数的时候，也就是划分完成了。

Answer 2

快排的时候，对剩下的数据用随机的方法选取三个数据，取中间的数据来做基点。这样可以稍微快那么一点点。。。

Answer 3

首答，欢迎追问与提意见，先说我的思路，用桶，以空间换时间的方式得到最快速度的答案，C代码在最下面，已测试。

测试结果：

思考了一会，按照常规方法走，如果没有特殊要求，用排序是可以的。最快的排序算法是时间复杂度是 O(nlogn)
十万的数据量的复杂度，也就是进行 100000*log(100000) = 17万次运算。

以现在计算机的运算速度（单位是每秒百万条指令），如果你不是做一些有时间限制的竞赛(ACM)的话，是完全可以的。

但这道题如果放在ACM竞赛中，如果用排序方法去做应该是铁铁的超时了。
于是我用桶（C语言桶的概念不懂请百度）做了一个以空间换时间的折中算法，时间复杂度是O(n)，也就是10万次运算。空间复杂度取决于最大数字。如果最大数字是10万，就要开辟10万的数组空间，如果最大数字是20万，就要开辟20万的数组空间。如果最大数字是一百万，就要开辟一百万数组大小的空间，C语言不支持开辟这么多连续的内存空间，如果你真有这个问题，可以在segmentfault上提一个新问题，或者在答案下追问。

具体思路：
结果分为两个堆：0堆和1堆。
用桶存放所有元素的出现次数，对桶进行遍历，记录数组中所有的元素出现次数之和为count，当count>=N/2时（N在这里为10万），停止遍历。
[1] 这时遍历过的就是在左边堆的了。没遍历过的就是在右边堆里的了。

比如

                  3 2 1 4 5 3
排序后            1 2 3 3 4 5
桶(记为b)的状态： b[0]=0, b[1]=1, b[2]=1, b[3]=2, b[4]=1, b[5]=1

当遍历到b[3]的时候，count为4，已经大于3了(元素个数/2)。这时候记录一下中间数的位置

然后根据上面思路[1] 就很容易得出1 2 3 3 都是在左边堆的，
4 5 都是在右边堆的。

这时候出现了一个bug，有两个3，其中1个3应该在右边。
这个问题很好解决，上例中，count在停止记数的时候为4，4与3相比较多了1，证明多加了一个。所以要把最后一个移到右边堆。

C语言代码

把N改成10万，记得把printf该关的关掉。

#include<stdio.h>
#include<stdlib.h>

#define N 19
#define MAX 32767

int main()
{
    int a[N] = {0}, b[MAX] = {0};
    int count = 0, position = -1;
    
    printf("the random data is \n\n");
    for(int i=0; i<N; i++)
    {
        a[i] = (int)(rand() % MAX);        //产生MAX以下的随机数 
        b[a[i]]++;                        //统计每个数字出现的次数 
        printf("%5d ",a[i]);
    }
    
    for(int i=0; i<MAX; i++)
    {
        if(b[i] == 0)
            continue;
        count += b[i];                    //统计从小到大所有的数字出现的次数
        if(count >= N/2) 
        {
            position = i;                //找到分界点时记录位置 
            break;
        }
    }
    
    printf("\n-----------------\n\nthe result is\n\n");
    int temp = 0;
    for(int i=0; i<N; i++)
    {
        if(a[i] < position)
            printf(" left ");
        else if(a[i] == position)
        {
            if(++temp <= b[a[i]]-(count-N/2))        //左右分界点的值出现多次的时候，控制一下。 
                printf(" left ");
            else
                printf("right ");
        }
        else
            printf("right ");
    }
    
    printf("\n\n>>>>>>  Middle is %5d\n",position);
    
    return 0;
}

PS：其实我感觉应该有不浪费空间又可以节省时间的方法，但想了半天没想出来，如果有更好的答案望分享。
我是学Java的，也专门学习过一些算法知识，正在往全栈方面发展。有兴趣可以加个兴趣群一起交流，群号374660776

Answer 4

搞个P啊，那最后合并还不是要用到N内存？怎么用N/4内存或者更少？