当前位置： 首页 > article >正文

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

article 2025/1/15 19:13:46

三大排序算法&对数器

1.选择排序

Java版

package class01;

import java.util.Arrays;

public class Code01_SelectionSort {

	public static void selectionSort(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		// 0 ~ N-1  找到最小值，在哪，放到0位置上
		// 1 ~ n-1  找到最小值，在哪，放到1 位置上
		// 2 ~ n-1  找到最小值，在哪，放到2 位置上
		for (int i = 0; i < arr.length - 1; i++) {
			int minIndex = i;
			for (int j = i + 1; j < arr.length; j++) { // i ~ N-1 上找最小值的下标 
				minIndex = arr[j] < arr[minIndex] ? j : minIndex;
			}
			swap(arr, i, minIndex);
		}
	}

	public static void swap(int[] arr, int i, int j) {
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}

	// for test
	public static void comparator(int[] arr) {
		Arrays.sort(arr);
	}

	// for test
	public static int[] generateRandomArray(int maxSize, int maxValue) {
		// Math.random()   [0,1)  
		// Math.random() * N  [0,N)
		// (int)(Math.random() * N)  [0, N-1]
		int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
		for (int i = 0; i < arr.length; i++) {
			// [-? , +?]
			arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
		}
		return arr;
	}

	// for test
	public static int[] copyArray(int[] arr) {
		if (arr == null) {
			return null;
		}
		int[] res = new int[arr.length];
		for (int i = 0; i < arr.length; i++) {
			res[i] = arr[i];
		}
		return res;
	}

	// for test
	public static boolean isEqual(int[] arr1, int[] arr2) {
		if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
			return false;
		}
		if (arr1 == null && arr2 == null) {
			return true;
		}
		if (arr1.length != arr2.length) {
			return false;
		}
		for (int i = 0; i < arr1.length; i++) {
			if (arr1[i] != arr2[i]) {
				return false;
			}
		}
		return true;
	}

	// for test
	public static void printArray(int[] arr) {
		if (arr == null) {
			return;
		}
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
		System.out.println();
	}

	// for test
	public static void main(String[] args) {
		int testTime = 500000;
		int maxSize = 100;
		int maxValue = 100;
		boolean succeed = true;
		for (int i = 0; i < testTime; i++) {
			int[] arr1 = generateRandomArray(maxSize, maxValue);
			int[] arr2 = copyArray(arr1);
			selectionSort(arr1);
			comparator(arr2);
			if (!isEqual(arr1, arr2)) {
				succeed = false;
				printArray(arr1);
				printArray(arr2);
				break;
			}
		}
		System.out.println(succeed ? "Nice!" : "Wrong!");

		int[] arr = generateRandomArray(maxSize, maxValue);
		printArray(arr);
		selectionSort(arr);
		printArray(arr);
	}

}

C++ 

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

void selectionSort(vector<int>& arr) {
    if (arr.size() < 2) {
        return;
    }

    for (int i = 0; i < arr.size() - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < arr.size(); j++) { // i ~ N-1 上找最小值的下标 
            minIndex = arr[j] < arr[minIndex] ? j : minIndex;
        }
        swap(arr[i], arr[minIndex]);
    }
}

// for test
void comparator(vector<int>& arr) {
    sort(arr.begin(), arr.end());
}

// for test
vector<int> generateRandomArray(int maxSize, int maxValue) {
    vector<int> arr((size_t)((maxSize + 1) * (double)rand() / RAND_MAX));
    for (int i = 0; i < arr.size(); i++) {
       
        arr[i] = (int)((maxValue + 1) * (double)rand() / RAND_MAX) - (int)(maxValue * (double)rand() / RAND_MAX);
    }
    return arr;
}

// for test
vector<int> copyArray(const vector<int>& arr) {
    if (arr.empty()) {
        return {};
    }
    vector<int> res(arr.size());
    for (size_t i = 0; i < arr.size(); i++) {
        res[i] = arr[i];
    }
    return res;
}

// for test
bool isEqual(const vector<int>& arr1, const vector<int>& arr2) {
    if ((arr1.empty() && !arr2.empty()) || (!arr1.empty() && arr2.empty())) {
        return false;
    }
    if (arr1.empty() && arr2.empty()) {
        return true;
    }
    if (arr1.size() != arr2.size()) {
        return false;
    }
    for (size_t i = 0; i < arr1.size(); i++) {
        if (arr1[i] != arr2[i]) {
            return false;
        }
    }
    return true;
}

// for test
void printArray(const vector<int>& arr) {
    if (arr.empty()) {
        return;
    }
    for (const auto& val : arr) {
        cout << val << " ";
    }
    cout << endl;
}

// for test
int main() {
    srand(time(nullptr));
    int testTime = 500000;
    int maxSize = 100;
    int maxValue = 100;
    bool succeed = true;
    for (int i = 0; i < testTime; i++) {
        vector<int> arr1 = generateRandomArray(maxSize, maxValue);
        vector<int> arr2 = copyArray(arr1);
        selectionSort(arr1);
        comparator(arr2);
        if (!isEqual(arr1, arr2)) {
            succeed = false;
            printArray(arr1);
            printArray(arr2);
            break;
        }
    }
    cout << (succeed ? "Nice!" : "Wrong!") << endl;

    vector<int> arr = generateRandomArray(maxSize, maxValue);
    printArray(arr);
    selectionSort(arr);
    printArray(arr);

    return 0;
}

对数器

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

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

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

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

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

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

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

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

Print大法、断点技术都可以

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

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

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

2.冒泡排序

public class Code02_BubbleSort {

