精华内容
下载资源
问答
  • 高效排序算法

    千次阅读 2018-05-13 16:28:26
    采用分治的思想:首先设置一个轴值pivot,然后以这个轴值为划分基准将待排序序列分成比pivot大和比pivot小的两部分,接下来对划分完的子序列进行快排直到子序列为一个元素为止。public void quickSort(int array[]...

    特点:高效,时间复杂度为nlogn。

    采用分治法的思想:首先设置一个轴值pivot,然后以这个轴值为划分基准将待排序序列分成比pivot大和比pivot小
    的两部分,接下来对划分完的子序列进行快排直到子序列为一个元素为止。
    public void quickSort(int array[], int low, int high) {// 传入low=0,high=array.length-1;
            int pivot, p_pos, i, t;// pivot->位索引;p_pos->轴值。
            if (low < high) {
                p_pos = low;
                pivot = array[p_pos];
                for (i = low + 1; i <= high; i++)
                    if (array[i] > pivot) {
                        p_pos++;
                        t = array[p_pos];
                        array[p_pos] = array[i];
                        array[i] = t;
                    }
                t = array[low];
                array[low] = array[p_pos];
                array[p_pos] = t;
                // 分而治之
                quickSort(array, low, p_pos - 1);// 排序左半部分
                quickSort(array, p_pos + 1, high);// 排序右半部分
            }


    展开全文
  • 如标题,这里讨论的是基于比较的排序算法中最高效的三种算法和希尔排序。堆排序、归并排序、快速排序的平均时间复杂度均为O(NlogN)。前面有介绍过O(N2)的三种简单排序算法(见三大简单排序算法——插入、选择、冒泡...

    如标题,这里讨论的是基于比较的排序算法中最高效的三种算法和希尔排序。堆排序、归并排序、快速排序的平均时间复杂度均为O(NlogN)。前面有介绍过O(N2)的三种简单排序算法(见三大简单排序算法——插入、选择、冒泡),其中实际表现最好的要属希尔排序。可以证明通过交换相邻元素来进行排序的任何算法都需要O(N2)的平均时间,其中插入排序虽然不是通过交换来排序,但是可以等价为交换的操作,依然是O(N2)。这里讨论的堆排序、归并排序、快速排序均是平均时间复杂度O(NlogN)的算法,实际表现最好的要属快速排序。可以证明O(NlogN)是基于比较的排序算法的时间复杂度下界。所以这三种排序算法都是渐进最优的。最后介绍一下C++的algorithm库中的sort()函数,一般我们自己写的排序算法优化不够时都是达不到这个效率的。还有会对这些算法在大规模数据下的运行时间进行一个简单的测试。

    排序算法相关知识

    逆序:逆序是指数组中具有性质 i>j i > j 但是 A[i]<A[j] A [ i ] < A [ j ] 的序偶 (A[i],A[j]) ( A [ i ] , A [ j ] ) 。(升序排列的情况,反之亦然)

    排序的过程就是消除逆序的过程。很明显逆序的最大数目为 N1i=1i=N(N1)2 ∑ i = 1 N − 1 i = N ( N − 1 ) 2 ,平均情况下逆序数目为最大的一半即 N(N1)/4 N ( N − 1 ) / 4

    很容易看出,通过交换相邻元素一次最多只能消除一个逆序。所以通过交换相邻元素来排序的算法的平均时间复杂度一定为 O(N2) O ( N 2 )

    而要突破 O(N2) O ( N 2 ) 的时间屏障,就必须在一次交换/操作中消除不止一个逆序。下面的排序算法都有这个特点。

    另外如果下列实现中有要交换元素的均调用如下的模板。

    template<typename T>
    void swap(T & x , T & y)
    {
        T tmp = x;
        x = y;
        y = tmp;
    }

    希尔排序

    希尔排序(Shell sort)是第一批冲破 O(N2) O ( N 2 ) 时间屏障的算法之一。也称缩小增量排序。上一篇(三大简单排序算法——插入、选择、冒泡)介绍得很详细。这里贴出代码。

    //希尔排序,效率惊人
    void Shell_sort(ElemType A[],int n)
    {
        for(int d=n/2; d>0; d/=2)
        {
            for(int i=d; i<n; i++)
            {
                ElemType tmp = A[i];
                int j = i-d;
                while(j >= 0 && tmp < A[j])
                {
                    A[j+d] = A[j];
                    j = j-d;
                }
                A[j+d] = tmp;
            }
        }
    }

    这里的增量序列是 n/2,n/4,...,1 n / 2 , n / 4 , . . . , 1 ,为最原始的希尔序列。但这并不是高效的增量序列,一个更加高效的增量序列为Hibbard增量,形如 1,3,7,...,2k1 1 , 3 , 7 , . . . , 2 k − 1 (使用时需要从合适的位置逆序),可以证明Hibbard增量的希尔排序最坏情形时间复杂度为 O(N3/2) O ( N 3 / 2 ) 。希尔排序的算法实现很简单,但是分析却是很困难的。其实还有更好的增量序列,可以参见 Shellsort - Wikipedia - Gap sequences
    动图演示(以下动图均来自Wikipedia):
    此处输入图片的描述

    堆排序

    heap sort,这个介绍堆时也是介绍的很详细的。见基本数据结构——堆优先队列 & 堆
    实现:

    //升序排列、最大堆 
    void sift_down(ElemType A[],int i,int n)
    {
        ElemType tmp;
        int child;
        for(tmp = A[i]; 2*i <= n; i = child)
        {
            child = 2*i;
            if(child != n && A[child+1] > A[child])
                child ++;
            if(tmp < A[child])
                A[i] = A[child];
            else 
                break; 
        }
        A[i] = tmp;
    }
    //将数组建堆然后排序——升序 
    void heap_sort(ElemType A[],int n)
    {
        for(int i = n/2; i>0; i--)
            sift_down(A,i,n);
        for(int i=n; i>1; i--)
        {
            swap<ElemType>(A[1],A[i]);
            sift_down(A,1,i-1);
        }
    }

    需要注意的是这里堆排序的实现要求给数组多分配一个内存。当然可以将其改为与其他排序一致,这很容易做到,但我个人更偏向于现在这种实现。
    动图演示:
    此处输入图片的描述

    归并排序

    归并排序(Merge sort)采用分治策略。思路也很简单:将数组分为两个等长子数组,对两个子数组递归采用归并排序来排序,然后将两个数组合并,其中递归结束条件为子数组长为1直接返回。则时间 T(N)=T(N/2)+N T ( N ) = T ( N / 2 ) + N ,由主定理得到时间复杂度为 O(NlogN) O ( N l o g N )

    实现也很清晰很简单。

    void merge_sort(ElemType A[], int n)
    {
        ElemType * TmpArr = new ElemType[n];
        m_sort(A,TmpArr,0,n-1);
        delete [] TmpArr;
    }
    void m_sort(ElemType A[], ElemType TmpArr[], int left, int right)
    {
        if(left < right)
        {
            int center = (left + right) / 2;
            m_sort(A, TmpArr, left, center);
            m_sort(A, TmpArr, center+1, right);
            merge(A, TmpArr, left, center+1, right);
        }
    }
    //两个子数组的合并,lpos~rpos-1 and rpos~rightend ,临时存储在TmpArr[rpos~rightend] 
    void merge(ElemType A[], ElemType TmpArr[], int lpos, int rpos, int rightend)
    {
        int leftend = rpos - 1;
        int tmppos = lpos;
        int begin = lpos;
        while(lpos <= leftend && rpos <= rightend)
        {
            if(A[lpos] <= A[rpos])
                TmpArr[tmppos ++] = A[lpos ++];
            else
                TmpArr[tmppos ++] = A[rpos ++];
            //TmpArr[tmppos++] = A[lpos] <= A[rpos] ? A[lpos ++] : A[rpos ++];
        }
        while(lpos <= leftend)
            TmpArr[tmppos ++] = A[lpos ++];
        while(rpos <= rightend)
            TmpArr[tmppos ++] = A[rpos ++];
        for(int i = begin; i <= rightend; i ++)
            A[i] = TmpArr[i];
    }

    其中动态分配了一个与原数组等长的数组存放那些临时子数组合并之后的数组。这样实现比在每一次递归中都去申请一个数组来存放临时数据要更好。
    动图演示:
    此处输入图片的描述

    快速排序

    Quick sort)最近很烦,写到这真的无心去写了。有空再优化。现在没有优化甚至都比不过希尔排序、堆排序和归并排序。当然差std::sort肯定是差远了。

    给一个算法导论上的实现:

    //划分
    int Partition(int A[], int p, int r)
    {
        int x = A[r];
        int i = p - 1;
        for (int j = p; j<r; j++)
        {
            if (A[j] <= x)
            {
                i++;
                if (i != j)
                    swap(A[i], A[j]);
            }
        }
        swap(A[i + 1], A[r]);
        return i + 1;
    }
    
    //随机化的划分函数,使主元随机化 
    int Randomized_Partition(int A[], int p, int r)
    {
        int i = rand() % (r - p + 1) + p;   //产生p到r的随机数
        swap(A[i], A[r]);
        return Partition(A, p, r);
    }
    
    void Quick_Sort(int A[], int p, int r)
    {
        if (p < r)
        {
            int q = Randomized_Partition(A, p, r);
            Quick_Sort(A, p, q - 1);
            Quick_Sort(A, q + 1, r);
        }
    }
    void quick_sort2(int A[], int n)
    {
        Quick_Sort(A, 0, n - 1);
    }

    动图演示:
    此处输入图片的描述

    排序算法的时间下界

    可以使用决策树模型证明通过比较元素大小实现排序的排序算法的复杂度下界为O(NlogN)。所以快速排序、堆排序、归并排序都是渐进最优的。希尔排序由于增量序列的改变时间界会发生改变,但实际使用效果一般都很理想。并不差前面的三个排序算法多少,某些情况下甚至可能更优一点。

    C++ STL sort()函数

    一般我们自己实现的排序算法在优化不够的情况下都达不到C++的algorithm库中的sort()函数的效率。
    std::sort的实现采用了快速排序、插入排序、堆排序。并且进行了编译优化。一般是比不过的。

    调用方式,可以传入两个参数,或者三个参数。第一个参数为指向初始元素的指针,第二个参数为指向最后一个待排序元素的下一个位置的指针(或者迭代器),第三个元素可选,默认进行升序排序,可以定义一个返回值为bool类型的比较函数。当对结构或者对象进行排序时,重载运算符或者传入一个函数参数都可以实现排序。

    std::sort(A,A+n);    //对数组A中的n个元素排序
    std::sort(A.begin(),A.end(),cmp);   //对容器A中所有元素按照比较函数cmp()的规则进行排序

    简单的时间测试

    我对上述实现以及以前O(N2)的排序算法进行了一个测试。结果如下:

    test 1: 1e5 elements,静态分配
    simple aort algoritms :
    bubble sort time : 15735ms
    selection sort time : 10665ms
    insertion sort time : 1095ms
    binary insertion sort time : 872ms
    
    efficient sort algorithms :
    shell sort time : 13ms
    merge sort time : 15ms
    heap sort time : 8ms
    quick sort time : 9ms
    stl sort function time : 8ms
    
    test 2: 1e7 elements, 动态分配
    efficient sort algorithms :
    shell sort time : 1985ms
    merge sort time : 1858ms
    heap sort time : 1816ms
    quick sort time : 2010ms
    stl sort function time : 697ms

    ps: 测试时请将编译器设置为release模式。不然不开优化std::sort会非常慢。可以看到开启优化之后std::sort是吊打一切的存在。愉快地使用STL吧!

    源码下载。

    参考资料:数据结构与算法分析——C语言描述、算法导论

    展开全文
  • Timsort——自适应、稳定、高效排序算法

    万次阅读 多人点赞 2018-10-08 22:10:12
    Timsort是一种混合、稳定高效排序算法,源自合并排序和插入排序,旨在很好地处理多种真实数据。它由Tim Peters于2002年实施使用在Python编程语言中。该算法查找已经排序的数据的子序列,并使用该知识更有效...

    当在使用python中自带的排序算法、或者Java中的排序算法时,产生了一些好奇,他们本身运用的是什么高端的排序算法,深究、探索、查阅资料后得到了如下的认识。

    Timsort介绍

    Timsort是一种混合、稳定高效的排序算法,源自合并排序和插入排序,旨在很好地处理多种真实数据。它由Tim Peters于2002年实施使用在Python编程语言中。该算法查找已经排序的数据的子序列,并使用该知识更有效地对其余部分进行排序。这是通过将已识别的子序列(称为运行)与现有运行合并直到满足某些条件来完成的。从版本2.3开始,Timsort一直是Python的标准排序算法。如今,Timsort 已是是 Python、 Java、 Android平台 和 GNU Octave 的默认排序算法。

    思想

    针对现实中需要排序的数据分析看,大多数据通常是有部分已经排好序的数据块,Timsort 就利用了这一特点。Timsort 称这些已经排好序的数据块为 “run”,我们可以将其视为一个一个的“分区”。在排序时,Timsort迭代数据元素,将其放到不同的 run 里,同时针对这些 run ,按规则进行合并至只剩一个,则这个仅剩的 run 即为排好序的结果。
    换句话说,就是分析待排序数据,根据其本身的特点,将排序好的(不管是顺序还是逆序)子序列的分为一个个run分区,当然,这个分区run也存在一定的约束,即根据序列会产生一个minrun,如果原始的run小于minrun的长度,用插入排序扩充run,直到达到条件,之后使用归并排序来合并多个run。
    timsort1
    timsort2

    算法步骤

    • 根据数列大小产生minrun(为什么需要一个minrun?合并时会说到)
      • minrun是划分run的一个条件值,run的大小小于这个minrun,就要进行扩充,将后面元素填充到run中,直到符合要求等于minrun。因此说明一下minrun 的选取方式,如果待排序序列长度为 n,则我们总共会生成 ⌈ n m i n r u n ⌉ \lceil\frac{n}{minrun}\rceil minrunn个初始 run 。
        • ⌈ n m i n r u n ⌉ \lceil\frac{n}{minrun}\rceil minrunn刚好是2的整数次幂,则归并过程将会非常“完美”,可以表述为一个满二叉树。
        • ⌈ n m i n r u n ⌉ \lceil\frac{n}{minrun}\rceil minrunn比2的某个整数次幂稍大一点点,则到算法的最后阶段会出现一个超长 run 与一个超短 run 的合并,这是一种非常不好的的情况。
          因此,我们会选取minrun,使得 ⌈ n m i n r u n ⌉ \lceil\frac{n}{minrun}\rceil minrunn刚好是2的整数次幂或比某个2的整数次幂稍小一点的数。
      • 当数组元素个数小于64时,minrun就是数组的长度,此时就采用二分查找插入排序来进行数组排序。
        charu
      • 当数组元素个数大于64时,如前所述, 我们知道当 run 的数目等于或略小于2的幂时,合并两个数组最为有效。所以 Timsort 选择范围为 [32,64]的 minrun,使得原始数组的长度除以 minrun 时 ⌈ n m i n r u n ⌉ \lceil\frac{n}{minrun}\rceil minrunn等于或略小于2的幂。
        具体而言,选择数组长度的六个最高标志位,如果其余的标志位被设置,则加1:
        • 189:10111101,取前六个最高标志位为101111(47),同时最后两位为01,所以 minrun 为47+1=48, ⌈ n m i n r u n ⌉ \lceil\frac{n}{minrun}\rceil minrunn = 4符合条件。
        • 976:11 1101 0000,取前六个最高标志位为111101(61),同时最后几位为0000,所以 minrun 为61, ⌈ n m i n r u n ⌉ \lceil\frac{n}{minrun}\rceil minrunn = 16符合条件。
    • 依次寻找待排序序列中的run,并判断run的大小是否小于minrun,如果小于,则向后进行扩充,采用插入排序的方式将后面的元素加入到当前的run中,直到等于minrun。如果run区间的元素为逆序时,就地线性时间调整为顺序。
    • 合并run
      上一步提出了一个问题,为什么需要minrun这个值来约束run的大小,因为这样做可以使得run的大小保持一个均衡,避免存在一个很短的run和一个很长的run进行合并,这样的合并操作性价比很低。此时,合并操作也需要一个规则来进行约束。
      X、Y、Z代表栈最上方的3个run的长度(下图),如果违反了下面的两条规则,则Y与X、Z中的较小者合并。规则使得合并保持近似平衡,同时在延迟合并以实现平衡,利用cache memory中新出现的runs以及使合并决策相对简单之间保持折衷。
      • X &gt; Y + Z X &gt; Y + Z X>Y+Z
      • Y &gt; Z Y &gt; Z Y>Z
        在到达数据末尾时,Timsort反复将两次运行合并到堆栈顶部,直到只剩下一次完整数据,同时满足上面两个规则结束。
        merge
        实际中 Timsort 合并2个相邻的 run 需要临时存储空闲,临时存储空间的大小是2个 run 中较小的 run 的大小。Timsort算法先将较小的 run 复制到这个临时存储空间,然后用原先存储这2个 run 的空间来存储合并后的 run。
        merge2
        合并算法是用简单插入排序,依次从左到右或从右到左比较,然后合并2个 run。为了提高效率,Timsort用二分插入排序(binary merge sort)。即先用二分查找(binary search)找到插入的位置,然后再插入。(python中的比较很贵,比较比移动昂贵,故能减少比较就减少比较

    Galloping mode

    在 Galloping mode 中,算法在一个 run 中搜索另一个 run 的第一个元素。通过将该初始元素与另一个 run 的第 2 k − 1 2k-1 2k1个元素(即1,3,5…)进行比较来完成的,以便获得初始元素所在的元素范围。这缩短了二分查找的范围,从而提高了效率。如果发现 Galloping 的效率低于二分查找,则退出 Galloping mode。
    例如,我们要将 X 和 Y 这2个 run 合并,且X是较小的 run,以及 X 和 Y 已经分别是排好序的,将X复制到cache memory中,如下图所示。
    Galloping mode1
    二分查找会找到 X 中第一个大于 Y[0] 的元素 x,当找到 x 时,可以在合并时忽略 x 之前的元素。类似的,还可以在 Y 中找到第一个大于 X[-1] (即X最大的元素)的元素 y,当找到 y 时,可以在合并时忽略 y 之后的元素,这种查找可能在随机数中效率不会很高,但是在其他情况下有很高的效率。
    Galloping mode2
    当算法到达最小阈值min_gallop时,算法切换到 Galloping mode,试图利用数据中的那些可以直接排序的元素。只有当一个 run 的初始元素不是另一个 run 的前七个元素之一时,Galloping 才有用。这意味着初始阈值为7。
    为了避免 Galloping mode 的缺点,合并函数会调整阈值。如果所选元素来自先前返回元素的同一数组,则min_gallop减1。否则,该值增加1,从而阻止返回到 Galloping mode 。 在随机数据的情况下,min_gallop的值会变得非常大,以至于 Galloping mode 永远不会再次发生。

    算法时间复杂度

    O(n)
    本质上 Timsort 是一个经过大量优化的归并排序,而归并排序已经到达了最坏情况下,比较排序算法时间复杂度的下界,所以在最坏的情况下,Timsort 时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)。在最佳情况下,即输入已经排好序,它则以线性时间运行 O ( n ) O(n) O(n)。可以看出Timsort是目前最好的排序方式。

    代码

    以下实现的代码并不是具体完整的timsort,而是简化的,符合Timsort思想的大概实现。具体、完整的代码可以参看python源代码中的排序,或者JDK1.8中的源码,也可参照Timsort官方原始C代码

    #!/usr/bin/env python
    # coding=utf-8
    
    """realize timsort"""
    
    __author__ = 'steven'
    
    
    def binary_search(arr, left, right, value):
        """
        二分查找
        :param arr: 列表
        :param left: 左索引
        :param right: 右索引
        :param value: 需要插入的值
        :return: 插入值所在的列表位置
        """
        if left >= right:
            if arr[left] <= value:
                return left + 1
            else:
                return left
        elif left < right:
            mid = (left + right) // 2
            if arr[mid] < value:
                return binary_search(arr, mid + 1, right, value)
            else:
                return binary_search(arr, left, mid - 1, value)
    
    
    def insertion_sort(arr):
        """
        针对run使用二分折半插入排序
        :param arr: 列表
        :return: 结果列表
        """
        length = len(arr)
        for index in range(1, length):
            value = arr[index]
            pos = binary_search(arr, 0, index - 1, value)
            arr = arr[:pos] + [value] + arr[pos:index] + arr[index + 1:]
        return arr
    
    
    def merge(l1, l2):
        """
        合并
        :param l1: 列表1
        :param l2: 列表2
        :return: 结果列表
        """
        if not l1:
            return l2
        if not l2:
            return l1
        if l1[0] < l2[0]:
            return [l1[0]] + merge(l1[1:], l2)
        else:
            return [l2[0]] + merge(l1, l2[1:])
    
    
    def timsort(arr):
        """
        timsort
        :param arr: 待排序数组
        :return:
        """
        if not arr:  # 空列表
            return
        runs, sorted_runs = [], []
        new_run = [arr[0]]
        length = len(arr)
        # 划分run区,并存储到runs里,这里简单的按照升序划分,没有考虑降序的run
        for index in range(1, length):
            if arr[index] < arr[index - 1]:
                runs.append(new_run)
                new_run = [arr[index]]
            else:
                new_run.append(arr[index])
            if length - 1 == index:
                runs.append(new_run)
                break
    
        # 由于仅仅是升序的run,没有涉及到run的扩充和降序的run
        # 因此,其实这里没有必要使用insertion_sort来进行run自身的排序
        for run in runs:
            insertion_sort(run)
    
        # 合并runs
        sorted_arr = []
        for run in runs:
            sorted_arr = merge(sorted_arr, run)
        print(sorted_arr)
    

    参考资料

    • Timsort - wiki
    • Timsort原理学习
    • Nicolas Auger, Cyril Nicaud, Carine Pivoteau. Merge Strategies: from Merge Sort to TimSort. 2015.
    展开全文
  • 目录序言介绍[^1]原理补充内容分治介绍[^3]递归介绍[^4]快速排序算法基本思想基准数字的选取利用i,j作为指针对数组进行检索和排序在C语言为例子实现快速排序算法总结 序言 笔者还只是大一新生,在做我们学校OJ平台...

    序言

    笔者还只是大一新生,在做我们学校OJ平台上的题的时候遭遇了排序算法太慢而导致TLE(Time Limit Exceed,即超时)错误,于是上网查询了很多资料了解了快速排序算法。在学习该算法之后,由于觉得该算法实在是太厉害,于是突发奇想在CSDN上写了一篇小文章。
    这是笔者第一次发表作品,内容肯定不够详尽,也肯定不够完美,请大佬们看了之后轻喷。

    介绍1

    快速排序法是对冒泡排序的一种改进算法,由C·A·R·Hoare2在1960年提出。该算法通过将数组分割为使得两边数字分别小于中间的数字和大于中间的数字,并将这种过程通过递归进行多次,使数组中的元素最终被调整为有序数列。

    原理

    下面将会介绍快速排序算法的原理。在进入正式的解释前,我们需要先了解快速排序法涉及到的两种计算机编程技巧

    补充内容

    分治法介绍3

    首先介绍分治法。分治法是计算机科学中的一种重要编程技巧。其基本思想在于将一个大问题拆分为小问题,当把小问题一个个地解决完成后,把小问题的结果结合起来大问题便被解决了。
    分治法是很多高效算法的基础,比如本文正在介绍的快速排序算法,以及另外一种排序算法归并排序法,快速傅里叶变换等等。

    递归介绍4

    其次再介绍递归。同分治法一样,递归也是计算机科学中的一种重要编程技巧。递归实际上就是在一个函数运行过程中调用了该函数本身。不过为了保证该函数运行会有终止的时候,在运用了递归的函数之中都会加入一些边界条件以保证函数运行到一定程度会终止。

    快速排序算法基本思想

    快速排序算法的基本思想:将待排序数组中的一个数字作为基准数字(Key)。此后,将比基准数字小的数字移动到基准数字的左边,比基准数字大的数字移动到基准数字的右边。这一步骤完成后,整个数组将会变为中间是基准数字,其左的数字都比基准数字小,其右的数字都比基准数字大。通过这种方法,该算法将数组分割为了更小和更大的部分,此后通过递归的方法,将左边和右边的部分再进行同样的操作,直到数列中的数字已经有序。这时一个大型的数列排序便被完成了排序

    基准数字的选取

    在快速排序算法中,我们往往将送入算法中的数组最右边的数字作为基准数字。但是为了避免遇到一个有过多重复数字堆砌在一起的数组,使得算法效率被迫降低到 O ( n 2 ) O\left(n^{2}\right) O(n2),因此在一些更优化的快速排序算法中会使用随机数作为索引值在数组中挑选一个数字作为基准值进行排序。不过在本文中,笔者为了使文章尽可能让大家理解,就直接选取最右边的数字作为基准数字了。

    利用i,j作为指针对数组进行检索和排序

    将最左边的索引值作为i,最右边的索引值(对应的是基准值)作为j。首先是i向右移动,分别查看其所指向的元素与基准值的关系,如果左边的数字小于基准值则i继续右移,否则将i所指向的元素与j所指向的元素(及基准值)交换。交换后,i所指向的元素变为了基准值,此时改为j向左移,与i移动时相似,当遇到j所指向的元素大于基准值则j继续左移,否则交换数字并改为i移动。当i和j相遇时结束
    如此方法继续下去,数组将会变为以基准值为中心,左部分比基准值低,右部分比基准值高。
    通过i,j移动对数组进行排序在C语言中可以如下代码那样进行:

    int dir = 1;//用于指示该那一个标记动
        while(i != j)
        {
            if(dir == 1)
            {
                if(a[j] < a[i])//当右边发现有小于基础数字的数字时两边交换
                {
                    int t = a[j];
                    a[j] = a[i];
                    a[i] = t;
                    dir = 0;//交换过后换为左方标记动
                }else {
                    j -= 1;
                }
            }else{
                if(a[i] > a[j])//当左边发现有大于基础数字的数字时两边交换
                {
                    int t = a[i];
                    a[i] = a[j];
                    a[j] = t;
                    dir = 1;//交换过后换为右方标记动
                }else{
                    i += 1;
                }
            }
        }
    

    此时,我们再将左部分的数组和右部分的数组也进行同样的操作,那么我们就要用到前面介绍的递归了。
    那么,我们再在代码中加入这样一项:

    quickSort(left,i-1);
    quickSort(i+1,right);//进行递归,反复运算知道排序结束
    

    由于以最右边的数字作为基准值,我们其后使用的利用i,j指针对数组检索的操作便可以直接将基准值“带着走”,可以不用单独定义一个基准值。

    在C语言为例子实现快速排序算法

    综合上面的内容,我们可以以C语言为例子,将快速排序算法实现:

    #include <stdio.h>
    
    int a[1005];
    //设定全局变量a
    int quickSort(int left, int right){
        int i,j;
        i = left;
        j = right;
        if(left > right){
            return 0;
        }//保证程序运行到范围内只有2个数后能够退出
        int dir = 1;//用于指示该那一个标记动
        while(i != j)
        {
            if(dir == 1)
            {
                if(a[j] < a[i])//当右边发现有小于基础数字的数字时两边交换
                {
                    int t = a[j];
                    a[j] = a[i];
                    a[i] = t;
                    dir = 0;//交换过后换为左方标记动
                }else {
                    j -= 1;
                }
            }else{
                if(a[i] > a[j])//当左边发现有大于基础数字的数字时两边交换
                {
                    int t = a[i];
                    a[i] = a[j];
                    a[j] = t;
                    dir = 1;//交换过后换为右方标记动
                }else{
                    i += 1;
                }
            }
        }
        quickSort(left,i-1);
        quickSort(i+1,right);//进行递归,反复运算知道排序结束
    }
    
    int main()
    {
        int n;
        scanf("%d",&n);
        for(int i=0;i<n;i++){
            scanf("%d",&a[i]);
        }
        quickSort(0,n-1);//进行测试
        for(int i=0;i<n;i++){
            printf("%d",a[i]);
            if(i != n-1)
            {
                printf(" ");
            }else{
                printf("\n");
            }
        }
        return 0;
    }
    

    在测试代码中,第一行输入待排序数字的数目n,第二行以空格作为间隔输入n个待排序的数字,随后程序会通过快速排序算法完成排序,并将结果输出。

    总结

    快速排序算法利用分治法和递归大幅度地提升了算法的效率,使排序时间大大减短。
    但是快速排序算法的效率不够稳定,其时间复杂度处在 O ( n log ⁡ 2 n ) O\left(n\log_{2}n\right) O(nlog2n) O ( n 2 ) O\left(n^{2}\right) O(n2)之间,也就是说该算法最好的情况速度很快但最坏的情况速度和冒泡算法没什么区别。
    这里我列了一个表,用了CSDN上的资料5,将部分常见的排序算法做了一个对比:

    排序方法平均时间复杂度最好的时间复杂度最坏的时间复杂度
    冒泡排序算法 O ( n 2 ) O\left(n^{2}\right) O(n2) O ( n ) O\left(n\right) O(n) O ( n 2 ) O\left(n^{2}\right) O(n2)
    快速排序算法 O ( n log ⁡ 2 n ) O\left(n\log_{2}n\right) O(nlog2n) O ( n log ⁡ 2 n ) O\left(n\log_{2}n\right) O(nlog2n) O ( n 2 ) O\left(n^{2}\right) O(n2)
    归并排序算法 O ( n log ⁡ 2 n ) O\left(n\log_{2}n\right) O(nlog2n) O ( n log ⁡ 2 n ) O\left(n\log_{2}n\right) O(nlog2n) O ( n log ⁡ 2 n ) O\left(n\log_{2}n\right) O(nlog2n)

    由于时间不足的原因,没有将剩下的部分写下,只在文中写了部分排序算法的时间复杂度情况,非常抱歉,如果想要了解剩下的部分请打开来源


    1. 快速排序算法的介绍部分来源于百度百科–快速排序算法↩︎

    2. C·A·Hoare:1934年1月11日出生,英国著名的计算机科学家,是1980年的图灵奖获得者。该部分来源于Wikiquoto,并由笔者翻译。 ↩︎

    3. 分治法的介绍来源于百度百科–分治法↩︎

    4. 递归的介绍来源于百度百科–递归↩︎

    5. 资料来源于排序算法之(9)–八种常用排序算法效率对比↩︎

    展开全文
  • 本文对比较常用且比较高效排序算法进行了总结和解析,并贴出了比较精简的实现代码,包括选择排序、插入排序、归并排序、希尔排序、快速排序等。算法性能比较如下图所示: 2选择排序 选择排序的第一趟处理是...
  • 快速排序时对冒泡排序的一种改进。 实现思想:通过一趟排序将待排序记录(数组)分割成独立的两部分,其中一部分的元素均比另一部分的元素要小,则可以对这两部分记录继续进行排序,从而达到整个序列有序。实现的...
  • 算法(Algorithm),是程序设计的灵魂,它是利用系统的方法描述...本系列文章旨在用C语言解释算法的作用,分析包括排序算法、查找算法、迭代算法、递推算法、 递归算法、枚举算法、贪心算法、回溯算法、矩阵算法等。
  • 后缀排序高效算法

    2021-03-14 13:26:26
    后缀排序高效算法
  • java实现四种常用排序算法

    万次阅读 多人点赞 2019-03-29 11:20:28
    四种常用排序算法 冒泡排序 特点:效率低,实现简单 思想(从小到大排):每一趟将待排序序列中最大元素移到最后,剩下的为新的待排序序列,重复上述步骤直到排完所有元素。这只是冒泡排序的一种,当然...
  • 2、归并排序的设计思想:是将一个数组的两个有序的部分合并成一个有序数组,其算法的本质也是依靠递归来实现的。 3、归并排序的缺陷:在于需要额外的存储空间来合并数组。在归并排序的过程中必须使用一个临时数组,...
  • 高效排序算法

    2010-08-28 18:51:00
    已知最大值的高效排序算法 今天看到一个排序算法,感觉挺有新意,可能是我见识短。所以要转到自己博客里。文章分类:Java编程有一组数据3,5,9,7,4,13,15,0,2,20.已知最大数是20,把数据从小到大排序,而且算法...
  • 十大经典排序算法-归并排序算法详解

    万次阅读 多人点赞 2020-06-19 15:23:51
    归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法,归并排序对序列的元素进行逐层折半分组,然后从最小分组开始比较排序,合并成一个大的分组,逐层进行,最终所有的元素都是有序的 2.算法原理 这是一...
  • **跪求求高效排序算法???**问题描述 给出n个数,找出这n个数的最大值,最小值,和。输入格式 第一行为整数n,表示数的个数。第二行有n个数,为给定的n个数,每个数的绝对值都小于10000。输出格式 输出三行,每行一个...
  • 程序员那些必须掌握的排序算法(上)

    万次阅读 多人点赞 2019-08-17 16:03:39
    算法也是一个争论了很久的话题,程序员到底该不该掌握算法?不同的人有不同的答案,而事实上,很多公司都对算法有一定的要求,有些公司直接在面试的时候便会要求面试者手写算法题。这就对程序员的技术要求产生了很大...
  • 点击上方蓝字关注我们快速排序算法是一种非常高效排序算法,它采用“分而治之”的思想,将大的拆分为小的,小的拆分为更小的。如果说,希尔排序是直接插入排序的升级(插入类),堆排序是简单选择排...
  • 通过对算法的分析和问题的分析来引导如何去编程,一步步论证,检测,再论证去用程序来实现心中的想法。 2.1.3 mergeSort 先分后...与快速排序相同的是合并排序也基于分治思想而想出来的一种排序算法;而与快速排序...
  • Shell排序又称为渐进增量排序法。 Shell排序算法思想是:先将这个待排记录序列分割成为若干子序列(子数组)分别进行直接插入排序,待整个序列中的记录“基本有序”时,再对全体记录进行一次直接插入排序。 说明:对...
  • 为什么说快速排序是性能最好的排序算法

    万次阅读 多人点赞 2018-09-12 22:47:41
    心想从表上来看,堆排序不该是最好的排序算法么?不管最好、最坏还是平均情况,时间复杂度都是O(nlogn),而且还不像快排和归并排序那样占空间,为什么说快速排序是最好的算法呢? 其实经过实验,会发现相同的数据...
  • 高效链表排序-归并算法

    千次阅读 2016-05-03 11:45:41
    排序算法应该是最基础的了,快速、归并、选择、堆排序等等...那么对于链表而言,可以采取一种怎么样的高效排序算法呢归并排序分而治之,分别拍好前后两个部分,然后合并两个有序链表,在合适不过,并且由于链表自带属性
  • 当初学习插入的时候,一看到这么接地气的名字,学起来也有信心。但是看到希尔排序这高端大气上档次的名字,一下子就起了退避三舍的心思。那么,希尔排序真的就这么的拒人于千里之外吗?其实学会了希尔排序的思路后...
  • 如何实现高效排序算法?空间复杂度: 不是原地排序的算法,需要注意数据量是不是很大,如果100M的数据,突然多出100M的临时空间申请,这相当于需 要多出一倍的空间量,不太合适用非原地排序算法。 稳定性: 如果...
  • 阵列众核处理器上的高效归并排序算法.pdf
  • 主要介绍了Java排序算法总结之冒泡排序,较为详细的分析了冒泡排序的原理与java实现技巧,需要的朋友可以参考下
  • 也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本。 希尔排序的基本思想是:先将整个待排元素序列分割成若干个子序列(由相隔某个“增量”的元素组成的)分别进行直接插入排序,然后依次缩减增量再进行...
  • Java常用高效8大排序算法与二分法查找,适合正在学习算法和准备学习算法的算法爱好者和研究使用算法的开发人员使用。
  • 总结5种比较高效常用的排序算法

    万次阅读 2017-05-18 20:42:33
     本文对比较常用且比较高效排序算法进行了总结和解析,并贴出了比较精简的实现代码,包括选择排序、插入排序、归并排序、希尔排序、快速排序等。算法性能比较如下图所示:   2 选择排序  选择排序的第一...
  • 经典排序算法动图图解

    千次阅读 多人点赞 2019-08-05 10:41:28
    1、冒泡排序(Bubble Sort) 2、选择排序(Selection Sort) 3、插入排序(Insertion Sort) 4、希尔排序(Shell Sort) 5、归并排序(Merge Sort) 6、快速排序(Quick Sort) 7、堆排序(Heap Sort) 8、...
  • 针对带精英策略的非支配排序遗传算法不能根据环境变化自适应地动态调整运行参数,难以实现对解空间的高效搜索,提出一种自适应的非支配排序遗传算法.所提出算法根据运行阶段、运行代数和当前临时种群非支配个体数动态...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 145,577
精华内容 58,230
关键字:

高效排序算法

友情链接: bubble.rar