首页 > 编程语言 >C# 实现排序算法

C# 实现排序算法

时间：2022-10-27 12:03:24浏览次数：66  
标签：count C# list seg int 算法 swap 排序

C#实现各种排序

每种排序的要点和实现

目录

文章中参数Func<T, T, bool> comp的意思是：排序后对于任意i < j，不可能有comp(list[j], list[i])

冒泡排序

  • 每次循环都将最值放到最前或者最后
  • 倒着排序，只需访问一次list.Count（可选）
  • 使用sorted布尔变量，如果中途已经排序好了就不用继续排了（可选）
  • 稳定，最值稳定上浮
public static void BubbleSort<T>(IList<T> list)
    where T : IComparable<T>
{
    for (int i = list.Count; i > 0; i--)
    {
        bool sorted = true;
        for (int j = 1; j < i; j++)
        {
            if (list[j].CompareTo(list[j - 1]) < 0)
            {
                T swap = list[j - 1];
                list[j - 1] = list[j];
                list[j] = swap;
                sorted = false;
            }
        }
        if (sorted)
            return;
    }
}
public static void BubbleSort<T>(IList<T> list, Func<T, T, bool> comp)
{
    for (int i = list.Count; i > 0; i--)
    {
        bool sorted = true;
        for (int j = 1; j < i; j++)
        {
            if (comp(list[j], list[j - 1]))
            {
                T swap = list[j - 1];
                list[j - 1] = list[j];
                list[j] = swap;
                sorted = false;
            }
        }
        if (sorted)
            return;
    }
}

选择排序

  • 每次都选出未排序段的最值，加入排序段
  • 倒着排序，只需访问一次list.Count（可选）
  • 不稳定，最值放入排序段时与最值交换的数位置改变
public static void SelectionSort<T>(IList<T> list)
    where T : IComparable<T>
{
    for (int i = list.Count - 1; i > 0; i--)
    {
        int maxIndex = i;
        T maxValue = list[i];
        for (int j = i - 1; j >= 0; j--)
        {
            T value = list[j];
            if (maxValue.CompareTo(value) < 0)
            {
                maxValue = value;
                maxIndex = j;
            }
        }
        T swap = list[i];
        list[i] = list[maxIndex];
        list[maxIndex] = swap;
    }
}
public static void SelectionSort<T>(IList<T> list, Func<T, T, bool> comp)
{
    for (int i = list.Count - 1; i > 0; i--)
    {
        int maxIndex = i;
        T maxValue = list[i];
        for (int j = i - 1; j >= 0; j--)
        {
            T value = list[j];
            if (comp(maxValue, value))
            {
                maxValue = value;
                maxIndex = j;
            }
        }
        T swap = list[i];
        list[i] = list[maxIndex];
        list[maxIndex] = swap;
    }
}

插入排序

  • 将新值插入已排序的一段中
  • 排序段已排序，可以使用二分搜索寻找插入位置（可使用其他方式）
  • 稳定，插入时遇到相同值保持相对位置
public static void InsertionSort<T>(IList<T> list)
    where T : IComparable<T>
{
    int count = list.Count;
    for (int i = 1; i < count; i++)
    {
        T insert = list[i];
        int low = -1, high = i;
        do
        {
            int mid = ((high - low) >> 1) + low;
            if (insert.CompareTo(list[mid]) < 0)
                high = mid;
            else
                low = mid;
        } while (low + 1 != high);
        for (int j = i; j > high; j--)
            list[j] = list[j - 1];
        list[high] = insert;
    }
}
public static void InsertionSort<T>(IList<T> list, Func<T, T, bool> comp)
{
    int count = list.Count;
    for (int i = 1; i < count; i++)
    {
        T insert = list[i];
        int low = -1, high = i;
        do
        {
            int mid = ((high - low) >> 1) + low;
            if (comp(insert, list[mid]))
                high = mid;
            else
                low = mid;
        } while (low + 1 != high);
        for (int j = i; j > high; j--)
            list[j] = list[j - 1];
        list[high] = insert;
    }
}

希尔排序

  • 每次循环结束后，将相隔距离为一个区间的值看作一组，这一组是有序的
  • 区间大小和区间每次缩小的倍数是可以选择的
  • 不稳定，值可能会跳到另一个区间中
