查找和排序是最基础也是最重要的两类算法,熟练地掌握这两类算法,并能对这些算法的性能进行分析很重要,这两类算法中主要包括二分查找、快速排序、归并排序等等。我们先来了解查找算法!
顺序查找:

顺序查找又称线性查找。它的过程为:从查找表的最后一个元素开始逐个与给定关键字比较,若某个记录的关键字和给定值比较相等,则查找成功,否则,若直至第一个记录,其关键字和给定值比较都不等,则表明表中没有所查记录查找不成功,它的缺点是效率低下。
二分查找:
二分查找又称折半查找,对于有序表来说,它的优点是比较次数少,查找速度快,平均性能好。

二分查找的基本思想是将n个元素分成大致相等的两部分,取a[n/2]与目标值x做比较,如果x=a[n/2],则找到x,算法中止,如果x小于a[n/2],则只要在数组a的左半部分继续搜索x,如果x>a[n/2],则只要在数组a的右半部搜索x.代码实现如下:
public int funBinSearch(int[] array,int data){ int low=0; int high=array
.length-1; while(low<=high){ int mid=(low+high)/2; if(data==array[mid]){ return
mid; }else if(data<array[mid]){ high=mid-1; }else{ low=mid+1; } } return -1; }

排序是计算机程序设计中的一种重要操作,它的功能是将一个数据元素(或记录)的任意序列,重新排列成一个按关键字有序的序列。下面主要对一些常见的排序算法做介绍.先来了解冒泡排序!
冒泡排序:

冒泡排序的基本思想是:设排序序列的记录个数为n,进行n-1次遍历,每次遍历从开始位置依次往后比较前后相邻元素,这样较大的元素往后移,n-1次遍历结束后,序列有序。
需要注意的是,如果在某次遍历中没有发生交换,那么就不必进行下次遍历,因为序列已经有序。代码实现如下:
public void bubbleSort(int[] array){ boolean flag=true; for(int i=0;i<array
.length-1&&flag;i++){ //如果在某次遍历中没有发生交换,那么就不必再进行下次遍历,因为序列已经有序 flag=false; for(int
j=0;j<array.length-1-i;j++){ if(array[j]>array[j+1]){ int temp=array[i]; array
[j]=array[j+1]; array[j+1]=temp; flag=true; } } } }
简单选择排序:
简单选择排序的思想是:设排序序列的记录个数为n,每一轮进行n-2-i次选择,每次在n-i-1(i =
1,2,…,n-1)个记录中选择关键字最小的记录作为有效序列中的第i个记录。代码实现如下:
public void selectionSort(int[] array){ for(int i=0;i<array.length-1;i++){ int
mink=i;//每次从未排序数组中找到最小值的坐标 for(int j=i+1;j<array.length;j++){ if(array[j]<array
[mink]){ mink=j; } }//将最小值放在最前面 if(mink!=i){ int temp=array[mink]; array[mink]=
array[i]; array[i]=temp; } } }
直接插入排序:
直接插入的思想是:是将一个记录插入到已排好序的有序表中,从而得到一个新的、记录数增1的有序表。
public void insertSort(int[] array){ int j; for(int i=1;i<array.length;i++){
int temp=array[i]; j=i-1; while(j>-1&&temp<array[j]){ array[j+1]=array[j]; j--;
}array[j+1]=temp; } }
希尔排序:

希尔排序又称“缩小增量排序”,它是基于直接插入排序的以下两点性质而提出的一种改进:(1)
直接插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率。(2) 直接插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位。
快速简单理解——希尔排序 <https://blog.csdn.net/lemisi/article/details/77075018>.
public void xier(int[] arrays,int n){ int gap=n/2; for(;gap>0;gap=gap/2){ for(
int i=0;i<n;i++){ int temp=a[i]; int j=i-gap; while(j>=0&&temp<a[j]){
a[j+gap]=a[j]; j=j-gap; } a[j+gap]=temp; } } }
快速排序:

