Technology Sort - chaolunner/CloudNotes GitHub Wiki

各种排序算法复杂度比较

时间复杂度如何计算，下面以快速排序的时间复杂度为例：

快速排序的一次划分算法从两头交替搜索，直到low和high重合，因此其时间复杂度是O(n)；而整个快速排序算法的时间复杂度与划分的趟数有关。
理想的情况是，每次划分所选择的中间数恰好将当前序列几乎等分，经过log2n趟划分，便可得到长度为1的子表。这样，整个算法的时间复杂度为O(nlog2n)。
最坏的情况是，每次所选的中间数是当前序列中的最大或最小元素，这使得每次划分所得的子表中一个为空表，另一子表的长度为原表的长度-1。这样，长度为n的数据表的快速排序需要经过n趟划分，使得整个排序算法的时间复杂度为O(n2)。

公式理解：

如果2^x=n，那么n=(以2为底n的对数)，即n=1,log2n=0;n=2,log2n=1;n=3,log2n=1;n=4,log2n=2;

log2n+1也可以用来表示一棵完全二叉树的高。

新的问题：

从图中我们不难看出，似乎堆排序的效率要比快速排序还要好，但是事实中却并非如此。

堆排序访问数据的方式没有快速排序友好。

对于快速排序来说，数据是顺序访问的。而对于堆排序来说，数据是跳着访问的。比如，堆排序中，最重要的一个操作就是数据的堆化。比如下面这个例子，对堆顶进行堆化，会依次访问数组下标是1，2，4，8的元素，而不像快速排序那样，局部顺序访问，所以，这样对CPU缓存是不友好的。
对于同样的数据，在排序过程中，堆排序算法的数据交换次数要多于快速排序。

我们在讲排序的时候，提过两个概念，有序度和逆序度。对于基于比较的排序算法来说，整个排序过程是由两个基本操作组成的，比较和交换。快速排序交换的次数不会比逆序度多。

但是堆排序的第一步是建堆，建堆的过程会打乱数据原有的相对选择顺序，导致数据有序度降低。比如对于一组已经有序的数据来说，经过建堆之后，数据反而变得更无序了。

冒泡排序（Bubble sort）

原理：

比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

算法实现：

using UnityEngine;
using System.Collections;

public class BubbleSort : MonoBehaviour {
    //定义一个数组
    private int[] array = new int[] { 5, 9, 3, 1, 4, 7, 2 };

    void Awake()
    {
        //调用排序方法
        BubbleSortArray(array);
        //打印数组
        foreach (int item in array)
        {
            Debug.Log(item);
        }
    }

    void BubbleSortArray(int[] array)
    {
        int temp = 0;
        for (int i = 0; i < array.Length - 1; i++)
        {
            for (int j = 0; j < array.Length - 1 - i; j++)
            {
                if (array[j] > array[j + 1])
                {
                    temp = array[j + 1];
                    array[j + 1] = array[j];
                    array[j] = temp;
                }
            }
        }
    }
}

插入排序（Insertion sort）

定义：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。

原理：

从第一个元素开始，该元素可以认为已经被排序。
取出下一个元素，在已经排序的元素序列中从后向前扫描。
如果该元素（已排序）大于新元素，将该元素移到下一位置。
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置。
将新元素插入到下一位置中。
重复步骤2~5。

算法实现：

using UnityEngine;
using System.Collections;

public class InsertionSort : MonoBehaviour {
    //定义一个数组
    private int[] array = new int[] { 5, 9, 3, 1, 4, 7, 2 };

    void Awake()
    {
        //调用排序方法
        InsertionSortArray(array);
        //打印数组
        foreach (int item in array)
        {
            Debug.Log(item);
        }
    }

    void InsertionSortArray(int[] array)
    {
        for (int i = 1; i < array.Length; ++i)
        {
            Insert(array, i);
        }
    }

