- A+
所属分类：.NET技术
一 选择排序
选择排序的时间复杂度O(n2)，额外空间复杂度O(1)
public static void SelectionSort(int[] arr) { if (arr == null || arr.Length < 2) { return; } for (int i = 0; i < arr.Length - 1; i++)// i ~ n-1 { int minIndex = i; for (int j = i + 1; j < arr.Length; j++)// i+1 ~ n 上找到最小值的下标 { //从 i+1 的位置开始，逐个比较，得出最小值的索引 minIndex = arr[j] < arr[minIndex] ? j : minIndex; } //交换 i 位置 和 最小值索引位置的值 Swap(arr, i, minIndex); } } public static void Swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }
二 冒泡排序
冒泡排序的时间复杂度O(n2)，额外空间复杂度O(1)
public static void BubbleSort(int[] arr) { if (arr == null || arr.Length < 2) { return; } for (int e = arr.Length - 1; e > 0; e--)// e 从数组长度开始，逐渐缩小 e 范围 { for (int i = 0; i < e; i++) // i 从 0 开始遍历 到 e { if (arr[i] > arr[i + 1]) // 如果 i 位置的值 大于 i+1 位置的值，交换 { Swap(arr, i, i + 1); } } } } public static void Swap(int[] arr,int i,int j) { arr[i] = arr[i] ^ arr[j]; arr[j] = arr[i] ^ arr[j]; arr[i] = arr[i] ^ arr[j]; }
三 插入排序
插入排序的时间复杂度O(n2)，额外空间复杂度O(1)。最好情况下时间复杂度O(n)
public static void InsertionSort(int[] arr) { if (arr == null || arr.Length < 2) { return; } for (int i = 1; i < arr.Length; i++) //在 0 ~ i 范围内做到有序 { for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) { Swap(arr, j, j + 1); } } } public static void Swap(int[] arr, int i, int j) { arr[i] = arr[i] ^ arr[j]; arr[j] = arr[i] ^ arr[j]; arr[i] = arr[i] ^ arr[j]; }
四 异或运算 ^
4.1 关于异或运算
如果 x 计算结果为 true 且 y 计算结果为 false，或者 x 计算结果为 false 且 y 计算结果为 true，那么 x ^ y 的结果为 true。否则，结果为 false。
也就是说，对于 bool 操作数，^ 运算符的计算结果与不等运算符!= 相同。即相异为true，相同为false。
Console.WriteLine(true ^ true); // output: False Console.WriteLine(true ^ false); // output: True Console.WriteLine(false ^ true); // output: True Console.WriteLine(false ^ false); // output: False
而对于整型数值类型的操作数，^ 运算计算其操作数的位逻辑异或。
uint a = 0b_1111_1000; uint b = 0b_0001_1100; uint c = a ^ b; Console.WriteLine(Convert.ToString(c, toBase: 2)); // Output: // 11100100
对于整型操作数的异或，可以理解为无进位相加。
4.2 异或运算的性质
异或运算满足交换律和结合律。
a ^ b ^ c == a ^ c ^ b == b ^ ( a ^ c )
0 ^ n == 0 , n ^ n == 0
4.3 异或运算的应用
4.3.1 已知一个整型数组中只有一个数出现了奇数次，其他数出现了偶数次。如何找到这个数？要求时间复杂度O(n)，额外空间复杂度O(1)。
public static void PrintOddTimesNum1(int[] arr) { int eor = 0; for (int i = 0; i < arr.Length; i++) { eor = eor ^ arr[i]; } Console.WriteLine(eor); }
4.3.2 已知一个整型数组中只有两个数出现了奇数次，其他数出现了偶数次。如何找到这两个数？要求时间复杂度O(n)，额外空间复杂度O(1)。
public static void PrintOddTimesNum2(int[] arr) { int eor = 0; foreach (var item in arr) { eor = eor ^ item; } // eor = a ^ b // 因为 a!= b，所以 eor!= 0，则 eor必然有一位是1 int rightOne = eor & (~eor + 1); //取出eor最右边的1 int onlyOne = 0; foreach (var item in arr) { if ((item & rightOne) == 0) { onlyOne = onlyOne ^ item; } } Console.WriteLine(onlyOne); Console.WriteLine(onlyOne ^ eor); }
五 局部最小值问题
给定一个长度为n的无序数组，任何两个相邻的数不相等，如果0位置比1位置小，则0位置是局部最小，如果n-2位置比n-1位置小，则n-1位置是局部最小，
如果中间位置 i 比 i - 1 位置小且比 i + 1 位置小，则 i 位置是局部最小。
求一个局部最小值的位置，要求时间复杂度O(log n)
public static int GetLocalMinimum(int[] arr) { if (arr == null || arr.Length == 0) { return -1; } if (arr.Length == 1 || arr[0] < arr[1]) { return 0; } if (arr[arr.Length - 1] < arr[arr.Length - 2]) { return arr.Length - 1; } int mid = 0; int left = 1; int right = arr.Length - 2; while (left < right) { mid = left + ((right - left) >> 1); if (arr[mid - 1] < arr[mid]) { right = mid - 1; } else if (arr[mid + 1] < arr[mid]) { left = mid + 1; } else { return mid; } } return left; }
以上。
