• 欢迎光临~

排序算法 Sort

开发技术 开发技术 2022-10-28 次浏览

Sort

评价排序算法的标准

  • 时间复杂度
  • 空间复杂度
  • 稳定性:如果一个排序算法能够保留数组中的重复元素的相对位置,则可以被称为是稳定的

冒泡排序

通过两两交换,每次循环都使最值上浮到开头或末尾

关键点在于每次循环结束后都将最值排在开头或末尾

public static void BubbleSort<T>(IList<T> list) where T : IComparable<T>
{
    T temp;
    for (int i = 1; i != list.Count; ++i) // 以从小到大的顺序作示范
    {
        bool sorted = true; // 如果在一趟遍历中没有需要移动的元素,那么说明已经排序好了
        for (int j = 1; j != list.Count - i + 1; ++j)
        {
            if (list[j].CompareTo(list[j - 1]) < 0) // 将大的值放在更后面
            {
                temp = list[j];
                list[j] = list[j - 1];
                list[j - 1] = temp;
                sorted = false;
            }
        }
        if (sorted) return;
    }
}

插入排序

就如同打牌时整理的方法,为新来的值在已有的排好序的数组中找好位置

public static void InsertionSort<T>(IList<T> list) where T : IComparable<T>
{
    int count = list.Count;
    if (count <= 1)
        return;
    T temp;
    for (int i = 1; i != count; ++i)
    {
        int low = -1, high = i; // 鉴于前i个数已经排序好了,我们可以用二分搜索寻找位置
        while (low + 1 != high) // assert: list[low] <= list[i]
        {
            int mid = (high - low) / 2 + low;
            if (list[i].CompareTo(list[mid]) < 0)
                high = mid;
            else
                low = mid;
        } // 此时low + 1就是所求的位置
        temp = list[i];
        for (int j = i - 1; j != low; --j) // (low, i - 1]的数后移为新数提供位置
            list[j + 1] = list[j];
        list[low + 1] = temp;
    }
}

选择排序

很好理解,在数组中找到最小(大)值之后放到开头(末尾)

public static void SelectionSort<T>(IList<T> list) where T : IComparable<T>
{
    T temp;
    for (int i = list.Count - 1; i > 0; --i)
    {
        int max = i;
        for (int j = i - 1; j >= 0; --j)
            if (list[max].CompareTo(list[j]) < 0)
                max = j; // 寻找最大值
        temp = list[i];
        list[i] = list[max];
        list[max] = temp;
    }
}

希尔排序

希尔排序是插入排序的改进

  • 使数组中任意间隔为seg的有序
  • 令seg逐渐减小
  • seg为1时数组有序
public static void ShellSort<T>(IList<T> list) where T : IComparable<T>
{
    int count = list.Count;
    int seg = 1;
    T temp;
    while (seg < count / 3)
        seg = seg * 3 + 1;
    while (seg > 0)
    {
        for (int i = seg; i < count; ++i)
        {
            temp = list[i];
            int j;
            for (j = i; j >= seg && temp.CompareTo(list[j - seg]) < 0; j -= seg)
                list[j] = list[j - seg];
            list[j] = temp;
        }
        seg /= 3;
    }
}

归并排序

  • 归并:将两个有序数组合成为一个有序数组

归并排序是基于归并手法和分治法思想的排序

  1. 长度为一的数组自然是有序的
  2. 将两个长度为一的有序数组合成为一个长度为二的有序数组
  3. 将两个长度为二的有序数组合成为一个长度为四的有序数组
  4. ...
  5. 直到将整个数组排序完
public static void MergeSort<T>(IList<T> list) where T : IComparable<T>
{
    int count = list.Count;
    if (count <= 1)
        return;
    IList<T> b = new T[count];
    IList<T> a = list;
    for (int seg = 1; seg < count; seg <<= 1)
    {
        for (int start = 0; start < count; start += seg << 1)
        {
            int low = start, high = Math.Min(low + (seg << 1), count), mid = Math.Min(low + seg, count);
            int i = low, j = mid, k = low; // 归并a[low:mid], a[mid:high]
            while (i != mid && j != high)
                b[k++] = a[j].CompareTo(a[i]) < 0 ? a[j++] : a[i++];
            while (i != mid)
                b[k++] = a[i++];
            while (j != high)
                b[k++] = a[j++];
        }
        var temp = a;
        a = b;
        b = temp; // 此时a指向更有序的数组
    }
    if (object.ReferenceEquals(b, list))
        for (int i = 0; i != count; ++i)
            list[i] = a[i];
}