    // 希尔排序需要额外设置gap，直接插值排序gap = 1。
    void Insert(int[] array, int i, int gap = 1)
    {
        int t = array[i];
        int j;
        for (j = i-gap; j >= 0 && t < array[j]; j -= gap)
        {
            // 相较于冒泡排序，插入排序减少了元素值“交换”的次数。
            // 插入排序利用变量t暂时存储array[i]的值，等到本轮次排序结束之后再把t的值赋给array[j+gap]。
            // 从而以“值变换”替代“值互换”减少开销。
            array[j+gap] = array[j];
        }
        array[j+gap] = t;
    }
}

希尔排序（Shell's Sort）是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort）

原理：对于n个待排序的数列，取一个小于n的整数gap(gap被称为步长)将待排序元素分成若干个组子序列，所有距离为gap的倍数的记录放在同一个组中；然后，对各组内的元素进行直接插入排序。这一趟排序完成之后，每一个组的元素都是有序的。然后减小gap的值，并重复执行上述的分组和排序。重复这样的操作，当gap=1时，整个数列就是有序的。

算法实现：

using UnityEngine;
using System.Collections;

public class ShellSort : MonoBehaviour {
    //定义一个数组
    private int[] array = new int[] { 5, 9, 3, 1, 4, 7, 2 };

    void Awake()
    {
        //调用排序方法
        ShellSortArray(array);
        //打印数组
        foreach (int item in array)
        {
            Debug.Log(item);
        }
    }

    void ShellSortArray(int[] array)
    {
        int length = array.Length;
        for (int gap = length / 2; gap > 0; gap /= 2)
        {
            if (gap % 2 == 0) { gap++; }

            // 按gap分组，最开始时的增量为数组长度的一半。
            for (int i = gap; i < length; i++)
            {
                Insert(array, i, gap);
            }
        }
    }

    // 希尔排序需要额外设置gap，直接插值排序gap = 1。
    void Insert(int[] array, int i, int gap = 1)
    {
        int t = array[i];
        int j;
        for (j = i-gap; j >= 0 && t < array[j]; j -= gap)
        {
            // 相较于冒泡排序，插入排序减少了元素值“交换”的次数。
            // 插入排序利用变量t暂时存储array[i]的值，等到本轮次排序结束之后再把t的值赋给array[j+gap]。
            // 从而以“值变换”替代“值互换”减少开销。
            array[j+gap] = array[j];
        }
        array[j+gap] = t;
    }
}

快速排序（Quick sort）

原理：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

算法实现：

using UnityEngine;
using System.Collections;

public class QuickSort : MonoBehaviour {
    //定义一个数组
    private int[] array = new int[] { 5, 9, 3, 1, 4, 7, 2 };

    void Awake()
    {
        //调用排序方法
        QuickSortArray(array, 0, array.Length - 1);
        //打印数组
        foreach (int item in array)
        {
            Debug.Log(item);
        }
    }
    /// <summary>
    /// 快速排序的方法
    /// </summary>
    /// <param name="array">数组</param>
    /// <param name="start">数组起始位置</param>
    /// <param name="end">数组终止位置</param>
    void QuickSortArray(int[] array, int start, int end)
    {
        //若数组中数小于等于0直接返回
        if (start >= end) return;
        //定义一个基准值
        int pivot = array[start];
        //定义2个索引指向数组的而开头和结束
        int left = start;
        int right = end;
        //按照从小到大的排序，直到2数相遇结束排序
        while (left < right)
        {
            //第一轮比较
            //把所有left右边的数都和基准值比较,获得最左边数在排序后位于数组中的位置（索引）
            while (left < right  && array[right] >= pivot)
            {
                right--;
            }
            //将该数放到数组中的该位置
            array[left] = array[right];
            //第二轮比较
            //把所有left右边的数都和基准值比较,获得最左边数在排序后位于数组中的位置（索引）
            while (left < right && array[left] <= pivot)
            {
                left++;
            }
            //将该数放到数组中的该位置
            array[right] = array[left];
        }
        //将2轮比较之后的数组的起始值再赋为基准值（已经得到最大值，并在最后一位）
        array[left] = pivot;
        //递归该方法（每次剔除一个排好的数）
        QuickSortArray(array, start, left - 1);
        QuickSortArray(array, left + 1, end);
    }
}

