标签：---------------- nums c# ++ Length int 算法 test array

排序算法

参考文章：https://blog.csdn.net/weixin_61361738/article/details/128794945

冒泡排序

namespace ConsoleApp1
{
    internal class Program
    {
        static void Main(string[] args)
        {
            string str=Console.ReadLine();
            string[] strarr = str.Split(',');
            int[] intarr= new int[strarr.Length];
            for (int i = 0; i < strarr.Length; i++)
            {
                intarr[i] = Convert.ToInt32(strarr[i]);
            }
            for(int i = 0;i<intarr.Length-1; i++)// 外层循环控制循环次数
            {
                for(int j = 0;j<intarr.Length-1-i; j++)//内层循环用于交换相邻要素
                {
                    int temp;
                    // if (split[j] < split[j + 1])倒序排列
                    if (intarr[j] > intarr[j + 1])
                    {
                        temp = intarr[j + 1];
                        intarr[j + 1] = intarr[j];
                        intarr[j] = temp;
                    }
                }
            }
            string result = "";
            foreach(int i in intarr)
            {
                result += i + ",";
            }
            Console.WriteLine(result);
            Console.ReadLine();
        }
    }
}

选择排序

namespace ConsoleApp1
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int[] test = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
            for(int i = 0; i < test.Length; i++)
            {
                // 找无序区中最小的元素 
                int minindex = i;
                for(int j=i+1; j<test.Length; j++)
                {
                    if (test[j] < test[minindex])
                    {
                        minindex = j;
                    }
                }
                //执行完上面的循环
                //minindex就是无序区最小元素的索引
                //把最小元素和有序区交换位置
                int temp = test[i];
                test[i] = test[minindex];
                test[minindex] = temp;
            }
            foreach(int item in test)
            {
                Console.WriteLine(item);
            }
            Console.ReadKey();
        }
    }
}

插入排序

namespace ConsoleApp1
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int[] test = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
            for (int i = 0; i < test.Length - 1; i++)//最后一位不用排序
            {
                int curNum = test[i + 1];     // 无序区的第一个元素 
                int idx = i;    //有序区的最后一个元素的索引

                while (idx >= 0 && test[idx] > curNum)
                {
                    test[idx + 1] = test[idx];  // 把有序区的元素往后挪一位
                    idx -= 1;
                }
                test[idx + 1] = curNum;
            }
            foreach (int item in test)
            {
                Console.WriteLine(item);
            }
            Console.ReadKey();
        }
    }
}

快速排序

using System.Collections.Concurrent;

namespace ConsoleApp1
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int[] test = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
            QuickSort2(test, 0, test.Length - 1);
            foreach (int item in test)
            {
                Console.WriteLine(item);
            }
            Console.ReadKey();
        }

        /*第二种方法：用数组计算，此方法无需生成新的数组，
         * 而是人为的将一个数组划分两个区域.
         * 数组大了之后计算速度比较快
         */
        //将一个数组看为两个，第一个小数组起点为原数组的起点
        //第二个大数组起点为原数组的终点
        public static void QuickSort2(int[] list, int left, int right)
        {
            if (left >= right)//若数组的左端下标大于或等于右端下标，则表明数组为一或空
            {
                return;//结束方法
            }
            int i, j, temp;
            i = left;
            j = right;
            temp = list[left];//将数组中的第一个元素当做基准值
            while (i != j)//当i=j时，表明将大于基准值的数和小于基准值的数全部分开
            {
                while (list[j] >= temp && i < j)
                {
                    j--;
                }
                while (list[i] <= temp && i < j)
                {
                    i++;
                }
                //交换数组中大于基准值的数和小于基准值的数
                if (i < j)
                {
                    int t = list[i];
                    list[i] = list[j];
                    list[j] = t;
                }
            }
            //将基准值放到大数组和小数组中间
            list[left] = list[i];
            list[i] = temp;
            QuickSort2(list, i + 1, right);
            QuickSort2(list, left, i - 1);

        }
    }
}

归并排序

public class Solution
{
    // 合并
    public static int[] merge(int[] left, int[] right)
    {
        // 最终返回一个合并好的有序的数组
        // 定义两个变量,分别代表当前left与right的未添加进有序数组的第一个元素
        int leftIndex = 0, rightIndex = 0;
        List<int> res = new List<int>();        
       
        while (leftIndex < left.Length && rightIndex < right.Length)
        {
            //左边数组的元素小于右边数组 
            if (left[leftIndex] <= right[rightIndex])
            {
                // 把左边元素添加到有序区中 
                res.Add(left[leftIndex]);
                // 索引往后移
                leftIndex ++; 
            }
            else
            {
                // 把右边元素添加到有序区中 
                res.Add(right[rightIndex]);
                // 索引往后移 
                rightIndex ++; 
            }
        }

        // 把剩余的未添加的元素全部添加到有序数组后面
        foreach (int item in right[rightIndex..])    
        {
            res.Add(item);
        }

        // 为什么可以直接添加?因为left,right本身就是一个有序数组
        foreach (int item in left[leftIndex..])      
        {
            res.Add(item);
        }
        // 如果说left_idx走完了,right还剩一些元素,说明right剩下的元素全部都比有序数组的最后一个元素要大
        return res.ToArray();
    }

