追光学院
Yang Liangxi
2021-03-05

数组

说明

假设算法要解决问题的输入规模是 n

# 数组时间复杂度

静态数组

连续的一次性分配内存，之后无法随意更改其大小。

简单情况下，数组的时间复杂度如下：

  • 在末尾追加元素：O(1)O(1)
  • 在中间插入元素：O(n)O(n)
  • 删除末尾元素：O(1)O(1)
  • 删除末尾元素：O(n)O(n)
  • 查索引值元素：O(1)O(1)
  • 改索引值元素：O(1)O(1)
  • 查元素的索引值：O(n)O(n)

# 数组冒泡排序

using System;
using System.Diagnostics;

namespace AlgorithmTest
{
    public class SortAlgorithm
    {
        /// <summary>
        /// 冒泡排序
        /// </summary>
        /// <param name="arr"></param>
        private static void BubbleSort(int[] arr)
        {
            int n = arr.Length;
            bool swapped;
            for (int i = 0; i < n - 1; i++)
            {
                swapped = false;
                for (int j = 0; j < n - 1 - i; j++)
                {
                    if (arr[j] > arr[j + 1])
                    {
                        int temp = arr[j + 1];
                        arr[j + 1] = arr[j];
                        arr[j] = temp;
                        swapped = true;
                    }
                }
                if (!swapped) break;
            }
        }

        // 代码说明：
        // swapped 标志：用于检测内层循环是否发生了交换。如果没有发生交换，说明数组已经有序，可以提前退出循环，减少不必要的比较。
        // 内层循环优化：每次外层循环后，最大的元素会被移动到正确的位置，因此内层循环的次数可以减少 i 次。

        /// <summary>
        /// 测试
        /// </summary>
        /// <param name="n"></param>
        private static void TestSort(int n, Action<int[]> action)
        {
            // 创建一个随机数组
            Random rand = new();
            int[] arr = new int[n];
            for (int i = 0; i < arr.Length; i++)
            {
                arr[i] = rand.Next(1, n);
            }

            // 获取当前进程
            Process process = Process.GetCurrentProcess();
            // 记录初始内存占用
            long memoryBefore = process.WorkingSet64;

            // 创建 Stopwatch 实例
            Stopwatch stopwatch = new();
            // 开始计时
            stopwatch.Start();
            // 调用排序算法
            action(arr);
            // 停止计时
            stopwatch.Stop();

            // 记录排序后的内存占用
            long memoryAfter = process.WorkingSet64;

            Console.WriteLine($"排序完成，数组规模 = {n}");
            // 输出运行时间
            Console.WriteLine($"耗时: {stopwatch.ElapsedMilliseconds} 毫秒");
            // 输出内存占用
            Console.WriteLine($"排序前内存占用: {memoryBefore / 1024} KB");
            Console.WriteLine($"排序后内存占用: {memoryAfter / 1024} KB");
            Console.WriteLine($"内存增加: {(memoryAfter - memoryBefore) / 1024} KB");
        }

