devbox
算法构造者
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

算法.1-三大排序算法-对数器-二分

作者：算法构造者 | 2024-02-06 13:45:01

赞

踩

算法.1-三大排序算法-对数器-二分

三大排序算法&对数器

1.选择排序

Java版

  1. package class01;
  2.  
  3. import java.util.Arrays;
  4.  
  5. public class Code01_SelectionSort {
  6.  
  7. 	public static void selectionSort(int[] arr) {
  8. 		if (arr == null || arr.length < 2) {
  9. 			return;
  10. 		}
  11. 		// 0 ~ N-1  找到最小值，在哪，放到0位置上
  12. 		// 1 ~ n-1  找到最小值，在哪，放到1 位置上
  13. 		// 2 ~ n-1  找到最小值，在哪，放到2 位置上
  14. 		for (int i = 0; i < arr.length - 1; i++) {
  15. 			int minIndex = i;
  16. 			for (int j = i + 1; j < arr.length; j++) { // i ~ N-1 上找最小值的下标 
  17. 				minIndex = arr[j] < arr[minIndex] ? j : minIndex;
  18. 			}
  19. 			swap(arr, i, minIndex);
  20. 		}
  21. 	}
  22.  
  23. 	public static void swap(int[] arr, int i, int j) {
  24. 		int tmp = arr[i];
  25. 		arr[i] = arr[j];
  26. 		arr[j] = tmp;
  27. 	}
  28.  
  29. 	// for test
  30. 	public static void comparator(int[] arr) {
  31. 		Arrays.sort(arr);
  32. 	}
  33.  
  34. 	// for test
  35. 	public static int[] generateRandomArray(int maxSize, int maxValue) {
  36. 		// Math.random()   [0,1)  
  37. 		// Math.random() * N  [0,N)
  38. 		// (int)(Math.random() * N)  [0, N-1]
  39. 		int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
  40. 		for (int i = 0; i < arr.length; i++) {
  41. 			// [-? , +?]
  42. 			arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
  43. 		}
  44. 		return arr;
  45. 	}
  46.  
  47. 	// for test
  48. 	public static int[] copyArray(int[] arr) {
  49. 		if (arr == null) {
  50. 			return null;
  51. 		}
  52. 		int[] res = new int[arr.length];
  53. 		for (int i = 0; i < arr.length; i++) {
  54. 			res[i] = arr[i];
  55. 		}
  56. 		return res;
  57. 	}
  58.  
  59. 	// for test
  60. 	public static boolean isEqual(int[] arr1, int[] arr2) {
  61. 		if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
  62. 			return false;
  63. 		}
  64. 		if (arr1 == null && arr2 == null) {
  65. 			return true;
  66. 		}
  67. 		if (arr1.length != arr2.length) {
  68. 			return false;
  69. 		}
  70. 		for (int i = 0; i < arr1.length; i++) {
  71. 			if (arr1[i] != arr2[i]) {
  72. 				return false;
  73. 			}
  74. 		}
  75. 		return true;
  76. 	}
  77.  
  78. 	// for test
  79. 	public static void printArray(int[] arr) {
  80. 		if (arr == null) {
  81. 			return;
  82. 		}
  83. 		for (int i = 0; i < arr.length; i++) {
  84. 			System.out.print(arr[i] + " ");
  85. 		}
  86. 		System.out.println();
  87. 	}
  88.  
  89. 	// for test
  90. 	public static void main(String[] args) {
  91. 		int testTime = 500000;
  92. 		int maxSize = 100;
  93. 		int maxValue = 100;
  94. 		boolean succeed = true;
  95. 		for (int i = 0; i < testTime; i++) {
  96. 			int[] arr1 = generateRandomArray(maxSize, maxValue);
  97. 			int[] arr2 = copyArray(arr1);
  98. 			selectionSort(arr1);
  99. 			comparator(arr2);
  100. 			if (!isEqual(arr1, arr2)) {
  101. 				succeed = false;
  102. 				printArray(arr1);
  103. 				printArray(arr2);
  104. 				break;
  105. 			}
  106. 		}
  107. 		System.out.println(succeed ? "Nice!" : "Wrong!");
  108.  
  109. 		int[] arr = generateRandomArray(maxSize, maxValue);
  110. 		printArray(arr);
  111. 		selectionSort(arr);
  112. 		printArray(arr);
  113. 	}
  114.  
  115. }

