一 選擇排序
選擇排序的時間復雜度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; }
以上，
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/536166.html
標籤：.NET技术