一、排序算法
1. 冒泡排序(Bubble Sort) 【算法|排序算法和二分查找】冒泡排序是一种简单的排序算法。它重复地走访过要排序的元素列,依次比较两个相邻的元素,如果顺序(如从大到小、首字母从Z到A)错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换,也就是说该元素列已经排序完成。
1.1 原理
- 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
- 对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
- 针对所有的元素重复以上的步骤,除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
文章图片
1.3 代码实现
public static void sort(int[] arr){
//外层循环比较轮数
for (int i=0;
iarr[j+1]){//相邻元素比较,若逆序则交换(升序为左大于右,降序反之)
int temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
}
2. 选择排序(Selection Sort) 首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。
2.1 原理
第一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后再从剩余的未排序元素中寻找到最小(大)元素,然后放到已排序的序列的末尾。以此类推,直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。
2.2 动画演示
文章图片
2.3 代码实现
public static void selectionSort(int[] arr){
for(int i = 0;
i < arr.length - 1;
i++){
// 交换次数
// 先假设每次循环时,最小数的索引为i
int minIndex = i;
// 每一个元素都和剩下的未排序的元素比较
for(int j = i + 1;
j < arr.length;
j++){
if(arr[j] < arr[minIndex]){//寻找最小数
minIndex = j;
//将最小数的索引保存
}
}//经过一轮循环,就可以找出第一个最小值的索引,然后把最小值放到i的位置
swap(arr, i, minIndex);
}
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
3.快速排序 快速排序(Quicksort)是对冒泡排序算法的一种改进。
快速排序的基本思想:通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。
3.1 原理
快速排序使用分治法来把一个串(list)分为两个子串(sub-lists)。具体算法描述如下:
- 从数列中挑出一个元素,称为 “基准”(pivot);
- 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作;
- 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。
文章图片
3.3 代码实现
public static void sort(int[] arr,int L,int R){
//如果起始下标别结束下标大,则结束程序
if(L>R)
return;
//定义基准数
int pivot = arr[L];
//定义变量left指向起始值
int left = L;
//定义变量right指向末尾值
int right= R;
//开始比较
while(left != right){//left和right没有相遇,说明可以继续检索//先由right从右往左检索,如果检索到比基准值小,则停下
//换言之,如果检索到比基准值大或者相等,则继续检索
while(arr[right]>=pivot && left
二、查找算法 1. 二分查找 二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。
1.1 原理
- 首先,从数组的中间元素开始搜索,如果该元素正好是目标元素,则搜索过程结束,否则执行下一步。
- 如果目标元素大于/小于中间元素,则在数组大于/小于中间元素的那一半区域查找,然后重复步骤1的操作。
- 如果某一步数组为空,则表示找不到目标元素。
public static int binarySearch(Integer[] srcArray, int des) {
//定义初始最小、最大索引
int start = 0;
int end = srcArray.length - 1;
//确保不会出现重复查找,越界
while (start <= end) {
//计算出中间索引值
int middle = (end + start)>>>1 ;
//防止溢出
if (des == srcArray[middle]) {
return middle;
//判断下限
} else if (des < srcArray[middle]) {
end = middle - 1;
//判断上限
} else {
start = middle + 1;
}
}
//若没有,则返回-1
return -1;
}
推荐阅读
- COMS 4771 分析
- 《LeetCode算法全集》|LeetCode 146. LRU 缓存
- 蓝桥真题|【蓝桥真题六】三十块的蓝桥省赛模拟真题,做的大一都直呼上当(文末PDF原题)
- 《力扣周赛题解》|【解题报告】力扣 第 277 场周赛
- 蓝桥杯|2020蓝桥杯校模拟赛真题解析
- 图论|【图论-最小生成树】洛谷官方题单刷题总结
- 算法|ACC Acwing4376. 数圈圈
- Leetcode|21. 合并两个有序链表
- c语言|数据结构3--深入了解单向链表的实现