C++ 

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7. void selectionSort(vector<int>& arr) {
  8.     if (arr.size() < 2) {
  9.         return;
  10.     }
  11.  
  12.     for (int i = 0; i < arr.size() - 1; i++) {
  13.         int minIndex = i;
  14.         for (int j = i + 1; j < arr.size(); j++) { // i ~ N-1 上找最小值的下标 
  15.             minIndex = arr[j] < arr[minIndex] ? j : minIndex;
  16.         }
  17.         swap(arr[i], arr[minIndex]);
  18.     }
  19. }
  20.  
  21. // for test
  22. void comparator(vector<int>& arr) {
  23.     sort(arr.begin(), arr.end());
  24. }
  25.  
  26. // for test
  27. vector<int> generateRandomArray(int maxSize, int maxValue) {
  28.     vector<int> arr((size_t)((maxSize + 1) * (double)rand() / RAND_MAX));
  29.     for (int i = 0; i < arr.size(); i++) {
  30.        
  31.         arr[i] = (int)((maxValue + 1) * (double)rand() / RAND_MAX) - (int)(maxValue * (double)rand() / RAND_MAX);
  32.     }
  33.     return arr;
  34. }
  35.  
  36. // for test
  37. vector<int> copyArray(const vector<int>& arr) {
  38.     if (arr.empty()) {
  39.         return {};
  40.     }
  41.     vector<int> res(arr.size());
  42.     for (size_t i = 0; i < arr.size(); i++) {
  43.         res[i] = arr[i];
  44.     }
  45.     return res;
  46. }
  47.  
  48. // for test
  49. bool isEqual(const vector<int>& arr1, const vector<int>& arr2) {
  50.     if ((arr1.empty() && !arr2.empty()) || (!arr1.empty() && arr2.empty())) {
  51.         return false;
  52.     }
  53.     if (arr1.empty() && arr2.empty()) {
  54.         return true;
  55.     }
  56.     if (arr1.size() != arr2.size()) {
  57.         return false;
  58.     }
  59.     for (size_t i = 0; i < arr1.size(); i++) {
  60.         if (arr1[i] != arr2[i]) {
  61.             return false;
  62.         }
  63.     }
  64.     return true;
  65. }
  66.  
  67. // for test
  68. void printArray(const vector<int>& arr) {
  69.     if (arr.empty()) {
  70.         return;
  71.     }
  72.     for (const auto& val : arr) {
  73.         cout << val << " ";
  74.     }
  75.     cout << endl;
  76. }
  77.  
  78. // for test
  79. int main() {
  80.     srand(time(nullptr));
  81.     int testTime = 500000;
  82.     int maxSize = 100;
  83.     int maxValue = 100;
  84.     bool succeed = true;
  85.     for (int i = 0; i < testTime; i++) {
  86.         vector<int> arr1 = generateRandomArray(maxSize, maxValue);
  87.         vector<int> arr2 = copyArray(arr1);
  88.         selectionSort(arr1);
  89.         comparator(arr2);
  90.         if (!isEqual(arr1, arr2)) {
  91.             succeed = false;
  92.             printArray(arr1);
  93.             printArray(arr2);
  94.             break;
  95.         }
  96.     }
  97.     cout << (succeed ? "Nice!" : "Wrong!") << endl;
  98.  
  99.     vector<int> arr = generateRandomArray(maxSize, maxValue);
  100.     printArray(arr);
  101.     selectionSort(arr);
  102.     printArray(arr);
  103.  
  104.     return 0;
  105. }

对数器

1，你想要测的方法a（最优解）

2，实现复杂度不好但是容易实现的方法b（暴力解）

3，实现一个随机样本产生器（长度也随机、值也随机）

4，把方法a和方法b跑相同的输入样本，看看得到的结果是否一样

5，如果有一个随机样本使得比对结果不一致，打印这个出错的样本进行人工干预，改对方法a和方法b

6，当样本数量很多时比对测试依然正确，可以确定方法a（最优解）已经正确。

关键是第5步，找到一个数据量小的错误样本，便于你去带入debug

然后把错误例子带入代码一步一步排查

Print大法、断点技术都可以

对数器的门槛其实是比较高的，因为往往需要在两种不同思路下实现功能相同的两个方法，暴力一个、想象中的最优解是另一个。

以后的很多题目都会用到对数器，几乎可以验证任何方法，尤其在验证贪心、观察规律方面很有用

到时候会丰富很多对数器的实战用法，这里只是一个简单易懂的示例

2.冒泡排序

  1. public class Code02_BubbleSort {
  2.  
  3. 	public static void bubbleSort(int[] arr) {
  4. 		if (arr == null || arr.length < 2) {
  5. 			return;
  6. 		}
  7. 		// 0 ~ N-1
  8. 		// 0 ~ N-2
  9. 		// 0 ~ N-3
  10. 		for (int e = arr.length - 1; e > 0; e--) { // 0 ~ e
  11. 			for (int i = 0; i < e; i++) {
  12. 				if (arr[i] > arr[i + 1]) {
  13. 					swap(arr, i, i + 1);
  14. 				}
  15. 			}
  16. 		}
  17. 	}
  18.  
  19. 	// 交换arr的i和j位置上的值
  20. 	public static void swap(int[] arr, int i, int j) {
  21. 		arr[i] = arr[i] ^ arr[j];
  22. 		arr[j] = arr[i] ^ arr[j];
  23. 		arr[i] = arr[i] ^ arr[j];
  24. 	}

3.插入排序（类似打扑克时摸到牌插牌的感觉）

  1. public static void insertionSort(int[] arr) {
  2. 		if (arr == null || arr.length < 2) {
  3. 			return;
  4. 		}
  5. 		// 不只1个数
  6. 		for (int i = 1; i < arr.length; i++) { // 0 ~ i 做到有序
  7. 			for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
  8. 				swap(arr, j, j + 1);
  9. 			}
  10. 		}
  11. 	}
  12.  
  13. 	// i和j是一个位置的话，会出错
  14. 	public static void swap(int[] arr, int i, int j) {
  15. 		arr[i] = arr[i] ^ arr[j];
  16. 		arr[j] = arr[i] ^ arr[j];
  17. 		arr[i] = arr[i] ^ arr[j];
  18. 	}