    // 归并排序
    public static int[] mergeSort(int[] nums)
    {
        //数组不能再分了
        if (nums.Length <= 1)
            return nums;
        int mid = nums.Length / 2;      // 求出数组的中间位置 
        
        int[] left = mergeSort(nums[..mid]);
        int[] right = mergeSort(nums[mid..]);
   
        // 合并
        return merge(left, right); 
    }

    // 归并排序 
    static void Main(string[] args)
    {
        int[] nums = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48}; 
        int[] result = mergeSort(nums);
        foreach(int item in result)
        {
            Console.WriteLine(item);
        }
    }
}

计数排序

public class Program
{
    // 计数排序
    public static void CountingSort(int[] array)
    {
        // 长度小于等于0直接return
        if (array.Length <= 0) 
            return;

        int min = array[0];     
        int max = min;
        // 找出数组最大元素和最小元素 
        foreach (int item in array)
        {
            if (item > max)
            {
                max = item;
            }
            else if (item < min)
            {
                min = item;
            }
        }

        // 把所有元素存入counting数组 
        int[] counting = new int[max - min + 1];
        for (int i = 0; i < array.Length; i++)
        {
            counting[array[i] - min] += 1;
        }

        int index = -1;
        for (int i = 0; i < counting.Length; i++)
        {
            for (int j = 0; j < counting[i]; j++)
            {
                index++;
                array[index] = i + min;
            }
        }
    }


    public static void Main(string[] args)
    {
        int[] array = { 43, 69, 11, 72, 28, 21, 56, 80, 48, 94, 32, 8 };
        CountingSort(array);

        foreach(int item in array)
        {
            Console.WriteLine(item);
        }
    } 
}

基数排序

public class Program
{
    // 基数排序 
    public static void RadixSort(int[] array, int bucketNum)
    {
        int maxLength = MaxLength(array);

        //创建bucket时，在二维中增加一组标识位，
        //其中bucket[x, 0]表示这一维所包含的数字的个数
        //通过这样的技巧可以少写很多代码
        int[,] bucket = new int[bucketNum, array.Length + 1];

        for (int i = 0; i < maxLength; i++)
        {
            foreach (var num in array)
            {
                int bit = (int)(num / Math.Pow(10, i) % 10);
                bucket[bit, ++bucket[bit, 0]] = num;
            }

            for (int count = 0, j = 0; j < bucketNum; j++)
            {
                for (int k = 1; k <= bucket[j, 0]; k++)
                {
                    array[count++] = bucket[j, k];
                }
            }

            //最后要重置这个标识
            for (int j = 0; j < bucketNum; j++)
            {
                bucket[j, 0] = 0;
            }

        }
    }

    private static int MaxLength(int[] array)
    {
        if (array.Length <= 0) 
            return 0;
            
        int max = array.Max();      // 取出数组的最大值 
        return (int)Math.Log10(max) + 1;    // 取出位数 
    }


    public static void Main(string[] args)
    {
        int[] array = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
        RadixSort(array, 10);
        foreach (int item in array)
        {
            Console.WriteLine(item);
        }
    }
}

桶排序

public class Program
{
    // 桶排序
    static void BucketSort(int[] array, int bucketsize = 5)
    {
        int max = array.Max(), min = array.Min();               // 最大值与最小值
        int bucketnums = (max - min) / bucketsize + 1;           // 分配的桶数量

        List<List<int>> buckets = new List<List<int>>();
        // 生成桶
        for (int i = 0; i < bucketnums; i++)
        {
            buckets.Add(new List<int>());
        }

        //将数组的元素放入桶中,并保证桶里是有序的        
        for (int i = 0; i < array.Length; i++)
        {
            int bucketIndex = (array[i] - min) / bucketsize;
            buckets[bucketIndex].Add(array[i]);
        }

        int index = 0;
        for (int i = 0; i < buckets.Count; i++)
        {
            buckets[i].Sort();      // 对生成的每个桶排序 
            for (int j = 0; j < buckets[i].Count; j++)
            {
                array[index++] = buckets[i][j];
            }
        }
    }
    
    static void Main(string[] args)
    {
        int[] test = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
        BucketSort(test); 
        
        foreach(int item in test)
        {
            Console.WriteLine(item);
        }
    }
}

堆排序