STL sort 函数优化快速排序

原理：STL中的sort并非只是普通的快速排序，除了对普通的快速排序进行优化，它还结合了插入排序和堆排序。根据不同的数量级别以及不同情况，能自动选用合适的排序方法。当数据量较大时采用快速排序，分段递归。一旦分段后的数据量小于某个阀值，为避免递归调用带来过大的额外负荷，便会改用插入排序。而如果递归层次过深，有出现最坏情况的倾向，还会改用堆排序。

STL源码：

#include <iostream>

const int __stl_threshold = 16;

template <class RandomAccessIterator, class T>
RandomAccessIterator __unguarded_partition(RandomAccessIterator first, RandomAccessIterator last, T pivot) {
    while (true)
    {
        while (*first < pivot) ++first;
        --last;
        while (pivot < *last) --last;
        if (!(first < last)) return first;
        iter_swap(first, last);
        ++first;
    }
}


template <class RandomAccessIterator, class T, class Compare>
void __partial_sort(RandomAccessIterator first, RandomAccessIterator middle,
    RandomAccessIterator last, T*, Compare comp) {
    make_heap(first, middle, comp);
    for (RandomAccessIterator i = middle; i < last; ++i)
        if (comp(*i, *first))
            __pop_heap(first, middle, i, T(*i), comp, distance_type(first));
    sort_heap(first, middle, comp);
}

//partial_sort，堆排序
template <class RandomAccessIterator, class Compare>
inline void partial_sort(RandomAccessIterator first,
    RandomAccessIterator middle,
    RandomAccessIterator last, Compare comp) {
    __partial_sort(first, middle, last, value_type(first), comp);
}

//Introspective Sorting(内省式排序)
/*
该函数只有两种情况下可能返回,
一是区域小于等于阈值16；二是超过递归深度阈值。
我们现在只考虑最左边的子序列，先假设是由于第一种情况终止了这个函数，那么该子区域小于16。
再根据前面的结论：左边区间的所有数据一定比右边小，可以推断出最小值一定在该小于16的子区域内。
假设函数是第二种情况下终止，那么对于最左边的区间，由于递归深度过深，因此该区间会调用堆排序，所以这段区间的最小值一定位于最左端。
再加上前面的结论：左边区间所有的数据一定比右边小，那么该区间内最左边的数据一定是整个序列的最小值。
因此，不论是哪种情况，都可以保证起始的16个元素中一定有最小值。
如此便能够使用__insertion_sort对前16个元素进行排序，接着用__unguarded_insertion_sort毫无顾忌的在不考虑边界的情况下对剩于的区间进行更快速的排序。
*/
template <class RandomAccessIterator, class T, class Size>
void __introsort_loop(RandomAccessIterator first, RandomAccessIterator last, T*,Size depth_limit)
{
    //const int __stl_threshold = 16; 最小分段阈值
    //当数据长度小于该阈值时，再使用递归来排序显然不划算，递归的开销相对来说太大。
    //而此时整个区间内部有多个元素个数少于16的子序列，
    //每个子序列都有相当程度的排序，但又尚未完全排序，过多的递归调用是不可取的。
    //而这种情况刚好插入排序最拿手，它的效率能够达到O(N)。
    //因此这里中止快速排序，sort会接着调用外部的__final_insertion_sort x行
    while (last - first > __stl_threshold) {
        //depth_limit是前面所提到的判断分割行为是否有恶化倾向的阈值
        if (depth_limit == 0) {
            //函数调用partial_sort，它便是堆排序
            partial_sort(first, last, last);
            return;
        }
        --depth_limit;
        //__unguarded_partition，这其实就是我们平常所使用的快速排序主体部分，用于根据pivot将区间分割为两个子序列。
        //__median函数，它的作用是取首部、尾部和中部三个元素的中值作为pivot。
        //我们之前学到的快速排序都是选择首部、尾部或者中间位置的元素作为pivot，并不会比较它们的值，在很多情况下这将引起递归的恶化。现在这里采用的中值法可以在绝大部分情形下优于原来的选择。
        RandomAccessIterator cut = __unguarded_partition(first, last, T(__median(*first, *(first + (last - first) / 2), *(last - 1))));
        //递归结构
        /*
        可以看出它是一个递归函数，因为我们说过，Introspective Sort在数据量很大的时候采用的是正常的快速排序，
        因此除了处理恶化情况以外，它的结构应该和快速排序一致。
        但仔细看代码，先不管循环条件和if语句(它们便是处理恶化情况所用)，循环的后半部分是用来递归调用快速排序。
        */
        //__introsort_loop中只有对右边子序列进行递归调用是不是？
        //左边的递归不见了。的确，这里的写法可读性相对来说比较差，但是仔细一分析发现是有它的道理的，它并不是没有管左子序列。
        //注意看，在分割原始区域之后，对右子序列进行了递归，接下来的last = cut将终点位置调整到了分割点，那么此时的[first, last)区间就是左子序列了。
        //又因为这是一个循环结构，那么在下一次的循环中，左子序列便得到了处理。只是并未以递归来调用!
        //两者区别就在于STL节省了接近一半的函数调用，由于每次的函数调用有一定的开销，因此对于数据量非常庞大时，这一半的函数调用可能能够省下相当可观的时间。
        __introsort_loop(cut, last, value_type(first), depth_limit);
        last = cut;
    }
}

