Java 中常见的排序算法(2)

注意：了解快速排序有助于了解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]; } } }