分类
数据结构和算法

几种排序算法的实现和性能比较

浏览量： 753
(在苹果系统下，如果文章中的图片不能正常显示，请升级Safari浏览器到最新版本，或者使用Chrome、Firefox浏览器打开。)

在各种各样的排序任务中，不同的算法有着不同的效果和性能，比如稳定性、时间开销、空间开销等。本文中实现了5种排序算法：
插入排序（Insertion Sort，IS）、
自顶向下归并排序（Top-down Mergesort，TDM）、
自底向上归并排序（Bottom-up Mergesort，BUM）、
随机快速排序（Random Quicksort，RQ）和
Dijktra 3路划分快速排序（Quicksortwith Dijkstra 3-way Partition，QD3P），
并且在同一台普通计算机上，针对不同输入规模的数据进行了测试，对比了上述排序算法的时间性能。

1.插入排序

插入排序就是将元素从其开始位置一个一个地跟其他元素比较，当位置不合适时，将其移动，插到其他元素前面。如果每次不合适时都交换一次位置，那么会有大量的无用功开销，一种改进方法是找到合适的位置之后再将其交换。插入排序是从理论上分析就属于平均比较慢的排序算法，时间复杂度为O(N2)，只有当整个数组基本有序而个别元素位置不当的时候，才能有接近线性的时间复杂度。其他的排序算法都应当比插入排序快得多。

2.自顶向下归并排序

该算法是首先将数组划分，一分为二，然后再递归地对子数组调用排序方法，直到子数组可以直接被判断大小顺序。该算法时间复杂度为O(N logN)。

3.自底向上归并排序

该算法与上一个相反首先将数组元素每两个两个进行排序，然后通过归并使得元素每四个四个有序，然后再八个八个有序，直到最后，整体有序。该算法时间复杂度同样为O(N logN)。

4.随机切分快速排序

从数组中随机选择一个元素作为标杆，放到第一个，然后分治，从左右两边分别有两个指针指向元素，逐渐向中间靠拢，当左指针元素值大于等于标杆元素，而且右指针元素小于等于标杆元素时，将它们的位置交换，当两个指针位置发生交叉时算法结束。该算法时间复杂度为O(N logN)。

5.三向切分快速排序

与随机切分快排差不多，三向切分快排更适合数组中有大量重复元素时的情形，并且排序时，标杆元素可能会被改变。当左元素大于标杆时交换，当右元素小于标杆时交换，直到最后有序。该算法时间复杂度为O(N logN)。

 

分别将五种排序算法封装到五个类中，留出传入排序数组和执行排序的成员方法，为了方便测试，这里还特别使用了数组的复制，只在类的内部进行排序，并不将排序结果直接放到外部数组中，保证不会把测试用的原始数组排好序使得后续大量重复测试无法进行。

测试结果

(基于100000个随机整数的排序)

Comparison of running time of sorting algorithms (in Milliseconds)

IS TDM BUM RQ QD3P
Run1 2543.7817 14.0088 13.0092 9.006 12.0089
Run2 2572.8183 13.011 13.0085 9.0053 11.0085
Run3 2488.76 14.0103 12.0081 8.0057 11.0074
Run4 2545.8011 13.0272 11.992 9.0049 11.0082
Run5 2540.7968 14.0102 13.01 9.0052 11.0082
Run6 2485.7593 13.0243 13.0092 9.0063 10.991
Run7 2495.7667 13.0084 13.0081 9.024 10.0235
Run8 2495.747 13.0092 12.0088 9.006 12.0085
Run9 2483.7583 13.007 13.0092 8.0053 11.0074
Run10 2483.7569 14.0102 13.01 9.0052 11.0254
Average 2513.67461 13.41266 12.70731 8.80739 11.1097

从中可以看出，插入排序耗时最大，随机切分快速排序速度最快，因为用的数据是随机生成的数据，所以此时QD3P算法的速度比随机切分慢一些，但是相比前两个归并排序，速度还是要快一些的。通常情况下，还是随机切分快速排序要快一些，不过，在元素基本有序或者常数列时，插入排序效果反而会更好，时间复杂度变成O(N)。

 

C#代码：

插入排序

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace 几种排序算法的实验性能比较
{
    /// <summary>
    /// 插入排序类
    /// </summary>
    public class Class_InsertionSort
    {
        private int[] arr;
        public Class_InsertionSort(int[] a)
        {
            arr = new int[a.Length];
            a.CopyTo(arr, 0);
        }

        public int[] Sort()
        {
            int N = arr.Length;
            for(int i = 1; i < N; i++)
            {
                for (int j = i; j > 0 && arr[j] < arr[j - 1]; j--)
                {
                    int tmp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = tmp;
                }
            }

            return arr;
        }

        public int[] Sort2()
        {
            int N = arr.Length;
            for (int i = 1; i < N; i++)
            {
                if (arr[i - 1] > arr[i])
                {
                    int tmp = arr[i];
                    int j = i;
                    for (; j > 0 && arr[j - 1] > tmp; j--)
                    {
                        arr[j] = arr[j - 1];
                    }
                    arr[j] = tmp;
                }
                
            }

            return arr;
        }
    }
}

 