public static void ShellSort<T>(IList<T> list)
    where T : IComparable<T>
{
    int count = list.Count;
    int seg = (count >> 1) + 1;
    while (seg > 0)
    {
        for (int i = seg; i < count; i++)
        {
            for (int j = i;
                 j >= seg && list[j].CompareTo(list[j - seg]) < 0;
                 j -= seg)
            {
                T swap = list[j];
                list[j] = list[j - seg];
                list[j - seg] = swap;
            }
        }
        seg /= 2;
    }
}
public static void ShellSort<T>(IList<T> list, Func<T, T, bool> comp)
{
    int count = list.Count;
    int seg = (count >> 1) + 1;
    while (seg > 0)
    {
        for (int i = seg; i < count; i++)
        {
            for (int j = i;
                 j >= seg && comp(list[j], list[j - seg]);
                 j -= seg)
            {
                T swap = list[j];
                list[j] = list[j - seg];
                list[j - seg] = swap;
            }
        }
        seg /= 2;
    }
}

堆排序

  • 数组\(\rightarrow\)堆\(\rightarrow\)已排序的数组
  • 堆是完全二叉树，完全二叉树可以用数组实现
  • 计算机倾向于将相邻地址的值同时载入，索引在数组中跳跃幅度过大，难以利用此功能
  • 不稳定，值在堆中移动，相同的值的相对位置受它们之间的值的影响
public static void HeapSort<T>(IList<T> list)
    where T : IComparable<T>
{
    int i = 0, count = list.Count;
    while (++i < count)
    {
        int j = i;
        int up;
        while (j > 0 && list[up = (j - 1) >> 1].CompareTo(list[j]) < 0)
        {
            T swap = list[up];
            list[up] = list[j];
            list[j] = swap;
            j = up;
        }
    }
    while (--i > 0)
    {
        T swap = list[i];
        list[i] = list[0];
        list[0] = swap;
        int j = 0;
        int down;
        while ((down = (j << 1) + 1) < i)
        {
            if (down + 1 < i && list[down].CompareTo(list[down + 1]) < 0)
                down++;
            if (list[down].CompareTo(list[j]) < 0)
                break;
            swap = list[down];
            list[down] = list[j];
            list[j] = swap;
            j = down;
        }
    }
}
public static void HeapSort<T>(IList<T> list, Func<T, T, bool> comp)
{
    int i = 0, count = list.Count;
    while (++i < count)
    {
        int j = i;
        int up;
        while (j > 0 && comp(list[up = (j - 1) >> 1], list[j]))
        {
            var swap = list[up];
            list[up] = list[j];
            list[j] = swap;
            j = up;
        }
    }
    while (--i > 0)
    {
        var swap = list[i];
        list[i] = list[0];
        list[0] = swap;
        int j = 0;
        int down;
        while ((down = (j << 1) + 1) < i)
        {
            if (down + 1 < i && comp(list[down], list[down + 1]))
                down++;
            if (comp(list[down], list[j]))
                break;
            swap = list[down];
            list[down] = list[j];
            list[j] = swap;
            j = down;
        }
    }
}

归并排序

  • 自底向上合并有序数组
  • 使用辅助数组，使用指针使原数组和辅助数组身份多次交换，最后将结果放回原数组
  • 稳定，合并有序数组时不改变相对位置