class Program
{
    // 堆排序 
    public static void HeapSort(int[] nums)
    {
        //将最大的值推到堆顶
        //x根据最后一个子节点的位置计算出父节点
        int x = Convert.ToInt32(Math.Floor(Convert.ToDouble((nums.Length - 2) / 2)));
        for (int i = x; i >= 0; i--)
        {
            //如果子元素只存在左子元素时, 让右子元素等于左子元素
            while (nums[i] < nums[i * 2 + 1] || nums[i] < nums[(i * 2 + 2) > (nums.Length - 1) ? (i * 2 + 1) : i * 2 + 2])
            {
                if (nums[i * 2 + 1] >= nums[(i * 2 + 2) > (nums.Length - 1) ? (i * 2 + 1) : i * 2 + 2])
                {
                    int index = nums[i];
                    nums[i] = nums[i * 2 + 1];
                    nums[i * 2 + 1] = index;
                }
                else
                {
                    int index = nums[i];
                    nums[i] = nums[i * 2 + 2];
                    nums[i * 2 + 2] = index;
                }
            }
        }
        //输出堆顶最大的元素
        int max = nums[0];
        nums[0] = nums[nums.Length - 1];
        Console.WriteLine(max);
        //将数组中的最后一个元素删除
        int[] num = new int[nums.Length - 1];
        for (int j = 0; j < nums.Length - 1; j++)
        {
            num[j] = nums[j];
        }

        Adjust(num);
    }


    public static void Adjust(int[] nums)
    {
        if (nums.Length > 1) HeapSort(nums);
        else Console.WriteLine("{0}\t", nums[0]);
    }

    static void Main(string[] args)
    {
        int[] nums = new int[] { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
        Adjust(nums);
    }
}

希尔排序

public class Program
{
    // 希尔排序 
    public static void shellSort(int[] nums)
    {
        int n = nums.Length;    // 数组的长度 
        int gap = n / 2;    // 设定一个增量gap 
        
        while(gap >= 1)
        {
            // 分组
            for(int i = gap; i < n; i++) 
            {
                int curNum = nums[i];   // 当前要插入的无序区的元素的值
                int idx = i - gap;      // 当前元素所在小组的有序区的最后一个元素的索引 
                while (idx >= 0 && curNum < nums[idx])      // 插入排序
                {
                    nums[idx + gap] = nums[idx];
                    idx -= gap;
                }
                nums[idx+gap] = curNum; 
            }
            gap /= 2;   // 缩小增量 
        }
    }
     
   
    static void Main(string[] args)
    {
        int[] test = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
        shellSort(test); 
        foreach(int item in test)
        {
            Console.WriteLine(item);
        }
    }
}

查找重复字母算法

namespace ConsoleApp1
{
    internal class Program
    {
        static void Main(string[] args)
        {
            string str=Console.ReadLine();
            int[] countArray = new int[26];
            string c = "";
            for(int i = 0; i < str.Length; i++)
            {
                countArray[str[i] - 'a'] = countArray[(str[i] - 'a')] + 1;
            }
            for(int i = 0;i < str.Length; i++)
            {
                if(countArray[str[i] - 'a'] > 1)
                {
                    if (!c.Contains(str[i])) 
                    {
                        c += str[i].ToString() + ",";
                    }
                }
            }
            if(string.IsNullOrEmpty(c))
            {
                c = "null";
            }
            Console.WriteLine(c);
            Console.ReadKey();
        }
    }
}

排序算法	平均时间复杂度	最好情况	最坏情况	空间复杂度	稳定性
冒泡排序	O(n²)	O(n)	O(n²)	O(1)	稳定
选择排序	O(n²)	O(n²)	O(n²)	O(1)	不稳定
插入排序	O(n²)	O(n)	O(n²)	O(1)	稳定
快速排序	O(nlogⁿ)	O(nlogⁿ)	O(n²)	O(logⁿ)	不稳定
随机快速排序	O(n²)	O(nlgⁿ)	O(n²)	O(1)	不稳定
归并排序	O(nlogⁿ)	O(nlogⁿ)	O(nlogⁿ)	O(n)	稳定
计数排序	O(n + k)	O(n + k)	O(n + k)	O(k)	稳定
基数排序	O(n × \times ×k)	O(n × \times ×k)	O(n × \times ×k)	O(n + k)	稳定
桶排序	O(n + k)	O(n + k)	O(n²)	O(n + k)	稳定
堆排序	O(nlogⁿ)	O(nlogⁿ)	O(nlogⁿ)	O(1)	不稳定
希尔排序	O(nlogⁿ)	O(nlog²n)	O(nlog²n)	O(1)	稳定

标签：----------------,nums,c#,++,Length,int,算法,test,array
From： https://www.cnblogs.com/misakayoucn/p/17608482.html

c#学习笔记----------------c#简单算法之排序算法

排序算法

相关文章

赞助商

阅读排行