CSharp算法

LeetCode

7.整数反转

/// <summary>
/// 7.整数反转
/// 给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。
/// 如果反转后整数超过 32 位的有符号整数的范围[?231, 231 ? 1] ，就返回 0。
/// </summary>
/// <returns></returns>
public static int Reverse(int x)
{
    int res = 0;

    while (x != 0)
    {
        int t = x % 10;
        x /= 10;

        if (res > int.MaxValue / 10 || (res == int.MaxValue / 10 && t > 7))
        {
            return 0;
        }
        if (res < int.MinValue / 10 || (res == int.MinValue / 10 && t < -8))
        {
            return 0;
        }
        res = res * 10 + t;
    }
    return res;
}

洗牌算法

public static List<int> Pukes;
public static void InitPukes()
{
    Pukes = new List<int>(54);
    for (int i = 0; i < 54; i++)
    {
        Pukes.Add(i + 1);
    }

    Console.WriteLine("***装牌完毕***");
    for (int i = 0; i < Pukes.Count; i++)
    {
        Console.WriteLine(Pukes[i] + " ");
    }
}

Fisher_Yates算法

/// <summary>
      /// Fisher_Yates算法
      /// 取两个列表，一个是洗牌前的序列A{1,2….54}，一个用来放洗牌后的序列B，B初始为空
      /// while A不为空,随机从A取一张牌加入B末尾
      /// 空间O（n），时间O（n^2)
      /// </summary>
      public static void Fisher_Yates()
      {
          Random r = new Random();
          List<int> newPuckes = new List<int>(Pukes.Count);
          for (int i = 0; i < 54; i++)
          {
              //Random.Range(minValue,maxValue) [minValue,maxValue)
              int randomIndex = r.Next(0, Pukes.Count);
              int puke = Pukes[randomIndex];
              newPuckes.Add(puke);
              Pukes.RemoveAt(randomIndex);
          }

          Console.WriteLine("***洗牌完毕***");
          for (int i = 0; i < newPuckes.Count; i++)
          {
              Console.WriteLine(newPuckes[i] + " ");
          }
      }

Knuth_Durstenfeld算法

/// <summary>
/// Knuth_Durstenfeld算法 是最佳的洗牌算法
/// 每次从未处理的数据中随机取出一个数字，然后把该数字放在数组的尾部， 即数组尾部存放的是已经处理过的数字。
/// 这是一个原地打乱顺序的算法，算法时间复杂度也从Fisher算法的 O ( n 2 )提升到了 O ( n )
/// </summary>
public static void Knuth_Durstenfeld()
{
    Random r = new Random();

    for (int i = Pukes.Count - 1; i > 0; --i)
    {
        int randomIndex = r.Next(0, i + 1);
        int bottom = Pukes[i];
        Pukes[i] = Pukes[randomIndex];
        Pukes[randomIndex] = bottom;
    }

    Console.WriteLine("***洗牌完毕***");
    for (int i = 0; i < Pukes.Count; i++)
    {
        Console.WriteLine(Pukes[i] + " ");
    }
}

排序算法

public static List<int> AfterLst;

public static void Swap(List<int> data,int x,int y)
{
    data[x] = data[x] + data[y];
    data[y] = data[x] - data[y];
    data[x] = data[x] - data[y];
}

public static void InitAfterLst()
{
    Random r = new Random();
    int range = r.Next(0, 50);
    AfterLst = new List<int>(range);
    for (int i = 0; i < range; i++)
    {
        int randomIndex = r.Next(0, 50);
        AfterLst.Add(randomIndex);
    }
    Console.WriteLine("***数组生成完毕***");
    for (int i = 0; i < AfterLst.Count; i++)
    {
        Console.WriteLine(AfterLst[i] + " ");
    }
}

选择排序

/// <summary>
/// 选择排序
/// 原理：找出参与排序的数组最大值，放到末尾（或找到最小值放到开头）
/// 过程解析：将剩余数组的最小数交换到开头。
/// https://zh.wikipedia.org/wiki/%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F
/// </summary>
public static void SelectSort()
{
    for (int i = 0; i < AfterLst.Count - 1; i++)
    {
        int min = i;
        int temp = AfterLst[i];
        for (int j = i + 1; j < AfterLst.Count; j++)
        {
            if (AfterLst[j] < temp)
            {
                min = j;
                temp = AfterLst[j];
            }
        }

        if (min != i)
        {
            AfterLst[min] = AfterLst[i];
            AfterLst[i] = temp;
        }
    }

    Console.WriteLine("***选择排序完毕***");
    for (int i = 0; i < AfterLst.Count; i++)
    {
        Console.WriteLine(AfterLst[i] + " ");
    }
}