快速排序的主要思想是:在待排序的序列中选择一个称为主元的元素,将数组分为两部分,使得第一部分中的所有元素都小于或等于主元,而第二部分中的所有元素都大于主元,然后对两部分递归地应用快速排序算法。
简单理解 快速排序算法 <https://blog.csdn.net/jinvmen/article/details/47017711>.
public void quickSort(int[] s,int left,int right){ if(1<right){ int
i=left,j=right,temp=s[left];while(i<j){ while(i<j&&s[j]>=temp){
//从右向左找第一个小于temp的数 j--; } if(i<j){ s[i++]=s[j]; } while(i<j&&s[i]<temp){
//从左向右找第一个大于等于temp的数 i++; } if(i<j){ s[j--]=s[i]; } } s[i]=temp;
quickSort(s,left,i-1);//递归调用(分治法) quickSort(s,i+1,right); } }
堆排序:
在介绍堆排序之前首先需要了解堆的定义,n个关键字序列K1,K2,…,Kn称为堆,当且仅当该序列满足如下性质(简称为堆性质):(1) ki <=
k(2i)且 ki <= k(2i+1) (1 ≤ i≤ n/2),当然,这是小根堆,大根堆则换成>=号。
如果将上面满足堆性质的序列看成是一个完全二叉树,则堆的含义表明,完全二叉树中所有的非终端节点的值均不大于(或不小于)其左右孩子节点的值。

堆排序的主要思想是:给定一个待排序序列,首先经过一次调整,将序列构建成一个大顶堆,此时第一个元素是最大的元素,将其和序列的最后一个元素交换,然后对前n-1个元素调整为大顶堆,再将其第一个元素和末尾元素交换,这样最后即可得到有序序列。
堆排序就这么简单 <https://blog.csdn.net/java_3y/article/details/79679568>.
//建堆 //参数:看作是完全二叉树,当前父节点位置,节点总数 public void heapify(int[] arrays,int
currentRootNode,int size){ if(currentRootNode<size){ //左节点和右节点的位置 int left=2
*currentRootNode+1; int right=2*currentRootNode+2; //把当前父节点看成是最大的 int max
=currentRootNode;if(left<size){ //如果比当前根元素要大,记录它的位置 if(arrays[max
]<arrays[left]){max=left; } } if(right<size){ //如果比当前根元素要大,记录它的位置 if(arrays[max
]<arrays[right]){max=right; } } //如果最大的不是根元素位置,那么就交换 if(max!=currentRootNode){
int temp=arrays[max]; arrays[max]=arrays[currentRootNode];
arrays[currentRootNode]=temp;//继续比较,知道完成一次堆建 heapify(arrays,max,arrays.length);
} } }//完成一次建堆,最大值在堆的顶部(根节点) public void maxHeapify(int[] arrays,int size){
//从数组的尾部开始,直到第一个元素(角标为0) for(int i=size-1;i>=0;i--){ heapify(arrays,i,size); } }
for(int i=0;i<arrays.length;i++){ //每次建堆就可以排除一个元素 maxHeapify(arrays,arrays.
length-i); //交换 int temp=arrays[0]; arrays[0]=arrays[arrays.length-1-i]; arrays[
length-1-i]=temp; }
归并排序:
归并排序 (merge sort)
是一类与插入排序、交换排序、选择排序不同的另一种排序方法。归并的含义是将两个或两个以上的有序表合并成一个新的有序表。它是一种稳定的排序,java.util.Arrays类中的sort方法就是使用归并排序的变体来实现的。
“深入理解”—归并排序算法 <https://blog.csdn.net/qq_25827845/article/details/70994874>.
public void mergeSort(int[] arrays){ if(arrays.length>1){ sort(arrays,0
,arrays.length); } }//归并排序 //将两个(或两个以上)有序表合并成一个新的有序表 即把待排序
//序列分为若干子序列,每个子序列是有序的.然后把有序子序列合并为 //整体有序序列 //传入待排序数组,输出有序数组 public int[] sort(
int[] nums,int low,int high){ int mid=(low+high)/2; if(low<high){ //处理左边
sort(nums,low,mid);//处理右边 sort(nums,mid+1,high); //左右归并
merge(nums,low,mid,high); }return nums; } public void merge(int[] nums,int low,
int mid,int high){ //定义一个辅助数组 int[] temp=new int[high-low+1]; int i=low; int
j=mid+1; int k=0; //找出较小值元素放入temp数组中 while(i<=mid&&j<=high){ if
(nums[i]<nums[j]){ temp[k++]=nums[i++]; }else{ temp[k++]=nums[j++]; } } //处理较长部分
while(i<=mid){ temp[k++]=nums[i++]; } while(j<=high){ temp[k++]=nums[j++]; }
//使用temp中的元素覆盖nums中的元素 for(int k2=0;k2<temp.length;K2++){
nums[k2+low]=temp[k2]; } }
更多算法内容可以浏览常见数据结构与算法整理总结(下)
<https://blog.csdn.net/xiaotaiyangzuishuai/article/details/79096774>.