//__unguarded_linear_insert不对边界作检查。正因为如此，它一定比下面的__insertion_sort要快。
template <class RandomAccessIterator, class T>
void __unguarded_linear_insert(RandomAccessIterator last, T value)
{
    RandomAccessIterator next = last;
    --next;
    while (value < *next) {
        *last = *next;
        last = next;
        --next;
    }
    *last = value;
}

template <class RandomAccessIterator, class T>
inline void __linear_insert(RandomAccessIterator first, RandomAccessIterator last, T*)
{
    T value = *last;
    if (value < *first) {
        copy_backward(first, last, last + 1);
        *first = value;
    }
    else
        __unguarded_linear_insert(last, value);
}

template <class RandomAccessIterator>
void __insertion_sort(RandomAccessIterator first, RandomAccessIterator last)
{
    if (first == last) return;
    for (RandomAccessIterator i = first + 1; i != last; ++i)
        __linear_insert(first, i, value_type(first));
}


//可以忽略掉这层aux函数的包装，它只是为了获得迭代器所指向的类型，其实这两个函数可以合并为一个。
template <class RandomAccessIterator, class T>
void __unguarded_insertion_sort_aux(RandomAccessIterator first, RandomAccessIterator last, T*)
{
    for (RandomAccessIterator i = first; i != last; ++i)
        __unguarded_linear_insert(i, T(*i));
}


template <class RandomAccessIterator>
inline void __unguarded_insertion_sort(RandomAccessIterator first, RandomAccessIterator last)
{
    __unguarded_insertion_sort_aux(first, last, value_type(first));
}


template <class RandomAccessIterator>
void __final_insertion_sort(RandomAccessIterator first, RandomAccessIterator last)
{
    //const int __stl_threshold = 16; 最小分段阈值
    //一个带边界检查而另一个不带，不带边界检查的__unguarded_insertion_sort更快。
    if (last - first > __stl_threshold) {
        __insertion_sort(first, first + __stl_threshold);
        __unguarded_insertion_sort(first + __stl_threshold, last);
    }
    else
        //__insertion_sort和__unguarded_insertion_sort有何区别？
        //有无边界检测
        __insertion_sort(first, last);
}



template <class RandomAccessIterator>
inline void sort(RandomAccessIterator first, RandomAccessIterator last) {
    if (first != last) {
        __introsort_loop(first, last, value_type(first), __lg(last - first) * 2);
        //std::sort的最后一步——插入排序。
        __final_insertion_sort(first, last);
    }
}

选择排序（Selection sort）

原理：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。