冒泡排序

/// <summary>
/// 冒泡排序
/// 原理：从头开始，每一个元素和它的下一个元素比较，如果它大，就将它与比较的元素交换，否则不动。
/// 这意味着，大的元素总是在向后慢慢移动直到遇到比它更大的元素。所以每一轮交换完成都能将最大值冒到最后。
/// 解析:需要注意的是j<i，每轮冒完泡必然会将最大值排到数组末尾，所以需要排序的数应该是在减少的。
/// https://zh.wikipedia.org/wiki/%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F#.E5.8A.A9.E8.AE.B0.E7.A0.81
/// </summary>
public static void BubbleSort()
{
    for (int i = AfterLst.Count - 1; i > 0; i--)
    {
        for (int j = 0; j < i; j++)
        {
            if (AfterLst[j] > AfterLst[j + 1])
            {
                AfterLst[j + 1] = AfterLst[j + 1] + AfterLst[j];
                AfterLst[j] = AfterLst[j + 1] - AfterLst[j];
                AfterLst[j + 1] = AfterLst[j + 1] - AfterLst[j];
            }
        }
    }

    Console.WriteLine("***冒泡排序完毕***");
    for (int i = 0; i < AfterLst.Count; i++)
    {
        Console.WriteLine(AfterLst[i] + " ");
    }
}

冒泡排序（标识版）

/// <summary>
/// 冒泡排序（标识版）
/// 解析：发现某轮冒泡没有任何数进行交换（即已经有序），就跳出排序。
/// </summary>
public static void BubbleSortWithFlag()
{
    bool flag;

    for (int i = AfterLst.Count - 1; i > 0; i--)
    {
        flag = true;
        for (int j = 0; j < i; j++)
        {
            if (AfterLst[j] > AfterLst[j + 1])
            {
                AfterLst[j + 1] = AfterLst[j + 1] + AfterLst[j];
                AfterLst[j] = AfterLst[j + 1] - AfterLst[j];
                AfterLst[j + 1] = AfterLst[j + 1] - AfterLst[j];
                flag = false;
            }
        }

        if (flag)
        {
            break;
        }
    }

    Console.WriteLine("***冒泡排序(标识)完毕***");
    for (int i = 0; i < AfterLst.Count; i++)
    {
        Console.WriteLine(AfterLst[i] + " ");
    }
}

鸡尾酒排序（来回排序）

/// <summary>
/// 鸡尾酒排序（来回排序）
/// 冒泡排序只是单向冒泡，而鸡尾酒来回反复双向冒泡。
/// 原理：自左向右将大数冒到末尾，然后将剩余数列再自右向左将小数冒到开头，如此循环往复。
/// 解析：分析第i轮冒泡，i是偶数则将剩余数列最大值向右冒泡至末尾，是奇数则将剩余数列最小值.
/// 向左冒泡至开头。对于剩余数列，n为始，AfterLst.Count-1-m为末。
/// https://zh.wikipedia.org/wiki/%E9%B8%A1%E5%B0%BE%E9%85%92%E6%8E%92%E5%BA%8F
/// </summary>
public static void BubbleCocktailSort()
{
    bool flag;
    int m = 0, n = 0;

    for (int i = AfterLst.Count - 1; i > 0; i--)
    {
        flag = true;

        if (i % 2 == 0)
        {
            for (int j = n; j < AfterLst.Count - 1 - m; j++)
            {
                if (AfterLst[j] > AfterLst[j + 1])
                {
                    AfterLst[j + 1] = AfterLst[j + 1] + AfterLst[j];
                    AfterLst[j] = AfterLst[j + 1] - AfterLst[j];
                    AfterLst[j + 1] = AfterLst[j + 1] - AfterLst[j];
                    flag = false;
                }
            }
            if (flag) break;
            m++;
        }
        else
        {
            for (int k = AfterLst.Count - 1 - m; k > n; k--)
            {
                if (AfterLst[k] < AfterLst[k - 1])
                {
                    AfterLst[k - 1] = AfterLst[k - 1] + AfterLst[k];
                    AfterLst[k] = AfterLst[k - 1] - AfterLst[k];
                    AfterLst[k - 1] = AfterLst[k - 1] - AfterLst[k];
                    flag = false;
                }
            }

            if (flag) break;
            n++;
        }
    }