        /// <summary>
        /// 测试冒泡排序
        /// </summary>
        /// <param name="n">数组规模大小</param>
        public static void TestBubbleSort(int n)
        {
            TestSort(n, BubbleSort);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

using System;

namespace ConsoleApp
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = 400000;
            AlgorithmTest.SortAlgorithm.TestBubbleSort(n);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
第一组：
排序完成，数组规模 = 100000
耗时: 29,366 毫秒

第二组:
排序完成，数组规模 = 200000
耗时: 119,604 毫秒

第三组：
排序完成，数组规模 = 400000
耗时: 472,737 毫秒
1
2
3
4
5
6
7
8
9
10
11

# 数组选择排序

using System;
using System.Diagnostics;

namespace AlgorithmTest
{
    public class SortAlgorithm
    {
        /// <summary>
        /// 选择排序
        /// </summary>
        /// <param name="arr"></param>
        private static void SelectionSort(int[] arr)
        {
            int n = arr.Length;
            for (int i = 0; i < n - 1; i++)
            {
                int minIndex = i;
                for (int j = i + 1; j < n; j++)
                {
                    if (arr[j] < arr[minIndex])
                    {
                        minIndex = j;
                    }
                }

                if (minIndex != i)
                {
                    int temp = arr[minIndex];
                    arr[minIndex] = arr[i];
                    arr[i] = temp;
                }
            }
        }

        /// <summary>
        /// 测试
        /// </summary>
        /// <param name="n"></param>
        private static void TestSort(int n, Action<int[]> action)
        {
            //... ... 代码同上
        }

        /// <summary>
        /// 测试选择排序
        /// </summary>
        /// <param name="n"></param>
        public static void TestSelectionSort(int n)
        {
            TestSort(n, SelectionSort);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

using System;

namespace ConsoleApp
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = 400000;
            AlgorithmTest.SortAlgorithm.TestSelectionSort(n);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
第一组：
排序完成，数组规模 = 100000
耗时: 9,861 毫秒

第二组:
排序完成，数组规模 = 200000
耗时: 42,073 毫秒

第三组：
排序完成，数组规模 = 400,000
耗时: 166,741 毫秒
1
2
3
4
5
6
7
8
9
10
11

# 数组插入排序

using System;
using System.Diagnostics;

namespace AlgorithmTest
{
    public class SortAlgorithm
    {
        /// <summary>
        /// 插入排序
        /// </summary>
        /// <param name="arr"></param>
        private static void InsertionSort(int[] arr)
        {
            int n = arr.Length;

            for (int i = 1; i < n; i++)
            {
                int curr = arr[i]; // 当前插入的元素
                int j = i - 1;

                while (j >= 0 && arr[j] > curr)  // 往后移动
                {
                    arr[j + 1] = arr[j];
                    j--;
                }

                arr[j + 1] = curr; //插入当前元素
            }
        }

        /// <summary>
        /// 测试
        /// </summary>
        /// <param name="n"></param>
        private static void TestSort(int n, Action<int[]> action)
        {
            //... ... 代码同上
        }

        /// <summary>
        /// 测试插入排序
        /// </summary>
        /// <param name="n"></param>
        public static void TestInsertionSort(int n)
        {
            TestSort(n, InsertionSort);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

using System;

namespace ConsoleApp
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = 400000;
            AlgorithmTest.SortAlgorithm.TestInsertionSort(n);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
第一组：
排序完成，数组规模 = 100000
耗时: 6,621 毫秒

第二组:
排序完成，数组规模 = 200000
耗时: 26,927 毫秒

第三组：
排序完成，数组规模 = 400000
耗时: 108,720 毫秒
1
2
3
4
5
6
7
8
9
10
11

# 数组希尔排序

using System;
using System.Diagnostics;

namespace AlgorithmTest
{
    public class SortAlgorithm
    {
        /// <summary>
        /// 希尔排序
        /// </summary>
        /// <param name="arr"></param>
        private static void ShellSort(int[] arr)
        {
            int n = arr.Length;

            for (int gap = n / 2; gap > 0; gap /= 2)
            {
                for (int i = gap; i < n; i++)
                {
                    int temp = arr[i];
                    int j;

                    for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
                    {
                        arr[j] = arr[j - gap];
                    }

                    arr[j] = temp;
                }
            }
        }

        /// <summary>
        /// 测试
        /// </summary>
        /// <param name="n"></param>
        private static void TestSort(int n, Action<int[]> action)
        {
            //... ... 代码同上
        }

        /// <summary>
        /// 测试希尔排序
        /// </summary>
        /// <param name="n"></param>
        public static void TestShellSort(int n)
        {
            TestSort(n, ShellSort);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

using System;

namespace ConsoleApp
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = 400000;
            AlgorithmTest.SortAlgorithm.TestShellSort(n);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
到此可以看出希尔排序已经比先前的算法较为优秀了！

第一组：
排序完成，数组规模 = 100000
耗时: 26 毫秒

第二组:
排序完成，数组规模 = 200000
耗时: 59 毫秒

第三组：
排序完成，数组规模 = 400000
耗时: 134 毫秒
1
2
3
4
5
6
7
8
9
10
11
12
13

# 数组的归并排序

using System;
using System.Diagnostics;

namespace AlgorithmTest
{
    public class SortAlgorithm
    {
        /// <summary>
        /// 归并排序
        /// </summary>
        /// <param name="arr"></param>
        private static void MergeSort(int[] arr)
        {
            if (arr.Length <= 1)
                return;

            int mid = arr.Length / 2;

            // 分隔数组
            int[] left_arr = new int[mid];
            int[] right_arr = new int[arr.Length - mid];

            Array.Copy(arr, 0, left_arr, 0, mid);
            Array.Copy(arr, mid, right_arr, 0, arr.Length - mid);

            // 递归排序
            MergeSort(left_arr);
            MergeSort(right_arr);
            // 合并
            Merge(arr, left_arr, right_arr);
        }

        private static void Merge(int[] arr, int[] left, int[] right)
        {
            int i = 0, j = 0, k = 0;
            // 合并两个有序数组
            while (i < left.Length && j < right.Length)
            {
                if (left[i] <= right[j])
                {
                    arr[k] = left[i];
                    i++;
                }
                else
                {
                    arr[k] = right[j];
                    j++;
                }
                k++;
            }

            // 将数组剩余元素拷贝到数组中
            while (i < left.Length)
            {
                arr[k] = left[i];
                i++;
                k++;
            }
            while (j < right.Length)
            {
                arr[k] = right[j];
                j++;
                k++;
            }
        }

        /// <summary>
        /// 测试
        /// </summary>
        /// <param name="n"></param>
        private static void TestSort(int n, Action<int[]> action)
        {
            //... ... 代码同上
        }

        /// <summary>
        /// 测试归并排序
        /// </summary>
        /// <param name="n"></param>
        public static void TestMergeSort(int n)
        {
            TestSort(n, MergeSort);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

using System;

namespace ConsoleApp
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = 400000;
            AlgorithmTest.SortAlgorithm.TestShellSort(n);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
到此可以看出归并排序已经比先前的算法更为优秀了！

第一组：
排序完成，数组规模 = 100000
耗时: 24 毫秒

第二组:
排序完成，数组规模 = 200000
耗时: 53 毫秒

第三组：
排序完成，数组规模 = 400000
耗时: 85 毫秒
1
2
3
4
5
6
7
8
9
10
11
12
13
编辑 (opens new window)
#数组
上次更新: 2025/02/13, 19:15:01

←

最近更新
01
Git问题集合
01-29
02
安装 Nginx 服务器
01-25
03
安装 Docker 容器
01-25
更多文章>
冀ICP备2025101965号
vdoing 支持|copyright©2021-2025 Yang Liangxi
×
×