算法实现：

using UnityEngine;
using System.Collections;

public class SelectionSort : MonoBehaviour {
    //定义一个数组
    private int[] array = new int[] { 5, 9, 3, 1, 4, 7, 2 };

    void Awake()
    {
        //调用排序方法
        SelectionSortArray(array);
        //打印数组
        foreach (int item in array)
        {
            Debug.Log(item);
        }
    }

    void SelectionSortArray(int[] array)
    {
        int temp;
        int pos = 0;
        for (int i = 0; i < array.Length - 1; i++)
        {
            pos = i;
            for (int j = i + 1; j < array.Length; j++)
            {
                if(array[j] < array[pos])
                {
                    pos = j;
                }
            } // 第i个数与最小的数array[pos]交换
            temp = array[i];
            array[i] = array[pos];
            array[pos] = temp;
        }
    }
}

堆排序（Heapsort）

定义：是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

原理：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。

堆中定义以下几种操作：

最大堆调整（Max Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点。
创建最大堆（Build Max Heap）：将堆中的所有数据重新排序。
堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算。

算法实现：

using UnityEngine;
using System.Collections;

public class HeapSort : MonoBehaviour {
    //定义一个数组
    private int[] array = new int[] { 5, 9, 3, 1, 4, 7, 2 };

    void Awake()
    {
        //调用排序方法
        HeapSortArray(array);
        //打印数组
        foreach (int item in array)
        {
            Debug.Log(item);
        }
    }

    void HeapSortArray(int[] array)
    {
        // 创建大顶堆
        BuildMaxHeap(array);
        for (int i = array.Length - 1; i > 0; i--)
        {
            // 将其与末尾元素进行交换，此时末尾就为最大值
            Swap(ref array[0], ref array[i]);
            // 将剩余i-1个元素重新构造成一个大顶堆
            MaxHeapify(array, 0, i);
        }
    }

    void Swap(ref int a, ref int b)
    {
        int temp = a;
        a = b;
        b = temp;
    }

    void MaxHeapify(int[] array, int currentIndex, int heapSize)
    {
        int left = 2 * currentIndex + 1;    // 左子节点在数组中的位置
        int right = 2 * currentIndex + 2;   // 右子节点在数组中的位置
        int large = currentIndex;           // 记录此根节点、左子节点、右子节点 三者中最大值的位置

        // 与左子节点进行比较
        if (left < heapSize && array[left] > array[large])
        {
            large = left;
        }
        // 与右子节点进行比较
        if (right < heapSize && array[right] > array[large])
        {
            large = right;
        }
        // 如果 currentIndex != large 则表明 large 发生变化（即：左右子节点中有大于根节点的情况）
        if (currentIndex != large)
        {
            // 将左右节点中的大者与根节点进行交换（即：实现局部大顶堆）
            Swap(ref array[currentIndex], ref array[large]);
            // 以上次调整动作的large位置（为此次调整的根节点位置），进行递归调整
            MaxHeapify(array, large, heapSize);
        }
    }

    void BuildMaxHeap(int[] array)
    {
        // 根据大顶堆的性质可知：数组的前半段的元素为根节点，其余元素都为叶节点
        // 从最底层的最后一个根节点开始进行大顶堆的调整
        for (int i = array.Length / 2 - 1; i >= 0; i--)
        {
            MaxHeapify(array, i, array.Length);
        }
    }
}

归并排序（Merge sort）

定义：是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列，即先使每个子序列有序，再使子序列段间有序。

合并两个有序序列的方法：

申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列。
设定两个指针，最初位置分别为两个已经排序序列的起始位置。
比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置。
重复步骤3直到某一指针超出序列尾。
将另一序列剩下的所有元素直接复制到合并序列尾。

算法实现：

using UnityEngine;
using System.Collections;

public class MergeSort : MonoBehaviour {
    //定义一个数组
    private int[] array = new int[] { 5, 9, 3, 1, 4, 7, 2 };

    void Awake()
    {
        //调用排序方法
        MergeSortArray(array);
        //打印数组
        foreach (int item in array)
        {
            Debug.Log(item);
        }
    }

