算法(Algorithm)是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令
1.前言
数据结构和算法是一个软件开发者的基本功,如果把数据结构类比成内功,那么算法就是心法.算法在计算机科学中的地位至关重要,相当于程序设计的灵魂,现在很多大公司都会考察面试者的算法掌握程度
2.目录
目录
3.算法的相关介绍
3.1.算法的特征
1.又穷性:有限个步骤后终止
2.确切性:有确切的含义
3.输入项:有0个或多个输入
4.输出项:有一个或多个输出
5.可行性:可以在有限时间内完成
3.2.算法的评定
1.时间复杂度:执行算法所需要的计算的工作量,问题规模n的函数f(n)的时间复杂度记做O(f(n))
2.空间复杂度:执行算法所需要消耗的内存空间
3.正确性:算法优劣的最重要标准
4.可读性:阅读,理解的容易程度
5.健壮性:对不合理数据输入的反应和处理能力
3.3.算法设计的方法
1.递推法:按照一定的规律来计算序列中的每个项
2.递归法:函数直接或间接的调用自身,必须有一个递归结束条件
3.穷举法:列出它所有的可能情况,尝试所有情况暴力破解
4.贪心算法:分级处理,每一步贪心选择获取局部最优解,最后得到文字最优解
5.分治法:把问题分成两个或更多相同或类似的子问题,直到子问题可以被简单求解,原问题即为子问题解的合并
6.动态规划:用于求解包含重叠子问题的最优化问题,思想为将原问题分解为相似的子问题,然后通过子问题求出原问题的解
7.迭代法:每次执行重复的指令,将变量的原值推导出新值,常见的如二分法
8.分支界限法:把全部的可行解不断分割为越来越小的子集,为每个子集内的解的值计算上界和下界,不在范围内的不再拆分,直至找到可行解,该可行解不大于任何自己的界限
9.回溯法:按照深度优先搜索的策略,从根开始探索,判断各探索结点相关问题的解,不包含则回溯到根,直至搜索出问题的最优解
3.4.八大排序算法
3.4.1.冒泡排序
冒泡排序(Bubble Sort):重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来,直到没有再需要交换,也就是说该数列已经排序完成.
/**
* 冒泡排序,时间复杂度为O(n^2)
* @param arr 排序数组
*/
public static void bobbleSort(int[] arr) {
// 是否进行过交换,默认为false
boolean flag = false;
// 需要遍历的次数
for (int i = 0; i < arr.length - 1; i++) {
//遍历数组中的值,来比较
for (int j = 0; j < arr.length - 1 - i; j++) {
// 如果后面的数比前面的数要大,则进行交换
if (arr[j] > arr[j+1]) {
flag = true;
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
// 如果flag==false,表示没有进行过交换,直接退出即可(优化)
// 即已经排好了序
if (!flag) {
break;
} else {
// 要将flag重置,进行下一次的判断
flag = false;
}
}
System.out.println(Arrays.toString(arr));
}
3.4.2.选择排序
选择排序(Selection Sort):从待排序的数据元素中取出最小(大)的存放在起始位置,再从剩余的数据元素中取出最小(大)放在其后,依次进行,直至全部排序
/**
* 选择排序 时间复杂度O(n^2)
* @param arr 排序数组
*/
public static void selectSort(int[] arr) {
for (int i = 0; i < arr.length-1; i++) {
// 记录最小值的下标,从0开始
int minIndex = i;
// 记录最小值,假设是a[0]开始
int minValue = arr[i];
// 从i后开始循环
for (int j = i+1; j < arr.length; j++) {
// 如果最小的值,并不是a[i],重置minIndex和minValue
if (minValue > arr[j]){
// 获取最小值,和最小值的下标
minValue = arr[j];
minIndex = j;
}
}
// 将最小的值放在a[i],比较并进行交换
if (minIndex != i) {
// 把a[0]第一个值先放在a[minIndex]处
arr[minIndex] = arr[i];
// 把保存下来的最小值回填到a[0],即找到了全局的最小值
arr[i] = minValue;
}
}
System.out.println(Arrays.toString(arr));
}
3.4.3.插入排序
插入排序(Insertion Sort):每次从待排序元素中取出第一个元素,将它与前面的有序元素作比较,插入合适的位置,至成为有序表
/**
* 插入排序
* @param array 带排序数组
*/
public static void insertSort(int[] array) {
for (int i = 1; i < array.length; i++) {
// 定义待插入的数 从第二个数开始和第一个数进行比较
int insertValue = array[I];
// 第一个数的下标
int insertIndex = i -1;
//与前面的数作比较
while (insertIndex >= 0 && insertValue < array[insertIndex]) {
array[insertIndex+1] = array[insertIndex];
insertIndex--;
}
// 将新数据插入
if (insertIndex + 1 != i){
array[insertIndex + 1] = insertValue;
}
}
System.out.println(Arrays.toString(array));
}
3.4.4.希尔排序
希尔排序(Shell's Sort):优化的插入排序,防止插入值过小,导致数组频繁移动效率低下.它将数据按下标进行增量分组,然后对每组进行插入排序,然后减小增量,再次排序,直至为1,排序完成(先分组排序,将每组的小值移动到前面,防止后面排序频繁移动)
希尔排序.png
/**
* 希尔排序
* @param arr 排序数组
*/
public static void shellSort(int[] arr){
for (int step = arr.length / 2; step > 0 ; step = step / 2) {
// 每次缩小遍历次数增量 每次折半,缩小增量
for (int i = step; i < arr.length; i++) {
// 从step个位置,逐步对其所在的元素进行插入排序
// 假定最小值是arr[i]
int minValue = arr[i];
// 记录i
int minIndex = i;
//1.minIdx-gap >=0 确保插入的位置不会越界
//2.minVal < arr[minIdx-gap] 找到了待插入的数
while (minIndex - step >= 0 && minValue < arr[minIndex - step]){
// 同插入排序
arr[minIndex] = arr[minIndex - step];
minIndex = minIndex - step;
}
arr[minIndex] = minValue;
}
}
System.out.println(Arrays.toString(arr));
}
3.4.5.快速排序
快速排序(Quick Sort):通过一趟排序将要排序的数据分割成独立的两个部分,其中一部分的数据比另一部分的数据都要小,然后在按照此方法对这两部分数据进行快速排序,整个排序通过递归实现,以此达到整个数据排列有序(适用于数据量较大且线性结构数据)
/**
* 快速排序
* @param arr 排序数组
* @param left 数组的开始索引
* @param right 数组的结束索引
*/
public static void quickSort(int[] arr,int left,int right) {
int start = left;
int end = right;
//排序的基点
int pivot = arr[(left + right) / 2];
//左右两端扫描
while (start <= end) {
//从前向后寻找大于基点的值
while (pivot > arr[start]) start++;
//从后向前寻找小于基点的值
while (pivot < arr[end]) end--;
//交换值进行下一次循环
if (start <= end) {
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}
}
//从左边将剩余的树再排序
if (end > left) quickSort(arr,left,end);
//从有边将剩余的树再排序
if (start < right) quickSort(arr,start,right);
System.out.println(Arrays.toString(arr));
}
3.4.6.归并排序
归并排序(Merge Sort):该算法采用分治法,先使每个子序列有序,再使有序的子序列合并，得到完全有序的序列(适用于数据量大且有较多重复数据的场景,需要空间较大)
分治法归并排序.png
/**
* 归并排序
* @param arr 原数组
* @param left 左下标
* @param right 右下标
* @param temp 临时数组
*/
public static void mergeSort(int[] arr,int left,int right,int[] temp){
if (left < right){
int mid =( left + right )/2;
// 向左递归
mergeSort(arr,left,mid,temp);
// 向右递归
mergeSort(arr,mid+1,right,temp);
// 合并
merge(arr,left,mid,right,temp);
}
}
/**
* 合并
* @param arr 需要排序的原始数组
* @param left 左边有序序列的初始索引
* @param mid 中间索引
* @param right 右边有序序列的初始索引
* @param temp 临时数组
*/
public static void merge(int[] arr,int left,int mid,int right,int[] temp) {
// 初始化i,左边有序序列的初始索引
int i = left;
// 初始化j,右边有序序列的初始索引
int j = mid + 1;
// 临时数组的索引
int t = 0;
//1.将左右两边的有序数据按照规则填充到temp中,直到左右两边的有序序列有一边处理完为止
while (i <= mid && j <= right) {
//如果左边的有序序列当前的元素小于右边有序序列当前的元素
if (arr[i] <= arr[j]) {
// 将左边有序序列的元素填充到temp中
temp[t] = arr[i];
t = t + 1;
i = i + 1;
} else {
//如果右边的有序序列当前的元素小于左边有序序列当前的元素
// 将右边有序序列的元素填充到temp中
temp[t] = arr[j];
t = t + 1;
j = j + 1;
}
}
//2.把剩余的数据的一边依次全部填充到temp中
while (i <= mid){
// 左边的有效数据还有剩余就全部填充到temp中
temp[t] = arr[i];
t = t + 1;
i = i + 1;
}
while (j <= right){
// 右边的有效数据还有剩余就全部填充到temp中
temp[t] = arr[j];
t = t + 1;
j = j + 1;
}
//3.将temp数组的元素拷贝到arr中,每次都要拷贝
// t要清空
t = 0;
int tempLeft = left;
while (tempLeft <= right){
arr[tempLeft] = temp[t];
t = t + 1;
tempLeft = tempLeft + 1;
}
}
3.4.7.基数排序
基数排序(Radix Sort):将所有待比较的数统一为同样的数位长度,数位较短的数前补零.然后从最低位开始,依次进行一次排序.这样从最低位排序一直到最高位排序完成后数列就成了有序序列了.
基数排序.png
/**
* 基数排序
* @param arr 待排序数组
*/
public static void radixSort(int[] arr) {
// 获取最大的数是多少位
int digit = getMaxDigit(arr);
for (int i = 0; i < digit; i++) {
// 执行 digit 次 bucketSort 排序即可
bucketSort(arr, i);
}
System.out.println(Arrays.toString(arr));
}
private static int getMaxDigit(int[] arr) {
// 默认只有一位
int digit = 1;
// 十进制每多一位，代表其值大了10倍
int base = 10;
for (int i : arr) {
while (i >= base) {
digit ++;
base = base * 10;
}
}
return digit;
}
private static void bucketSort(int[] arr, int digit) {
int base = (int) Math.pow(10, digit);
// init buckets
ArrayList<ArrayList<Integer>> buckets = new ArrayList<>();
// 只有0~9这十个数，所以准备十个桶
for (int i = 0; i < 10; i++) {
buckets.add(new ArrayList<Integer>());
}
// sort
for (int i : arr) {
int index = i / base % 10;
buckets.get(index).add(i);
}
// output: copy back to arr
int index = 0;
for (ArrayList<Integer> bucket : buckets) {
for (int i : bucket) {
arr[index++] = i;
}
}
}
3.4.8.堆排序
堆排序(Heap Sort):利用堆这种数据结构所设计的一种排序算法,堆是一个近似完全二叉树的结构,将待排序的序列构造成一个大顶堆.此时整个序列的最大值就是堆顶的根节点,把它和末尾的元素进行交换.此时末尾的元素就成了最大值.然后将剩余n-1个元素重新构造成一个堆.如此反复执行就能到一个有序的序列
排序数调整为最大堆.png
/**
* 堆排序
* @param array 待排序数组
*/
public static void heapSort(int[] array){
int len = array.length;
//建堆 len/2-1最后一个非叶子节点
for(int i = len / 2 - 1; i >= 0;i--){
maxHeapAdjust(array,i,len-1);
}
//排序,根节点和最后一个节点交换
//换完以后，取走根，重新建堆
//len-1 最后一个节点
for(int i=len-1;i>0;i--){
int temp=array[0];
array[0]=array[I];
array[i]=temp;
maxHeapAdjust(array,0,i-1);
}
System.out.println(Arrays.toString(array));
}
/**
* 堆调整
* @param array 待排序数组
* @param start 起始点
* @param end 结束点
*/
private static void maxHeapAdjust(int array[],int start,int end){
//父亲的位置
int father = start;
//儿子的位置
int son = father * 2 + 1;
//如果子节点下标在可以调整的范围内就一直调整下去
while(son <= end){
//如果没有右孩子就不用比,有的话,比较两个儿子，选择最大的出来
if(son + 1 <= end && array[son] < array[son+1]){
son++;
}
//和父节点比大小
if(array[father] > array[son]){
return;
} else {//父亲比儿子小，就要对整个子树进行调整
int temp = array[son];
array[son] = array[father];
array[father] = temp;
//递归下一层
father = son;
son = father * 2 + 1;
}
}
}
3.5.其它算法
3.5.1.KMP算法
KMP算法:改进的字符串匹配算法,利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。
- 一个序列A任意删除若干个字符得到新序列B，则A叫做B的子序列
- 最长公共子序列(Longest Common Subsequence,lcs):两个序列X和Y的公共子序列中,长度最长的那个,定义为X和Y的最长公共子序列
- 应用于DNA对比(亲自鉴定),非法数据过滤(不良言论,岛国爱情动作片)
3.6.2.加密算法
3.6.2.1.SHA-1算法
安全哈希算法(Secure Hash Algorithm SHA-1):是一个用来进行数字签名的算法,对于长度小于2^64位的消息,SHA1会产生一个160位的消息摘要,这个消息摘要可以用来验证数据的完整性
- android中会通过签名的sha1来绑定三方服务
3.6.2.2.RSA算法
RSA公钥加密算法:是1977年由罗纳德·李维斯特(Ron Rivest),阿迪·萨莫尔(Adi Shamir)和伦纳德·阿德曼(Leonard Adleman)一起提出的.1987年7月首次在美国公布,当时他们三人都在麻省理工学院工作实习.RSA就是他们三人姓氏开头字母拼在一起组成的
- RSA属于应用最为广泛的
非对称加密算法,其基本安全原理是建立在大素数因子很难分解的基础上,属于分组密码体制.
3.6.2.3.AES算法
AES技术是一种
对称的分组加密技术,使用128位分组加密数据,提供比WEP/TKIPS的RC4算法更高的加密强度
- DES算法的替代者,最流行的加密算法之一
- 是一种区块加密技术,把原文分成128位每块的数据,对每块单独进行加密
- 实际中,一般是通过RSA加密AES的密钥,传输到接收方,接收方解密得到AES密钥,然后发送方和接收方用AES密钥来通信
4.总结
本章主要是算法的基本知识的讲解,学习了常用的八大排序算法,也了解了部分在计算机科学中使用的高级算法.算法是一个十分复杂的技术,一般只需要了解基础的算法及其原理,感兴趣的话可以做些深入的研究
八大排序算法地址:github
网友评论