二分

1.在有序数组中确定num存在还是不存在

指针来到中间位置，中间值比n大意味着n-n-1位置都不可能，右指针来到mid-1，在左右之间再次取中间值递归

  1. package class01;
  2.  
  3. import java.util.Arrays;
  4.  
  5. public class Code04_BSExist {
  6.  
  7. 	public static boolean exist(int[] sortedArr, int num) {
  8. 		if (sortedArr == null || sortedArr.length == 0) {
  9. 			return false;
  10. 		}
  11. 		int L = 0;
  12. 		int R = sortedArr.length - 1;
  13. 		int mid = 0;
  14. 		// L..R
  15. 		while (L < R) { // L..R 至少两个数的时候
  16. 			mid = L + ((R - L) >> 1);
  17. 			if (sortedArr[mid] == num) {
  18. 				return true;
  19. 			} else if (sortedArr[mid] > num) {
  20. 				R = mid - 1;
  21. 			} else {
  22. 				L = mid + 1;
  23. 			}
  24. 		}
  25. 		return sortedArr[L] == num;
  26. 	}
  27. 	
  28. 	// for test
  29. 	public static boolean test(int[] sortedArr, int num) {
  30. 		for(int cur : sortedArr) {
  31. 			if(cur == num) {
  32. 				return true;
  33. 			}
  34. 		}
  35. 		return false;
  36. 	}
  37. 	
  38. 	
  39. 	// for test
  40. 	public static int[] generateRandomArray(int maxSize, int maxValue) {
  41. 		int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
  42. 		for (int i = 0; i < arr.length; i++) {
  43. 			arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
  44. 		}
  45. 		return arr;
  46. 	}
  47. 	
  48. 	public static void main(String[] args) {
  49. 		int testTime = 500000;
  50. 		int maxSize = 10;
  51. 		int maxValue = 100;
  52. 		boolean succeed = true;
  53. 		for (int i = 0; i < testTime; i++) {
  54. 			int[] arr = generateRandomArray(maxSize, maxValue);
  55. 			Arrays.sort(arr);
  56. 			int value = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
  57. 			if (test(arr, value) != exist(arr, value)) {
  58. 				succeed = false;
  59. 				break;
  60. 			}
  61. 		}
  62. 		System.out.println(succeed ? "Nice!" : "fuck!");
  63. 	}
  64.  
  65. }

2.在有序数组中找>=num的最左位置

  1. / 在arr上，找满足>=value的最左位置
  2. 	public static int nearestIndex(int[] arr, int value) {
  3. 		int L = 0;
  4. 		int R = arr.length - 1;
  5. 		int index = -1; // 记录最左的对号
  6. 		while (L <= R) { // 至少一个数的时候
  7. 			int mid = L + ((R - L) >> 1);
  8. 			if (arr[mid] >= value) {
  9. 				index = mid;
  10. 				R = mid - 1;
  11. 			} else {
  12. 				L = mid + 1;
  13. 			}
  14. 		}
  15. 		return index;
  16. 	}

3.最右 

  1. 	// 在arr上，找满足<=value的最右位置
  2. 	public static int nearestIndex(int[] arr, int value) {
  3. 		int L = 0;
  4. 		int R = arr.length - 1;
  5. 		int index = -1; // 记录最右的对号
  6. 		while (L <= R) {
  7. 			int mid = L + ((R - L) >> 1);
  8. 			if (arr[mid] <= value) {
  9. 				index = mid;
  10. 				L = mid + 1;
  11. 			} else {
  12. 				R = mid - 1;
  13. 			}
  14. 		}
  15. 		return index;
  16. 	}

4.寻找最小值，二分搜索不一定发生在有序数组上， 

  1. package class01;
  2.  
  3. public class Code06_BSAwesome {
  4.  
  5. 	public static int getLessIndex(int[] arr) {
  6. 		if (arr == null || arr.length == 0) {
  7. 			return -1; // no exist
  8. 		}
  9. 		if (arr.length == 1 || arr[0] < arr[1]) {
  10. 			return 0;
  11. 		}
  12. 		if (arr[arr.length - 1] < arr[arr.length - 2]) {
  13. 			return arr.length - 1;
  14. 		}
  15. 		int left = 1;
  16. 		int right = arr.length - 2;
  17. 		int mid = 0;
  18. 		while (left < right) {
  19. 			mid = (left + right) / 2;
  20. 			if (arr[mid] > arr[mid - 1]) {
  21. 				right = mid - 1;
  22. 			} else if (arr[mid] > arr[mid + 1]) {
  23. 				left = mid + 1;
  24. 			} else {
  25. 				return mid;
  26. 			}
  27. 		}
  28. 		return left;
  29. 	}
  30.  
  31. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/算法构造者/article/detail/62983
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号