    void MergeSortArray(int[] array)
    {
        Sort(array, 0, array.Length - 1);
    }

    void Sort(int[] array, int left, int right)
    {
        if (left < right)
        {
            int middle = (left + right) / 2;
            Sort(array, left, middle);
            Sort(array, middle + 1, right);
            Merge(array, left, middle, right);
        }
    }

    void Merge(int[] array, int left, int middle, int right)
    {
        int[] temp = new int[right - left + 1];
        int i = 0;
        int p1 = left;
        int p2 = middle + 1;
        // 比较左右两部分的元素，哪个小，把那个元素填入temp中
        while(p1 <= middle && p2 <= right) {
            temp[i++] = array[p1] < array[p2] ? array[p1++] : array[p2++];
        }
        // 上面的循环退出后，把剩余的元素依次填入到temp中
        // 以下两个while只有一个会执行
        while(p1 <= middle) {
            temp[i++] = array[p1++];
        }
        while(p2 <= right) {
            temp[i++] = array[p2++];
        }
        // 把最终的排序的结果复制给原数组
        for(i = 0; i < temp.Length; i++) {
            array[left + i] = temp[i];
        }
    }
}

基数排序（Radix sort）

定义：属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用。

原理：基数排序的发明可以追溯到1887年赫尔曼·何乐礼在打孔卡片制表机(Tabulation Machine)上的贡献。它是这样实现的：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。

算法实现：

using UnityEngine;
using System.Collections;
using System.Collections.Generic;

public class RadixSort : MonoBehaviour {
    //定义一个数组
    private int[] array = new int[] { 5, 9, 3, 1, 4, 7, 2 };

    void Awake()
    {
        //调用排序方法
        RadixSortArray(array);
        //打印数组
        foreach (int item in array)
        {
            Debug.Log(item);
        }
    }

    void RadixSortArray(int[] array)
    {
        int maxUnit = GetMaxUnit(array);
        int i, j, k;
        int radix = 1;
        int[] tmp = new int[array.Length];
        int[] count = new int[10]; // 计数器
        for (i = 1; i <= maxUnit; i++)
        {
            for (j = 0; j < 10; j++)
            {
                count[j] = 0; // 每次分配前清空计数器
            }
            for (j = 0; j < array.Length; j++)
            {
                k = (array[j] / radix) % 10; // 统计每个桶中的记录数
                count[k]++;
            }
            for (j = 1; j < 10; j++)
            {
                count[j] = count[j - 1] + count[j]; // 将tmp中的位置依次分配给每个桶
            }
            for (j = array.Length - 1; j >= 0; j--) // 将所有桶中记录依次收集到tmp中
            {
                k = (array[j] / radix) % 10;
                tmp[count[k] - 1] = array[j];
                count[k]--;
            }
            for (j = 0; j < array.Length; j++) // 将临时数组的内容复制到array中
            {
                array[j] = tmp[j];
            }
            radix = radix * 10;
        }
    }

    // 得到元素最大的位数
    int GetMaxUnit(int[] array)
    {
        int unit = 1;
        int radix = 10;
        for (int i = 0; i < array.Length; ++i)
        {
            while (array[i] >= radix)
            {
                radix *= 10;
                ++unit;
            }
        }
        return unit;
    }
}

Technology Sort - chaolunner/CloudNotes GitHub Wiki

各种排序算法复杂度比较

冒泡排序（Bubble sort）

插入排序（Insertion sort）

希尔排序（Shell's Sort）是 插入排序 的一种又称“缩小增量排序”（Diminishing Increment Sort）

快速排序（Quick sort）

STL sort 函数 优化快速排序

选择排序（Selection sort）

堆排序（Heapsort）

归并排序（Merge sort）

基数排序（Radix sort）

⚠️ **GitHub.com Fallback** ⚠️

希尔排序（Shell's Sort）是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort）

STL sort 函数优化快速排序

⚠️ GitHub.com Fallback ⚠️