	public static void bubbleSort(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		// 0 ~ N-1
		// 0 ~ N-2
		// 0 ~ N-3
		for (int e = arr.length - 1; e > 0; e--) { // 0 ~ e
			for (int i = 0; i < e; i++) {
				if (arr[i] > arr[i + 1]) {
					swap(arr, i, i + 1);
				}
			}
		}
	}

	// 交换arr的i和j位置上的值
	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];
	}

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

public static void insertionSort(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		// 不只1个数
		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);
			}
		}
	}

	// i和j是一个位置的话，会出错
	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];
	}

二分

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

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

package class01;

import java.util.Arrays;

public class Code04_BSExist {

	public static boolean exist(int[] sortedArr, int num) {
		if (sortedArr == null || sortedArr.length == 0) {
			return false;
		}
		int L = 0;
		int R = sortedArr.length - 1;
		int mid = 0;
		// L..R
		while (L < R) { // L..R 至少两个数的时候
			mid = L + ((R - L) >> 1);
			if (sortedArr[mid] == num) {
				return true;
			} else if (sortedArr[mid] > num) {
				R = mid - 1;
			} else {
				L = mid + 1;
			}
		}
		return sortedArr[L] == num;
	}
	
	// for test
	public static boolean test(int[] sortedArr, int num) {
		for(int cur : sortedArr) {
			if(cur == num) {
				return true;
			}
		}
		return false;
	}
	
	
	// for test
	public static int[] generateRandomArray(int maxSize, int maxValue) {
		int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
		for (int i = 0; i < arr.length; i++) {
			arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
		}
		return arr;
	}
	
	public static void main(String[] args) {
		int testTime = 500000;
		int maxSize = 10;
		int maxValue = 100;
		boolean succeed = true;
		for (int i = 0; i < testTime; i++) {
			int[] arr = generateRandomArray(maxSize, maxValue);
			Arrays.sort(arr);
			int value = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
			if (test(arr, value) != exist(arr, value)) {
				succeed = false;
				break;
			}
		}
		System.out.println(succeed ? "Nice!" : "fuck!");
	}

}

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

/ 在arr上，找满足>=value的最左位置
	public static int nearestIndex(int[] arr, int value) {
		int L = 0;
		int R = arr.length - 1;
		int index = -1; // 记录最左的对号
		while (L <= R) { // 至少一个数的时候
			int mid = L + ((R - L) >> 1);
			if (arr[mid] >= value) {
				index = mid;
				R = mid - 1;
			} else {
				L = mid + 1;
			}
		}
		return index;
	}

3.最右 

	// 在arr上，找满足<=value的最右位置
	public static int nearestIndex(int[] arr, int value) {
		int L = 0;
		int R = arr.length - 1;
		int index = -1; // 记录最右的对号
		while (L <= R) {
			int mid = L + ((R - L) >> 1);
			if (arr[mid] <= value) {
				index = mid;
				L = mid + 1;
			} else {
				R = mid - 1;
			}
		}
		return index;
	}

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

package class01;

public class Code06_BSAwesome {

	public static int getLessIndex(int[] arr) {
		if (arr == null || arr.length == 0) {
			return -1; // no exist
		}
		if (arr.length == 1 || arr[0] < arr[1]) {
			return 0;
		}
		if (arr[arr.length - 1] < arr[arr.length - 2]) {
			return arr.length - 1;
		}
		int left = 1;
		int right = arr.length - 2;
		int mid = 0;
		while (left < right) {
			mid = (left + right) / 2;
			if (arr[mid] > arr[mid - 1]) {
				right = mid - 1;
			} else if (arr[mid] > arr[mid + 1]) {
				left = mid + 1;
			} else {
				return mid;
			}
		}
		return left;
	}

}


http://www.kler.cn/a/229477.html

相关文章：

  • Java Stream流操作List全攻略：Filter、Sort、GroupBy、Average、Sum实践
  • 鸿蒙面试 2025-01-10
  • IDEA的Git界面(ALT+9)log选项不显示问题小记
  • 基于python的网页表格数据下载--转excel
  • FastDDS安装测试记录
  • 在 Safari 浏览器中，快速将页面恢复到 100% 缩放（也就是默认尺寸）Command (⌘) + 0 (零)
  • 什么是TCP三次握手、四次挥手?
  • 绕过过滤空格的 SQL 注入
  • 微服务介绍
  • Javascript | JS如何断点测试(WebStorm)
  • pytest的常用插件和Allure测试报告
  • 【蓝桥杯选拔赛真题91】Scratch筛选数据 第十五届蓝桥杯scratch图形化编程 少儿编程创意编程选拔赛真题解析
  • 宠物空气净化器哪个品牌质量好？实惠的猫用猫用净化器牌子测评
  • 计算机设计大赛 深度学习+opencv+python实现车道线检测 - 自动驾驶
  • 在每个地方都应该添加 memo 吗?
  • 【ArcGIS微课1000例】0101：删除冗余节点或折点
  • 计算机网络——03网络核心
  • 详解Python3的垃圾回收机制
  • 国内领先的酒店用品采购平台「尚和酒店」×企企通B2B2B商城上线，引领酒店用品行业数智升级
  • 在 CentOS 7上使用 Apache 和 mod_wsgi 部署 Django 应用的方法
  • Nginx使用详解
  • 6、基于机器学习的预测
  • 4. 树（二叉树、二叉查找树/二叉排序树/二叉搜索树、平衡二叉树、平衡二叉B树/红黑树）
  • 【JavaScript】Js中一些数组常用API总结
  • 面试数据结构与算法总结分类+leetcode目录【基础版】
  • 流量控制原理