public static void MergeSort<T>(IList<T> list)
    where T : IComparable<T>
{
    int count = list.Count;
    IList<T> a = list;
    IList<T> b = new T[count];
    for (int seg = 1; seg < count; seg <<= 1)
    {
        for (int low = 0; low < count; low += seg << 1)
        {
            int mid = Math.Min(count, low + seg);
            int high = Math.Min(count, low + (seg << 1));
            int i = low, j = mid, k = low;
            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 swap = a;
        a = b;
        b = swap;
    }
    if (!ReferenceEquals(a, list))
        for (int i = 0; i != count; i++)
            list[i] = a[i];
}
public static void MergeSort<T>(IList<T> list, Func<T, T, bool> comp)
{
    int count = list.Count;
    IList<T> a = list;
    IList<T> b = new T[count];
    for (int seg = 1; seg < count; seg <<= 1)
    {
        for (int low = 0; low < count; low += seg << 1)
        {
            int mid = Math.Min(count, low + seg);
            int high = Math.Min(count, low + (seg << 1));
            int i = low, j = mid, k = low;
            while (i != mid && j != high)
                b[k++] = comp(a[j], a[i]) ? a[j++] : a[i++];
            while (i != mid)
                b[k++] = a[i++];
            while (j != high)
                b[k++] = a[j++];
        }
        var swap = a;
        a = b;
        b = swap;
    }
    if (!ReferenceEquals(a, list))
        for (int i = 0; i != count; i++)
            list[i] = a[i];
}

快速排序

  • 自顶向下使用基准分割数组
  • 使用随机数选择基准（可选）
  • 使用双指针分别从前往后和从后往前（可使用其他方式）
  • 不稳定，双指针的交换会改变顺序
public static void QuickSort<T>(IList<T> list)
    where T : IComparable<T>
{
    Stack<(int, int)> ranges = new Stack<(int, int)>();
    Random rand = new Random();
    ranges.Push((0, list.Count));
    while (ranges.Count != 0)
    {
        (int low, int high) = ranges.Pop();
        if (high <= low + 1)
            continue;
        int temp = rand.Next(low, high);
        T sep = list[temp];
        list[temp] = list[low];
        list[low] = sep;
        int i = low, j = high;
        for (; ; )
        {
            do
                i++;
            while (i < high && list[i].CompareTo(sep) < 0);
            do
                j--;
            while (sep.CompareTo(list[j]) < 0);
            if (i > j)
                break;
            T swap = list[i];
            list[i] = list[j];
            list[j] = swap;
        }
        list[low] = list[j];
        list[j] = sep;
        ranges.Push((low, j));
        ranges.Push((i, high));
    }
}
public static void QuickSort<T>(IList<T> list, Func<T, T, bool> comp)
{
    Stack<(int, int)> ranges = new Stack<(int, int)>();
    Random rand = new Random();
    ranges.Push((0, list.Count));
    while (ranges.Count != 0)
    {
        (int low, int high) = ranges.Pop();
        if (high - low <= 1)
            continue;
        int temp = rand.Next(low, high);
        T sep = list[temp];
        list[temp] = list[low];
        list[low] = sep;
        int i = low, j = high;
        for (; ; )
        {
            do
                i++;
            while (i < high && comp(list[i], sep));
            do
                j--;
            while (comp(sep, list[j]));
            if (i > j)
                break;
            T swap = list[i];
            list[i] = list[j];
            list[j] = swap;
        }
        list[low] = list[j];
        list[j] = sep;
        ranges.Push((low, j));
        ranges.Push((i, high));
    }
}

标签：count,C#,list,seg,int,算法,swap,排序
From： https://www.cnblogs.com/violeshnv/p/16831729.html

相关文章

  • C++ 的有理数类 Rational 实现
    classRational{staticinlineintgcd(inta,intb){if(!b)returnabs(a);while((a%=b)&&(b%=a));//doinwhileret......
  • 用 C++ 实现 Python 中的 range
    在C++中实现Python的range目录在C++中实现Python的range在实现过程中几个应该注意的问题整型溢出迭代器选择终止条件类型选择vector转换最终代码和Python对比代码在最后，......
  • c++ 中 const, constexpr 的使用
    目录参数例外返回值例外constthis和成员const_cast与constexpr的关系函数变量构造函数C++与C语言相比有着更强的类型检查，包括四种cast，左值右值之分，reference，以及......
  • 【服务器数据恢复】linux ext3文件系统执行FSCK后无法挂载的数据恢复案例
    服务器数据恢复环境：POWEREDGE系列某型号服务器；LINUX系统+RAID5。​服务器故障：管理员执行FSCK操作后LINUX系统无法MOUNT。服务器数据恢复过程：1、经过北亚数据恢复工程......
  • C#笔记 其三
    自定义集合集合接口IList<T>列表关键词：变长数组、有序集合、任意访问、索引常用方法：list.Add(T);list.Remove();list.RemoveAt(int);list.Sort();list.Sort(ICo......
  • mysql用select的子查询结果作为where后筛选条件
    mysqlselect查询语句where子句除了写子查询，还有没有更好的代替子查询的？一使用SELECT子句进行多表查询SELECT字段名FROM表1，表2…WHERE表1.字段=表2.字段AND其它查询条件SELE......
  • C#笔记 其一
    类类的声明和实例化classA{}//anotherfileF(){Aa=newA();//实例化类，new<类名>(实例化参数)Aaa;aa=newA();//先声明后实例化同样可行......
  • C#中的 `true` 和 `false` 运算符
    C#中的true和false运算符基础用法我们先定义一个示例用的类publicclassBoolTest{publicintX{get;set;}publicBoolTest(intx){X=x;}publ......
  • C#笔记（输入输出、格式化、注释）
    输入输出ConsoleKeyInfoc;do{c=Console.ReadKey();//读取按键}while(c.Key!=ConsoleKey.Escape);//等待输入Esc键strings=Console.ReadLine();i......
  • csharp-webuploader+csharp如何实现分片+断点续传
    ​文件夹数据库处理逻辑public class DbFolder{    JSONObjectroot;       public DbFolder()    {        this.root= new JSONOb......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99