Java 中常见的排序算法
Java 中常见的排序算法
其实小编是不太想写关于Java的相关文章，因为是这个编程语言实在是会用的人太多了，网上的博文数不胜数，没必要在重复造轮子了，但是虽然java这门语言会用的人很多，但是会用、掌握、熟练、和精通可不是闹着玩的，想要达到精通的级别，小编敢说，一个正规的开发公司能过达到精通java的开发人员屈指可数，所以小编这里就跳过关于java哪些简单的API 、语法，直接给大家介绍一些相对提升能力，并且不是那么基础的知识，说不定以后面试就会用到，尤其是排序，真的，不晓得为啥都喜欢在面试的时候出排序的题，实际大数据开发中真正手写排序的还真不多，我想可能是各个面试官想要看到的是，各个应聘者是否能够get到排序算法的精髓吧。
好了，每次写博客都要废话一堆，自我检讨，但是不想改变，接下来小编介绍几种创建的排序算法以及他们的Java实现。
1. 冒泡排序
原理：从第一个元素开始，和它相邻的比较，如果前面一个元素大于后面一个元素，就把他们互换位置。
原理图：
代码实现：
public static void main(String[] args) {
int arr[] = { 15, 16, 145, 91, 9, 5, 0 };
int temp1=0;
for(int i=0;i<arr.length-1;i++){ //控制循环次数：arr.length-1
for(int j=0;j<arr.length-i-1;j++){ //控制比较次数：arr.length-i-1
if(arr[j]>arr[j+1]){
temp1=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp1;
}
}
}
}
增强版冒泡排序：
public static void main(String[] args) {
int arr[] = { 1,0,2,3,4,5,6,7,8 };
int temp1;
for(int i=0;i<arr.length-1;i++){ //控制循环次数：arr.length-1
boolean flag=true; //判断内层循环是否执行
for(int j=0;j<arr.length-i-1;j++){ //控制比较次数：arr.length-i-1
if(arr[j]>arr[j+1]){
temp1=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp1;
flag=false;
}
}
if(flag){ //如果内层循环的if一次都没有执行，说明已经排序结束
break;
}
}
2.选择排序
原理：从第一个位置开始，将他与后面的所有元素比较，如果前面大于后面的，就交换位置。
原理图：
代码实现：
public static void main(String[] args) {
int arr[] = { 45,15,48,9,3,65,22 };
for(int i=0;i<arr.length-1;i++){ //控制位置，从第一个位置开始，到倒数第二个位置
for(int j=i+1;j<arr.length;j++){ //当前位置的下一个位置开始，与后面的所有比较
if(arr[i]>arr[j]){
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
}
3. 插入排序
原理：从第二个元素位置开始，将他与他之前的元素比较，如果比之前的元素小，就将他插入到，那个元素的前面。
原理图：
代码实现：
public static void main(String[] args) {
int arr[] = { 45, 15, 48, 9, 3, 65, 22 };
// 插入排序
int temp1;
for (int i = 1; i < arr.length; i++) { //从第二个数开始，一直到最后一个数
for (int j = 0; j < i; j++) { //i之前的所有数，全部比较
if (arr[i] < arr[j]) {
temp1 = arr[i];
for (int k = i; k > j; k--) { //将前面的数据把后面的覆盖，从j开始，一直到i
arr[k] = arr[k - 1];
}
arr[j] = temp1;
}
}
}
4. 快速排序
原理：先选取一个基准点，作用：基准点左侧小于基准点的数据 基准点右侧放的数据都是大于基准点的数据。基准点：最常用的基准点选第一个,最终一个大数组不停的进行查分 拆分的最终结果每个数组只有一个元素。
原理图：
解释：大循环中有两个循环，一个是从右往左，找比基准点小的，一个是从左往右找比基准点大的（找到之后，与基准点交换位置）。最终大循环，在left>=right时结束。
（2） 快排拆分：
解释：使用递归的方式，将数组左右两边一次次拆分，直到left>=right时，递归结束。
代码实现：
public class QuickSort {
public static void main(String[] args) {
int arr[]= {2,7,1,2,8,1,3,9,415,189,123};
sort(arr,0,arr.length-1);
System.out.println(Arrays.toString(arr));
}
public static void sort(int [] arr,int left ,int right) {
//递归的出口，当左侧==右侧
if(left>=right) {
return;
}
//获取基准点
int point=getPoint(arr,left,right);
//左边排序(递归)
sort(arr,left,point-1);
//右边排序(递归)
sort(arr,point+1,right);
}
public static int getPoint(int [] arr,int left ,int right) {
int key=arr[left];
while(left<right) {
//从右向左循环,只要右边的比基准点大，就继续循序
while(key<=arr[right]&&left<right) {
//每循环一次，right的索引向左移一个
right--;
}
//交换基准点的位置
arr[left]=arr[right];
//从左向右循环,只要左边的比基准点小，就继续循序
while(arr[left]<=key&&left<right) {
left++;
}
//交换基准点
arr[right]=arr[left];
}
//最后给基准点赋值
arr[left]=key;
return left;
}
}
注意：了解快速排序有助于了解MR的map-reduce过程，因为在MRmap阶段环形缓冲区满了之后，会将数据溢写到文件中，这个过程中就是使用了快速排序。
5. 计数排序
原理：对一个已有数组进行排序，那么就新建一个数组，数组长度为数组中元素的最大值+1。并把已有数组中的元素，对应上新建数组的下标，放入里面，新建数组的元素为，已有数组中元素的出现次数。
原理图：
解释：新创建一个数组，长度为需要排序的数组的最大值+1，遍历数组，将数组中的值分别找到新数组的索引，将索引处的元素+1，最后，遍历输出新数组的下标（只输出相应的值>0的下标，并且值为多少就输出几次）。
代码实现：
public class CountSort {
public static void main(String[] args) {
int arr[]= {2,7,1,2,8,1,3,9,415,189,123};
sort(arr,415);
System.out.println(Arrays.toString(arr));
}
public static void sort(int arr[],int max) {
int index=0;
int newarr[]=new int [max+1];
for(int i=0;i<arr.length;i++) {
newarr[arr[i]]++;
}
for(int i=0;i<newarr.length;i++) {
if(newarr[i]!=0) {
for(int j=0;j<newarr[i];j++) {
arr[index++]=i;
}
}
}
}
}
注意：了解计数排序，有助于了解hbase的布隆过滤器，布隆过滤器的特点就是，我说没有就没有，我说有不一定有（有一定的误判率）。
6. 归并排序（两路）
原理：针对多个有序的数据集进行排序。（时间复杂度：n*logN）
归并排序有两个阶段：
一个是归：将一个数据集拆分到每一个小的数据集只有一个元素。
实现一个数据集的归：
public static void chai(int arr[],int first,int last,int [] newarr) {
if(first>=last) {
return;
}
//找中间点
int mid=(first+last)/2;
//左边归
chai(arr,first,mid,newarr);
//右侧拆
chai(arr,mid+1,last,newarr);
//拆完之后并
meger(arr,first,last,mid,newarr);
}
一个是并：将两个有序的数据集，合并成为一个有序的大数据集。
实现两个有序数据集的并：
public int[] bing(int arr1[], int arr2[]) {
//创建一个最终结果的数组：长度为arr1和arr2长度之和
int newarr[] = new int[arr1.length+arr2.length];
//新数组的元素标记
int index=0;
//记录arr1和arr2的下标
int arr1_index=0;
int arr2_index=0;
//只要有一个数组，遍历结束，就停止循环
while(arr1_index<arr1.length&&arr2_index<arr2.length) {
//进行判断，将数据存储在新数组中
if(arr1[arr1_index]<arr2[arr2_index]) {
newarr[index++]=arr1[arr1_index++];
}else {
newarr[index++]=arr2[arr2_index++];
}
}
//可能是arr1没有遍历完全
while(arr1_index<arr1.length) {
newarr[index++]=arr1[arr1_index++];
}
//可能是arr2没有遍历完全
while(arr2_index<arr2.length) {
newarr[index++]=arr2[arr2_index++];
}
return newarr;
}
完整代码实现：
public class bingSort {
public static void main(String[] args) {
int arr[]= {1,8,7,6,11,2,4};
int newarr[]=new int[arr.length];
System.out.println(Arrays.toString(arr));
chai(arr,0,arr.length-1,newarr);
System.out.println(Arrays.toString(newarr));
}
//归
public static void chai(int arr[],int first,int last,int [] newarr) {
if(first>=last) {
return;
}
//找中间点
int mid=(first+last)/2;
//左边归
chai(arr,first,mid,newarr);
//右侧拆
chai(arr,mid+1,last,newarr);
//拆完之后并
meger(arr,first,last,mid,newarr);
}
/**
* 并
* @param arr 原数组
* @param first 开始位置
* @param last 结束位置
* @param mid 中间位置
* @param newarr 存放最终结果的数组
*/
public static void meger(int arr[],int first,int last,int mid,int [] newarr) {
//第一个数据集的起始下标
int arr1_start=first;
//第一个数据集的终止下标
int arr1_end=mid;
//第二个数据集的起始下标
int arr2_start=mid+1;
//第二个数据集的终止下标
int arr2_end=last;
int index=0;
while(arr1_start<=arr1_end&&arr2_start<=arr2_end) {
if(arr[arr1_start]<arr[arr2_start]) {
newarr[index++]=arr[arr1_start++];
}else {
newarr[index++]=arr[arr2_start++];
}
}
while(arr1_start<=arr1_end) {
newarr[index++]=arr[arr1_start++];
}
while(arr2_start<=arr2_end) {
newarr[index++]=arr[arr2_start++];
}
/**
* 因为归并排序，需要使用两个有序的数据集，而arr一开始时无需的，所有每一次归并的时候
* 需要将归并好之后的那一段数据集，赋值到arr中，使之后的归并仍然有序
*/
//赋值的循环的次数，是本次归并的元素的个数
for(int i=0;i<index;i++) {
//每次赋值的时候，是从first开始
arr[first+i]=newarr[i];
}
}
}
注意：在MR程序中，其中有两个阶段使用到了归并，一个是在缓冲区溢写小文件时，最后会将多个小文件归并成一个大文件，另一个则是在reduce拉去map处理的数据到本地是会生成很多小文件，此时也会做一次归并。
7. 二分法查找数据
原理：在已经排好序的基础上，将数组元素折半查找。
原理图：
代码实现：
public static void main(String[] args) {
int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8 };
// 二分法查数据
int num = new Scanner(System.in).nextInt(); //查找的数
int start = 0;
int end = arr.length - 1;
int middle = (start + end) / 2;
while (true) {
//如果end<start说明全部找完也没有找到
if (end < start) {
System.out.println(num + "不在此数组中");
break;
}
if (arr[middle] > num) {
end = middle - 1;
} else if (arr[middle] < num) {
start = middle + 1;
} else {
System.out.println("这个数的索引下标为" + middle);
break;
}
middle = (start + end) / 2;
}
试试
评论暂时关闭