堆排序

先将数组变为堆,再将堆变为排序好的数组

  • 堆:一种完全二叉树,满足其父节点的值大于(小于)子节点,称为最大堆(最小堆)
  • 完全二叉树可以用数组来实现
public static void HeapSort<T>(IList<T> list) where T : IComparable<T>
{
    int index = 0, count = list.Count;
    T temp; // swap
    // Array -> Heap
    while (++index < count) // 使用最大堆
    {
        int up;
        int i = index;
        while (i > 0 && list[up = (i - 1) >> 1].CompareTo(list[i]) < 0) // 子节点大于父节点,就交换
        {
            temp = list[up];
            list[up] = list[i];
            list[i] = temp;
            i = up;
        }
    }
    // Heap -> Sorted
    while (--index != 0)
    {
        temp = list[0];
        list[0] = list[index];
        list[index] = temp;
        int i = 0;
        int down;
        while ((down = (i << 1) + 1) < index)
        {
            if (down + 1 < index && list[down].CompareTo(list[down + 1]) < 0) // 如果有子节点大于父节点,就交换
                ++down;
            if (list[down].CompareTo(list[i]) < 0)
                break;
            temp = list[down];
            list[down] = list[i];
            list[i] = temp;
            i = down;
        }
    }
}

快速排序

基于分治法的一种排序,也是最被广泛应用的排序

  1. 寻找基准值
  2. 将小于基准值的放在左边,大于基准值的放在右边,基准值放中间
  3. 此时再对左右两侧进行1、2步直到长度为一
public static void QuickSort<T>(IList<T> list) where T : IComparable<T>
{
    int count = list.Count;
    if (count <= 1)
        return;
    (int, int)[] range = new (int, int)[count];
    T temp, sep;
    int p = 0;
    range[p++] = (0, count); // 用作栈,保存始末位置
    while (p != 0)
    {
        (int start, int stop) = range[--p];
        if (start + 2 > stop)
            continue;
        sep = list[start];
        int i = start, j = stop;
        while (true)
        {
            do ++i; // 此时list[i] <= sep,所以先让i递增一位
            while (i < stop && list[i].CompareTo(sep) < 0); // 循环结束后有list[i] >= sep
            do --j; // 此时j == stop || list[j] >= sep, 所以先让j递减一位
            while (list[j].CompareTo(sep) > 0); // 循环结束后有list[j] <= sep
                                                // list[start]是哨兵,j == start时会自动停下
            if (i > j)
                break; // 已经分好左右两边了
            temp = list[i];
            list[i] = list[j];
            list[j] = temp; // 使list[i] <= sep && list[j] >= sep
        }
        list[start] = list[j];
        list[j] = sep;
        range[p++] = (start, j);
        range[p++] = (j + 1, stop);
    }
}

计数排序

已知数组上限和下限,用一个辅助数组累计各个数出现的次数

public static void CountSort(IList<int> list, int lowerBound, int upperBound)
{
    int[] count = new int[upperBound - lowerBound];
    int index = 0;
    foreach (int i in list)
        ++count[i - lowerBound];
    for (int i = 0; i != count.Length; ++i)
        for (int j = 0, c = count[i]; j != c; ++j)
            list[index++] = i + lowerBound;
}

桶排序

将数分为几组,再对每组数进行排序

public static void BucketSort(IList<int> list, int bucketNum,
                              int lowerBound, int upperBound)
{
    var buckets = new System.Collections.Generic.List<int>[bucketNum];
    for (int i = 0; i != bucketNum; ++i)
        buckets[i] = new();
    foreach (int i in list)
        buckets[(int)((double)(i - lowerBound) /
                      (upperBound - lowerBound) *
                      bucketNum)].Add(i);
    foreach (var li in buckets)
        QuickSort(li);
    int index = 0;
    foreach (var li in buckets)
        foreach (int i in li)
            list[index++] = i;
}

性能分析

当以上述算法实现时

算法 时间复杂度 空间复杂度 稳定性
冒泡排序 (O(n^2)) (O(1)) (surd)
选择排序 (O(n^2)) (O(1)) (surd)
插入排序 (O(n^2)) (O(1)) (surd)
希尔排序 (?) (O(1))
堆排序 (O(nlog{n})) (O(1))
归并排序 (O(nlog{n})) (O(n)) (surd)
快速排序 (O(nlog{n})) (O(n))
程序员灯塔
转载请注明原文链接:排序算法 Sort
喜欢 (0)
违法和不良信息举报电话:022-22558618 举报邮箱:dljd@tidljd.com