最快的排序算法是什么

最快的排序算法是什么，很多人的第一反应是快排，感觉QuickSort 当然应该最快了，其实并非如此，快排是不稳定的，最坏情况下，快排序并不是最优，Java7 中引入的 TimSort 就是一个结合了插入排序和归并排序的高效算法

Timsort最早是 Tim Peters 于2001年为 Python 写的排序算法。自从发明该算法以来，它已被用作Python，Java，Android平台和GNU Octave中的默认排序算法。

关于此算法的详细描述参见 >

1、“快速排序法”使用的是递归原理，下面一个例子来说明“快速排序法”的原理。首先给出一个数组{53，12，98，63，18，72，80，46， 32，21}，先找到第一个数--53，把它作为中间值，也就是说，要把53放在一个位置，使得它左边的值比它小，右边的值比它大。{21，12，32， 46，18，53，80，72，63，98}，这样一个数组的排序就变成了两个小数组的排序--53左边的数组和53右边的数组，而这两个数组继续用同样的方式继续下去，一直到顺序完全正确。一般来说，冒泡法是程序员最先接触的排序方法，它的优点是原理简单，编程实现容易，但它的缺点就是速度太慢。
2、快速排序代码：

#include<stdioh>
void quicksort(int a[],int left,int right)
{
    int i,j,temp;
    i=left;
    j=right;
    temp=a[left];
    if(left>right)
        return;
    while(i!=j)
    {
        while(a[j]>=temp&&j>i)
            j--;
        if(j>i)
            a[i++]=a[j];
        while(a[i]<=temp&&j>i)
            i++;
        if(j>i)
            a[j--]=a[i];
        
    }
    a[i]=temp;
    quicksort(a,left,i-1);
    quicksort(a,i+1,right);
}
void main()
{
    int a[]={53,12,98,63,18,72,80,46,32,21};
    int i;
    quicksort(a,0,9);
    /排好序的结果/
    for(i=0;i<10;i++)
        printf("%4d\n",a[i]);
}

上期为大家介绍了快速排序（Quicksort），有很多同学会问： 快排是不是比之前几种排序都要快？它到底有多快？ ，那就让我们一起来做个小实验测试一下吧！

目前给大家介绍过了6种排序：冒泡排序、选择排序、
插入排序、希尔排序、归并排序、快速排序，并且在上期讲 快速排续 时给出了快排的优化方案：对于大数据集排序先使用 快排 ，当分区达到一定小的时候使用 插入排序 ，有同学就有疑惑：为什么当分区达到一定小时要用 插入排序 ，这样真的会变快吗？

冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序

随机生成一个数据集，数据个数从10，100，1000依次递增到10万个

比较每个排序算法所用时长，多次测试，减少误差

首先对 随机数 进行排序，看看哪个排序方法较快；然后再对“ 基本有序 ”的数据集排序，再比较这几种排序方法用时。

使用randint随机生成整数

数据集生成的基本思路：先生成一个有序数列，然后将少量数据插入有序数列中，这里取 01n 个乱序插入到 09n 个有序数列中。

时间单位是秒，多次测试结果基本差不多，这里猪哥随机选取依次测试结果， 全场敷冰进行，请勿模仿 ：

冒泡排序耗时：24080276489257812e-05
选择排序耗时：19311904907226562e-05
插入排序耗时：15020370483398438e-05
希尔排序耗时：15974044799804688e-05
归并排序耗时：28848648071289062e-05
快速排序耗时：19073486328125e-05

冒泡排序耗时：0000782012939453125
选择排序耗时：00004570484161376953
插入排序耗时：000039076805114746094
希尔排序耗时：000018095970153808594
归并排序耗时：00003409385681152344
快速排序耗时：000017905235290527344

冒泡排序耗时：008327889442443848
选择排序耗时：003776884078979492
插入排序耗时：004986977577209473
希尔排序耗时：00034036636352539062
归并排序耗时：0005920886993408203
快速排序耗时：00021750926971435547

冒泡排序耗时：8781844854354858
选择排序耗时：3438148021697998
插入排序耗时：4186453819274902
希尔排序耗时：005663800239562988
归并排序耗时：006386470794677734
快速排序耗时：002335190773010254

冒泡排序耗时：9005480690002441
选择排序耗时：8791669909954071
插入排序耗时：42866180515289307
希尔排序耗时：0967015266418457
归并排序耗时：14872560501098633
快速排序耗时：03050980567932129

再经过几小时等待后，我仿佛闻到一股烧焦的味道，真香～

冒泡排序耗时：2288818359375e-05
选择排序耗时：19788742065429688e-05
插入排序耗时：13113021850585938e-05
希尔排序耗时：15974044799804688e-05
归并排序耗时：29087066650390625e-05
快速排序耗时：1811981201171875e-05

冒泡排序耗时：00004851818084716797
选择排序耗时：00004131793975830078
插入排序耗时：000013065338134765625
希尔排序耗时：000015997886657714844
归并排序耗时：000032019615173339844
快速排序耗时：000015974044799804688

冒泡排序耗时：005040717124938965
选择排序耗时：003394508361816406
插入排序耗时：0009570121765136719
希尔排序耗时：00029370784759521484
归并排序耗时：0005821943283081055
快速排序耗时：00022530555725097656

冒泡排序耗时：524026083946228
选择排序耗时：3340329885482788
插入排序耗时：08101489543914795
希尔排序耗时：004622912406921387
归并排序耗时：005988883972167969
快速排序耗时：0023930788040161133

无

我们从两种数据结果看，冒泡几乎都是最慢的

我们看到在随机数排序结果中，只有当 n=10 时，快排反而比较慢，而插入和希尔排序相对较快，这是因为插入排序和希尔排序都属于插入类型的排序，而快排和冒泡属于交换类排序，数据量少时交换所消耗的资源占比大。

在基本有序数据排序结果中，当n=10和n=100中都是插入排序消耗时间更短，因为数据基本有序，所以需要插入的次数比较少，尽管插入排序需要一个一个比较，但因为数据量不大，所以比较所消耗的资源占比不会太大。

快排果然还是名副其实的快，我们看到当数据集达到十万级别时，冒泡排序已经用时800多秒，而快排只用了03秒，相信随着数据量的增大，它们之间的差距也会越来越大。

之前我们讲过快排优化方案：对于大数据集排序先使用 快排 ，使数据集达到 基本有序 ，然后当分区达到一定小的时候使用 插入排序 ，因为插入排序对少量的基本有序数据集性能优于快排！

---