一、基本概念

1、程序基石

在数据结构上设计流程（算法）

2、评估算法优劣的核心指标

• 时间复杂度（流程决定）:O(忽略掉系数的最高阶），只与数据量有关
• 额外空间复杂度（流程决定）：与功能无关，你自己必须开辟的额外空间（功能要求不算额外空间）
• 常数项时间（实现细节决定）：如果时间复杂度一样，就要关心常数项时间了。别用理论分析了，去用大数据去跑，测试时间。

常数时间的操作：
算术运算、位运算、赋值、比较、自增、自减、数组寻址
C# >>带符号位右移 不带符号位右移要&0x7fff ffff

O(1)本身为常数操作：不需要开辟新的空间。
开辟一个额外数组，额外空间复杂度为O(n)

2.1 C#中的几种排序方法

int[] arr = new int[]{2,3,5,4,6,8,7,9,4,3}
Array.Sort(arr)
数组自带的Sort，实现自动排序
Array.Reverse(arr)
通过Reverse,可实现倒序排序

另一种方法是通过数组扩展方法
var tmp = arr.OrderBy(item=>item);//此处的tmp为IEnumerable类型，可通过foreach进行迭代
var tmp2 = arr.OrderByDescending(item=>item);//Func委托，前面是参数，最后一个是返回值类型

2.2 选择排序(选最小值）

从1-N筛选出最小值，与第1个数进行交换。在2-N筛选出最小值，与第二个数交换。

 //选择排序法
        public static void selectionSort(int[] array) {
            if (array.Length < 2 || array == null) {
                return;
            }
            for (int i = 0; i < array.Length; i++) {
                int minIndex = i;
                for (int j = i+1; j < array.Length; j++) {
                    minIndex = array[j] < array[minIndex] ? j : minIndex;
                }
                swap(array, i, minIndex);
            }
        }
        public static void swap(int[] arr,int i,int j) {
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }

2.3 冒泡排序（选最大的值）

4 3 5 2 6
3 4 5 2 6 0-1
3 4 5 2 6 1-2
3 4 2 5 6 2-3
3 4 2 5 6 3-4

  //冒泡排序法
        public static void bubbleSort(int[] arr) {
            if (arr.Length < 2 || arr == null) {
                return;
            }
            for (int i = arr.Length-1; i > 0; i--) {
                for (int j = 0; j < i; j++) {
                    if (arr[j] > arr[j + 1]) {
                        swap(arr, j, j + 1);
                    }
                }
            }
        }

2.3 插入排序法（打牌插入）

//插入排序法  3 4 2 1 5  打牌插入
        public static void PlugSort(int[] arr) {
            if (arr.Length < 2 || arr == null) {
                return;
            }
            for (int i = 1; i < arr.Length; i++) {
                for (int j = i; j > 0; j--) {
                    if (arr[j] < arr[j - 1]) {
                        swap(arr, j, j - 1);
                    }
                }
            }
        }