数据结构与算法分析-C语言描述：习题记录

今天在学习本书第二章的习题部分的时候觉得习题2.7.c比较有意思故作记录，使用语言c#

1.三种算法的程序记录

算法1

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp3
{
    class Program
    {
        
        const int NUM = 80000;
        static void Main(string[] args)
        {
            System.Diagnostics.Stopwatch stopwatch = new System.Diagnostics.Stopwatch();
            stopwatch.Start();
            Console.WriteLine("N is:");
            string N = Console.ReadLine();//输入数据量
            Random random = new Random();//随机生成数据
            int rom = 0;
            int flag = 1;
            int[] nums = new int[NUM];
            for (int i = 0; i < int.Parse(N); i++)
            {
                rom = random.Next(int.Parse(N))+1;
                for (int j = 0; j < i; j++)//算法主体
                {
                    if (nums[j] == rom)
                    {
                        flag = 0;
                    }
                }
                if(flag == 1)
                {
                    nums[i] = rom;
                }
                else
                {
                    flag = 1;
                    i--;
                }

            }
            stopwatch.Stop();
            Console.WriteLine(stopwatch.Elapsed.Minutes + "分" + stopwatch.Elapsed.Seconds + "秒" + stopwatch.Elapsed.Milliseconds + "微秒");
            Console.ReadLine();
        }
    }
}

算法2

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp4
{
    class Program
    {
        static System.Diagnostics.Stopwatch stopwatch = new System.Diagnostics.Stopwatch();
        const int NUM = 680001;

        static void Main(string[] args)
        {
            
            stopwatch.Start();
            Console.WriteLine("N is:");
            string N = Console.ReadLine();
            Random random = new Random();
            int rom = 0;
            int flag = 1;
            int[] nums = new int[NUM];
            int[] numflag = new int[NUM];
            for (int i = 0; i < int.Parse(N); i++)
            {
                rom = random.Next(int.Parse(N)) + 1;
                if(numflag[rom] != 1)
                {
                    nums[i] = rom;
                    numflag[rom] = 1;
                }
                else
                {
                    i--;
                }

            }
            stopwatch.Stop();
            Console.WriteLine(stopwatch.Elapsed.Minutes + "分" + stopwatch.Elapsed.Seconds + "秒" + stopwatch.Elapsed.Milliseconds + "微秒");

            Console.ReadLine();
        }
    }
}

算法3

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp5
{
    class Program
    {
        const int NUM = 6400001;
        static void Main(string[] args)
        {
            System.Diagnostics.Stopwatch stopwatch = new System.Diagnostics.Stopwatch();
            stopwatch.Start();
            Console.WriteLine("N is:");
            string N = Console.ReadLine();
            Random random = new Random();
            int rom = 0;
            int flag = 1;
            int[] nums = new int[NUM];
            for(int j = 0; j < int.Parse(N); j++)
            {
                nums[j] = j + 1;
            }
            for (int i = 0; i < int.Parse(N); i++)
            {
                rom = random.Next(i);
                int a = nums[i];
                nums[i] = nums[rom];
                nums[rom] = a;

            }
            stopwatch.Stop();
            Console.WriteLine(stopwatch.Elapsed.Minutes + "分" + stopwatch.Elapsed.Seconds + "秒" + stopwatch.Elapsed.Milliseconds + "微秒");
            Console.ReadLine();
        }

运行结果

数量级2000

数量级80000

数量级640000

如有错误，望指出。