算法-2 选择排序、冒泡排序、插入排序

一 选择排序

选择排序的时间复杂度O(n2)，额外空间复杂度O(1)

1. public static void SelectionSort(int[] arr)
2. {
3.     if (arr == null || arr.Length < 2)
4.     {
5.         return;
6.     }
8.     for (int i = 0; i < arr.Length - 1; i++)// i ~ n-1
9.     {
10.         int minIndex = i;   
11.         for (int j = i + 1; j < arr.Length; j++)// i+1 ~ n 上找到最小值的下标
12.         {
13.             //从 i+1 的位置开始，逐个比较，得出最小值的索引
14.             minIndex = arr[j] < arr[minIndex] ? j : minIndex;
15.         }
16.         //交换 i 位置 和 最小值索引位置的值
17.         Swap(arr, i, minIndex);
18.     }
19. }
21. public static void Swap(int[] arr, int i, int j)
22. {
23.     int temp = arr[i];
24.     arr[i] = arr[j];
25.     arr[j] = temp;
26. }

复制代码

 
二 冒泡排序

冒泡排序的时间复杂度O(n2)，额外空间复杂度O(1)

1. public static void BubbleSort(int[] arr)
2. {
3.     if (arr == null || arr.Length < 2)
4.     {
5.         return;
6.     }
8.     for (int e = arr.Length - 1; e > 0; e--)// e 从数组长度开始，逐渐缩小 e 范围
9.     {
10.         for (int i = 0; i < e; i++)         // i 从 0 开始遍历 到 e
11.         {
12.             if (arr[i] > arr[i + 1])        // 如果 i 位置的值 大于 i+1 位置的值，交换
13.             {
14.                 Swap(arr, i, i + 1);
15.             }
16.         }
17.     }
18. }
20. public static void Swap(int[] arr,int i,int j)
21. {
22.     arr[i] = arr[i] ^ arr[j];
23.     arr[j] = arr[i] ^ arr[j];
24.     arr[i] = arr[i] ^ arr[j];
25. }

复制代码

 
三 插入排序

 插入排序的时间复杂度O(n2)，额外空间复杂度O(1)。最好情况下时间复杂度O(n)

1. public static void InsertionSort(int[] arr)
2. {
3.     if (arr == null || arr.Length < 2)
4.     {
5.         return;
6.     }
7.     for (int i = 1; i < arr.Length; i++) //在 0 ~ i 范围内做到有序
8.     {
9.         for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--)
10.         {
11.             Swap(arr, j, j + 1);
12.         }
13.     }
14. }
15. public static void Swap(int[] arr, int i, int j)
16. {
17.     arr[i] = arr[i] ^ arr[j];
18.     arr[j] = arr[i] ^ arr[j];
19.     arr[i] = arr[i] ^ arr[j];
20. }

复制代码

 
四 异或运算 ^

4.1 关于异或运算

如果 x 计算结果为 true 且 y 计算结果为 false，或者 x 计算结果为 false 且 y 计算结果为 true，那么 x ^ y 的结果为 true。否则，结果为 false。
也就是说，对于 bool 操作数，^ 运算符的计算结果与不等运算符!= 相同。即相异为true，相同为false。

1. Console.WriteLine(true ^ true);    // output: False
2. Console.WriteLine(true ^ false);   // output: True
3. Console.WriteLine(false ^ true);   // output: True
4. Console.WriteLine(false ^ false);  // output: False

复制代码

而对于整型数值类型的操作数，^ 运算计算其操作数的位逻辑异或。

1. uint a = 0b_1111_1000;
2. uint b = 0b_0001_1100;
3. uint c = a ^ b;
4. Console.WriteLine(Convert.ToString(c, toBase: 2));
5. // Output:
6. // 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)。

1. public static void PrintOddTimesNum1(int[] arr)
2. {
3.     int eor = 0;
4.     for (int i = 0; i < arr.Length; i++)
5.     {
6.         eor = eor ^ arr[i];
7.     }
8.     Console.WriteLine(eor);
9. }

复制代码

4.3.2 已知一个整型数组中只有两个数出现了奇数次，其他数出现了偶数次。如何找到这两个数？要求时间复杂度O(n)，额外空间复杂度O(1)。

1. public static void PrintOddTimesNum2(int[] arr)
2. {
3.     int eor = 0;
5.     foreach (var item in arr)
6.     {
7.         eor = eor ^ item;
8.     }
9.     // eor = a ^ b
10.     // 因为 a!= b，所以 eor!= 0，则 eor必然有一位是1
11.     int rightOne = eor & (~eor + 1); //取出eor最右边的1
12.     int onlyOne = 0;
13.     foreach (var item in arr)
14.     {
15.         if ((item & rightOne) == 0)
16.         {
17.             onlyOne = onlyOne ^ item;
18.         }
19.     }
20.     Console.WriteLine(onlyOne);
21.     Console.WriteLine(onlyOne ^ eor);
22. }

复制代码

 
五 局部最小值问题

给定一个长度为n的无序数组，任何两个相邻的数不相等，如果0位置比1位置小，则0位置是局部最小，如果n-2位置比n-1位置小，则n-1位置是局部最小，
如果中间位置 i 比 i - 1 位置小且比 i + 1 位置小，则 i 位置是局部最小。
求一个局部最小值的位置，要求时间复杂度O(log n)

1. public static int GetLocalMinimum(int[] arr)
2. {
3.     if (arr == null || arr.Length == 0)
4.     {
5.         return -1;
6.     }
7.     if (arr.Length == 1 || arr[0] < arr[1])
8.     {
9.         return 0;
10.     }
11.     if (arr[arr.Length - 1] < arr[arr.Length - 2])
12.     {
13.         return arr.Length - 1;
14.     }
16.     int mid = 0;
17.     int left = 1;
18.     int right = arr.Length - 2;
19.     while (left < right)
20.     {
21.         mid = left + ((right - left) >> 1);
22.         if (arr[mid - 1] < arr[mid])
23.         {
24.             right = mid - 1;
25.         }
26.         else if (arr[mid + 1] < arr[mid])
27.         {
28.             left = mid + 1;
29.         }
30.         else
31.         {
32.             return mid;
33.         }
34.     }
35.     return left;
36. }

复制代码

 
以上。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！