概述: 冒泡排序是一种简单直观的排序算法。它重复的走访要排序的数列,一次比较两个元素,按照一定的顺序,如果顺序错误就将他们交换过来。重复进行直到没有再需要交换,也就是该数组已经排序完成。这个算法名字的又来是因为越小的元素会经交换慢慢“浮”到数列的头部。
算法步骤
1.比较相邻的元素。如果第一个比第二个大,就进行交换
2.对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对。做完这一步之后,最后一个元素就是最大的数
3.重复1 2 步骤,除了最后一个元素。对越来越少的元素重复上面的步骤,知道没有任何一对数字需要比较
public static void sort(int[] str) {
if (str == null || str.length == 0) {
return;
}
for (int i = 0; i < str.length; i++) {
for (int j = 0; j < str.length - 1 - i; j++) {
if (str[j] > str[j + 1]) {
int temp = str[j];
str[j] = str[j + 1];
str[j + 1] = temp;
}
}
}
}
时间复杂度
O(n^2)
概述: 选择排序也是一种简单直观的排序算法,无论什么数据进去都是O(n^2)的时间复杂度。所以使用选择排序时,数据规模越小越好。唯一的好处可能就是不占用额外的内存空间。
算法步骤
1.在未排序序列中找到最小(大)元素,存放到排序序列的起始位置
2.从剩余未排序元素中寻找最小(大)元素,然后放到已排序序列的末尾
3.重复第二步,直到所有元素均排序完毕
Java代码
public static void sort(int[] str){
if(str==null || str.length==0){
return;
}
for (int i = 0; i < str.length; i++) {
int min = i;
for (int j = i; j < str.length; j++) {
if(str[min]>str[j]){
min = j;
}
}
// 将最小值放在索引为i的位置
if(min!=i){
int temp = str[i];
str[i] = str[min];
str[min] = temp;
}
}
}
时间复杂度
O(n^2)
概述: 插入排序的代码实现起来虽然没有冒泡排序和选择排序那么简单粗暴,但它的原理是最容易理解的,插入排序的原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。
算法步骤
将待排序序列第一个元素看成一个有序序列,将第二个元素到最后一个元素看成未排序的序列。从头到尾依次扫描未排序序列,将扫描到的每个元素插入有序序列的适当位置。(如果待插入的元素与有序序列中的某个元素相等,则将待插入元素插入到相等元素的后面)
Java代码
public static void sort(int[] str) {
for (int i = 1; i < str.length; i++) {
int temp = str[i];
int j = i - 1;
while (j >= 0) {
if (str[j] > temp) {
str[j + 1] = str[j];
j--;
} else {
break;
}
}
str[j + 1] = temp;
}
}
概述: 希尔排序也称递减增量排序算法,是插入排序的一种更高效的改进版本。但是希尔排序是不是很稳定。
算法步骤
选择一个增量序列t1,t2,…tn 其中tn=1
按照增量序列个数n,对序列进行k趟排序,每趟排序将这些子序列用插入排序进行排序知道当增量因子为1时,整个序列作为一个序列处理
Java代码
public static void sort(int[] str) {
if (str == null || str.length == 0) {
return;
}
for (int temp = str.length / 2; temp >= 1; temp /= 2) {
for (int i = temp; i < str.length; i++) {
int flag = str[i];
int j = i - temp;
while (j >= 0) {
if (str[j] > flag) {
str[j + temp] = str[j];
j -= temp;
} else {
break;
}
}
str[j + temp] = flag;
}
}
}
概述: 归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。
算法步骤
1.申请空间,使其大小为两个已经排序的序列之和,该空间用来存放合并后的序列
2.设定两个指针,最初位置分别为两个已经排序序列的起始位置
3.比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
4.重复步骤3知道某一指针到达序列尾
5.将另一序列所剩下的所有元素直接复制到合并序列尾
Java代码
public static int[] sort(int[] str) {
if (str == null || str.length < 2) {
return str;
}
int middle = str.length / 2;
int[] left = Arrays.copyOfRange(str, 0, middle);
int[] right = Arrays.copyOfRange(str, middle, str.length);
return merge(sort(left), sort(right));
}
public static int[] merge(int[] left, int[] right) {
int[] result = new int[left.length + right.length];
int i = 0;
int m = 0;
int n = 0;
while (m < left.length && n < right.length) {
if (left[m] < right[n]) {
result[i++] = left[m++];
} else {
result[i++] = right[n++];
}
}
while (m < left.length) {
result[i++] = left[m++];
}
while (n < right.length) {
result[i++] = right[n++];
}
return result;
}
概述: 快速排序的最坏运行情况是O(n^2),比如说顺序数列的快排,但它的平摊期望时间是O(nlogn), 且O(nlogn)记号中隐含的常数因子很小,比复杂度稳定等于O(nlogn)的归并排序要小很多。所以,对绝大多数顺序性较弱的随机数列而言,快速排序总是优于归并排序。
算法步骤
1.从数列中挑出一个元素,称为“基准”(pivot)
2.重新排列数列,所有比基准值小的摆放在基准前面,所有元素比基准值大的把放在后面,相同的数可以放任一边。在这个分区退出之后,该基准就处于数列的中间位置,这个称为分区(partition)操作
3.递归的(recursive)把小于基准值的元素的子数列和大于基准值元素的子数列排序
Java代码
public static void sort(int[] str, int left, int right) {
// 递归到底的情况
if (left >= right) {
return;
}
// 递归操作
int pivot = str[left];
int i = left;
int j = right;
while (i < j) {
// 从右边开始找第一个小于pivot的元素
while (i < j && str[j] > pivot) {
j--;
}
// 替换
if (i < j) {
str[i] = str[j];
i++;
}
// 从左边开始找到第一个比pivot大的元素、
while (i < j && str[i] < pivot){
i++;
}
// 替换
if(i<j){
str[j] = str[i];
j--;
}
}
str[i] = pivot;
sort(str, left, i-1);
sort(str, i+1, right);
}
数据结构之堆的概念:
概述: 堆排序就是利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或大于)它的父结点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法:
算法步骤
1.构建一个堆(将完全二叉树整理成堆)
2.把堆首(最大值)和堆尾互换(下沉操作)
3.调用shift down方法,使除过堆尾元素的树满足最大堆的性质
4.重复步骤2,直到堆中只有一个元素
Java代码
public static void sort(int str[]) {
if (str == null || str.length == 0) {
return;
}
// 构建堆,将完全二叉树整理成堆
heapify(str);
// 排序
for (int i = 0; i < str.length-1; i++) {
// 将首位元素替换
int temp = str[0];
str[0] = str[i];
str[i] = temp;
// 整理成堆
siftDown(0, str, i);
}
}
public static void heapify(int[] str) {
// 找到最后一个元素的父亲结点
int parentIndex = getParentIndex(str.length - 1);
// 从最后一个元素的父亲结点开始进行下沉操作,直到根结点
for (; parentIndex >= 0; parentIndex--) {
siftDown(parentIndex, str, str.length);
}
}
// 获取堆的根结点,根结点一般都是最中间
public static int getParentIndex(int index) {
if (index < 0) {
throw new IllegalArgumentException("index is invalid!");
}
if (index == 0) {
// 处理根结点
return -1;
}
return (index - 1) / 2;
}
// 根据当前数组所在的索引获取左孩子结点的索引
private static int getLeftChileIndex(int index) {
return index * 2 + 1;
}
// 下沉操作
private static void siftDown(int curIndex, int[] str, int length) {
int leftChildIndex = getLeftChileIndex(curIndex);
int changeIndex = leftChildIndex;
while (leftChildIndex < length) {
int rightChildIndex = leftChildIndex + 1;
if (rightChildIndex < length && str[rightChildIndex] > str[leftChildIndex]) {
changeIndex = rightChildIndex;
}
if(str[changeIndex]>str[curIndex]){
// 交换操作
int temp = str[curIndex];
str[curIndex] = str[changeIndex];
str[changeIndex] = temp;
curIndex = changeIndex;
leftChildIndex = getLeftChileIndex(curIndex);
changeIndex = leftChildIndex;
}else{
break;
}
}
}
时间复杂度
O(nlogn)
概述: 计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序,计数排序要求输入的数据必须是有确定范围的整数。
特点: 计数排序不是比较排序,排序的速度快于任何比较排序算法。由于用来计数的数组的长度取决于待排序数组中数据的范围(等于待排序数组的最大值与最小值的差加上1),这使得计数排序对于数据范围很大的数组,需要大量时间和内存。
算法步骤
1.找出待排序的数组中最大和最小的元素
2.统计数组中每个值为i的元素出现的次数,存入数组的第i项
3.对所有的计数累加
4.反向填充目标数组
Java代码
// 辅助函数,查找数组最大值
private static int getMaxVal(int[] str) {
int max = str[0];
for (int i = 0; i < str.length; i++) {
max = Math.max(max, str[i]);
}
return max;
}
public static void sort(int[] str) {
if (str == null || str.length == 0) {
return;
}
// 获取数组中最大的值
int maxVal = getMaxVal(str);
// 创建一个数组用来计数
int[] counts = new int[maxVal + 1];
// 计数
for (int i = 0; i < str.length; i++) {
counts[str[i]]++;
}
// 反向填充
int index = 0;
for (int i = 0; i < counts.length; i++) {
while (counts[i] > 0) {
str[index++] = i;
counts[i]--;
}
}
}
时间复杂度
当输入的元素是n个0到k之间的整数时,运行时间为O(n+k)
概述: 桶排序是计数排序的升级版。它利用了函数的映射关系,高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效,我们需要做到这两点:
算法步骤
1.创建容器(桶)
2.初始化桶
3.将数据放入桶内
4.分别对每个桶进行排序
5.将桶中的元素反向填充到数组中
Java代码
public static void sort(int[] str) {
if (str == null || str.length == 0) {
return;
}
// 创建桶
List<Integer>[] buckets = new ArrayList[10];
// 初始化桶
for (int i = 0; i < buckets.length; i++) {
buckets[i] = new ArrayList<>();
}
// 将数据放入桶中
for (int i = 0; i < str.length; i++) {
int index = str[i] / 10;
buckets[index].add(str[i]);
}
// 分别对每个桶进行排序
for (int i = 0; i < buckets.length; i++) {
buckets[i].sort(null);
}
// 将桶中的数据反向填充到str中
int index = 0;
for (int i = 0; i < buckets.length; i++) {
List<Integer> item = buckets[i];
while (!item.isEmpty()) {
str[index++] = item.remove(0);
}
}
}
概述: 基数排序原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。基数排序的方式可以采用LSD或MSD,LSD的排序方式由键值的最右边开始,而MSD则相反,由键值的最左边开始。
算法步骤
1.从数组中选出最大数和最大数的位数
2.根据位数进行循环
3.每次循环获取数组中每个数的最后一位,然后将其数字放入相应的桶中
4.对桶中的元素进行排序
5.然后将桶中的数反向输出到原数组中
Java代码
public static void sort(int[] str) {
if (str == null || str.length == 0) {
return;
}
// 获取最大值
int maxValue = getMaxVal(str);
// 获取最大位数
int maxDigit = getMaxDigit(maxValue);
radixSort(str, maxDigit);
}
private static void radixSort(int[] str, int maxDigit) {
int mod = 1;
// 创建桶
List<Integer>[] buckets = new ArrayList[10];
// 对桶进行初始化
for (int i = 0; i < buckets.length; i++) {
buckets[i] = new ArrayList<>();
}
// 将相应的尾数的数字放入对应的桶中
for (int i = 0; i < str.length; i++) {
int bucketIndex = (str[i] / mod) % 10;
buckets[bucketIndex].add(str[i]);
}
// 对桶进行排序,分别对每个桶进行排序
for (int i = 0; i < buckets.length; i++) {
buckets[i].sort(null);
}
// 将桶中的元素反向填充到str中
int index = 0;
for (int i = 0; i < buckets.length; i++) {
while (!buckets[i].isEmpty()){
str[index++] = buckets[i].remove(0);
}
}
}
private static int getMaxDigit(int maxValue) {
int max = 0;
while (maxValue > 0) {
max++;
maxValue /= 10;
}
return max;
}
private static int getMaxVal(int[] str) {
int max = str[0];
for (int i = 0; i < str.length; i++) {
max = Math.max(max, str[i]);
}
return max;
}
文章浏览阅读4.3k次,点赞2次,收藏8次。bug的生命周期BUG的生命周期,就是一个BUG被发现到这个BUG被关闭的过程。生命周期中缺陷状态:新建-->指派-->已解决-->待验-->关闭发现BUG-->提交BUG-->指派BUG-->研发确认BUG-->研发去修复BUG-->回归验证BUG-->是否通过验证-->关闭BUG如果待验的BUG在验证时没有解决好,我们需要重新打开--指派—已解决—待验,循环这个过程。中间其他状态:拒绝、延期等_bug生命周期流程图
文章浏览阅读5.3k次,点赞3次,收藏18次。Pandas对行/列求和_pandas对具体列求和
文章浏览阅读1.9w次,点赞32次,收藏228次。做个小结。_visio画用例图
文章浏览阅读2.2k次。在网上看到的恶搞程序员的图片,实在是搞笑。看一次笑一次!程序猿的十年他不是乞丐,请尊称他为程序猿。对,他就是程序猿!其实,你们看到的不是僵尸,他们都是苦逼的程序猿!这不是恶搞的,是一个真实的故事!看他的拐杖,其实也挺可怜的!不知是不是敲代码敲多了,把脚敲颓了!_程序员的道路
文章浏览阅读42次。NetworkingCalling Web Service Methods from Script 为了简化Web Services方法调用,客户端代理的设计被改变了,它在方法调用和回调函数设置方面提供了强大的灵活性。 下面的例子展示了CTP版本中Web Services方法的客户端调用,以及回调函数的使用方式。第一个例子展示了在CTP版本中Web ..._.net6 applicationservices
文章浏览阅读1.1w次,点赞42次,收藏178次。Socket(套接字)是计算机网络编程中的一种抽象概念,它提供了在网络上进行通信的接口。通过使用 Socket,可以在不同计算机之间建立连接,并进行数据的传输和交换。通过 Socket,客户端可以与服务器建立连接并发送请求,服务器接收请求并返回响应。通过 Socket,可以在多个用户之间实现实时的文字、音频或视频通信。可以使用 Socket 在不同计算机之间传输文件,如上传和下载文件。可通过 Socket 在远程计算机上执行指令或操作。_socket编程
文章浏览阅读626次。自己的IT发展方向。1.做T型进化,横向做语言(java、python)的扩展,纵向主要是算法、模式、计算机原理。2.多系统的学习,WINDOW和LINUX的基本操作及维护。3.尽量做产品,少做项目,提高自己的竞争力。4.外语学习,日语是工作方面,英语是学习方面。坚持做自己喜欢的事。_it以后的几个方向
文章浏览阅读392次。对于二叉排序树,下面的说法 ___是正确的。(华南理工大学 2006年)设备驱动程序在读写磁盘数据时一般釆用下列哪种I/O方式?(中国科学院大学 2018)下列___交换技术是独占信道工作方式。(中南大学 2006年)命中率高且电路实现简单的Cache 与内存映射方式是___映射方式。(中国科学院大学 2015)_命中率高且电路实现简单的cache内存映射方式
文章浏览阅读3.2k次。可能是没有异常处理,只需要加上throws Exception就解决问题了。_unhandled exceptions: java.lang.instantiationexception, java.lang.illegalacc
文章浏览阅读1.5k次。webView.setWebViewClient(new WebViewClient(){ @Override public boolean shouldOverrideUrlLoading(WebView view, String url) { try{ if(url.startsWith("baidumap://")){ Intent _error_unsupported_scheme
文章浏览阅读66次。Embed (一)、基本语法: embed src=url 说明:embed可以用来插入各种多媒体,格式可以是 Midi、Wav、AIFF、AU、MP3等等, Netscape及新版的IE 都支持。url为音频或视频文件及其路径,可以是相对路径或绝对路径。 示例:<embed src="your.mid"> (二)、属性设置: 1、自动播放...
文章浏览阅读330次。PHP -- 文件包含、文件上传漏洞PHP -- 文件包含、文件上传漏洞文件包含文件引入漏洞,是由一个动态页面编译时引入另一个文件的操作。文件引入本身是没有问题,它是用于统一页面风格,减少代码冗余的一种技术。但是在特定的场景下就会形成漏洞jsp:include指令和include动作,其中include动作用于引入动态文件php:include(),include_once(),require()..._php文件上传4漏洞