自顶向下的归并排序

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace 几种排序算法的实验性能比较
{
    /// <summary>
    /// 自顶向下的归并排序
    /// </summary>
    public class Class_Top_down_Mergesort
    {
        private int[] arr;
        /// <summary>
        /// 归并所需的辅助数组
        /// </summary>
        private int[] aux;

        public Class_Top_down_Mergesort(int[] a)
        {
            arr = new int[a.Length];
            a.CopyTo(arr, 0);
        }

        public int[] Sort()
        {
            aux = new int[arr.Length];
            Sort(arr, 0, arr.Length - 1);
            return arr;
        }

        private void Sort(int[] a,int lo,int hi)
        {
            if (hi <= lo) return;
            int mid = lo + (hi - lo) / 2;
            Sort(a, lo, mid);
            Sort(a, mid + 1, hi);
            merge(a, lo, mid, hi);
        }

        public void merge(int[] a,int lo,int mid,int hi)
        {
            int i = lo, j = mid + 1;

            for(int k = lo; k <= hi; k++)
            {
                aux[k] = a[k];
            }

            for(int k = lo; k <= hi; k++)
            {
                if (i > mid)
                    a[k] = aux[j++];
                else if (j > hi)
                    a[k] = aux[i++];
                else if (aux[j] < aux[i])
                    a[k] = aux[j++];
                else
                    a[k] = aux[i++];
            }
        }

    }
}

 

自底向上的归并排序

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace 几种排序算法的实验性能比较
{
    /// <summary>
    /// 自底向上的归并排序
    /// </summary>
    public class Class_Bottom_up_Mergesort
    {
        private int[] arr;

        /// <summary>
        /// 归并所需的辅助数组
        /// </summary>
        private int[] aux;

        public Class_Bottom_up_Mergesort(int[] a)
        {
            arr = new int[a.Length];
            a.CopyTo(arr, 0);
        }

        public int[] Sort()
        {
            Sort(arr);
            return arr;
        }

        private void Sort(int[] a)
        {
            int N = a.Length;
            aux = new int[N];
            for (int sz = 1; sz < N; sz = sz + sz)
                for (int lo = 0; lo < N - sz; lo += sz + sz)
                    merge(a, lo, lo + sz - 1, Math.Min(lo + sz + sz - 1, N - 1));
        }

        public void merge(int[] a, int lo, int mid, int hi)
        {
            int i = lo, j = mid + 1;

            for (int k = lo; k <= hi; k++)
            {
                aux[k] = a[k];
            }

            for (int k = lo; k <= hi; k++)
            {
                if (i > mid)
                    a[k] = aux[j++];
                else if (j > hi)
                    a[k] = aux[i++];
                else if (aux[j] < aux[i])
                    a[k] = aux[j++];
                else
                    a[k] = aux[i++];
            }
        }
    }
}

 

随机切分快速排序

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace 几种排序算法的实验性能比较
{
    /// <summary>
    /// 随机快速排序
    /// </summary>
    public class Class_Random_Quicksort
    {
        private int[] arr;

        public Class_Random_Quicksort(int[] a)
        {
            arr = new int[a.Length];
            a.CopyTo(arr, 0);
        }

        public int[] Sort()
        {
            Sort(arr);
            return arr;
        }

        private void Sort(int[] a)
        {
            Random r = new Random();
            int ra = r.Next() % a.Length;
            int tmp = a[0];
            a[0] = a[ra];
            a[ra] = tmp;
            Sort(a, 0, a.Length - 1);
        }

        private void Sort(int[] a, int lo, int hi)
        {
            if (hi <= lo)
                return;
            int j = partition(a, lo, hi);
            Sort(a, lo, j - 1);
            Sort(a, j + 1, hi);
        }

        private int partition(int[] a, int lo,int hi)
        {
            int i = lo, j = hi + 1;
            int v = a[lo];
            while (true)
            {
                while (a[++i] < v)
                {
                    if (i == hi)
                        break;
                }
                while (v < a[--j])
                {
                    if (j == lo)
                        break;
                }
                if (i >= j)
                    break;
                int tmp1 = a[i];
                a[i] = a[j];
                a[j] = tmp1;
            }
            int tmp = a[lo];
            a[lo] = a[j];
            a[j] = tmp;

            return j;
        }

    }
}

 

三向切分快速排序

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace 几种排序算法的实验性能比较
{
    /// <summary>
    /// Dijkstra 3-路划分快速排序
    /// </summary>
    public class Class_Quicksort_with_Dijkstra_3_way_Partition
    {
        private int[] arr;

        public Class_Quicksort_with_Dijkstra_3_way_Partition(int[] a)
        {
            arr = new int[a.Length];
            a.CopyTo(arr, 0);
        }

        public int[] Sort()
        {
            Sort(arr);
            return arr;
        }

        //未完成
        private void Sort(int[] a)
        {
            Random r = new Random();
            int ra = r.Next() % a.Length;
            exch(a, 0, ra);
            
            Sort(a, 0, a.Length - 1);
        }

        private void Sort(int[] a, int lo, int hi)
        {
            if (hi <= lo)
                return;
            int lt = lo, i = lo + 1, gt = hi;
            int v = a[lo];
            while (i <= gt)
            {
                int cmp = a[i].CompareTo(v);
                if (cmp < 0)
                {
                    exch(a, lt++, i++);
                }
                else if (cmp > 0)
                {
                    exch(a, i, gt--);
                }
                else
                    i++;
            }
            Sort(a, lo, lt - 1);
            Sort(a, gt + 1, hi);
            
        }

        private void exch(int[] a,int i,int j)
        {
            int tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
        }

    }
}

 

版权声明
本博客的文章除特别说明外均为原创，本人版权所有。欢迎转载，转载请注明作者及来源链接，谢谢。
本文地址: https://blog.ailemon.net/2018/05/21/some-algorithms-implement-and-compare/
All articles are under Attribution-NonCommercial-ShareAlike 4.0
发表你的看法 “点击发表你的看法”

关注“AI柠檬博客”微信公众号，及时获取你最需要的干货。


打赏微海报分享

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

5 × 3 =

如果您是第一次在本站发布评论，内容将在博主审核后显示，请耐心等待