归并排序与计数排序

博主主页: 码农派大星.

数据结构专栏:Java数据结构

数据库专栏:MySQL数据库

JavaEE专栏:JavaEE

关注博主带你了解更多数据结构知识

1.归并排序

1.递归实现归并排序

归并排序

//归并排序public static void mergeSort(int[] array) {mergeSortFun(array,0,array.length-1);
return array;}public static void mergeSortFun(int[] array,int left,int right) {if(left >= right) {// >return;}int mid = (right+left) / 2;mergeSortFun(array,left,mid);mergeSortFun(array,mid+1,right);//合并merge(array,left,mid,right);}private static void merge(int[] array,int left,int mid,int right) {int[] tmp = new int[right-left+1];int k = 0;int s1 = left;int e1 = mid;int s2 = mid+1;int e2 = right;while (s1 <= e1 && s2 <= e2) {if(array[s1] <= array[s2]) {tmp[k++] = array[s1++];}else {tmp[k++] = array[s2++];}}while (s1 <= e1) {tmp[k++] = array[s1++];}while (s2 <= e2) {tmp[k++] = array[s2++];}//走到这里 相当于tmp数组 当中 所有的元素 都有序了//接下来把tmp数组的内容 拷贝到array数组当中for (int i = 0; i < k; i++) {array[i+left] = tmp[i];}}

2.非递归归并排序

 //非递归归并排序public static void mergeSortNor(int[] array) {int gap = 1;while (gap < array.length) {for (int i = 0; i < array.length; i = i + 2*gap) {int left = i;int mid = left+gap - 1;if(mid >= array.length) {mid = array.length-1;}int right = mid+gap;if(right >= array.length) {right = array.length-1;}merge(array,left,mid,right);}gap *= 2;}
return array;}

3.归并排序总结

1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序题。

2. 时间复杂度：O(N*logN)

3. 空间复杂度：O(N)

4. 稳定性：稳定

2.计数排序

思想：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。

操作步骤：

1. 统计相同元素出现次数

2. 根据统计的结果将序列回收到原来的序列中

计数排序

1.计数排序实现

public static void countSort(int[] array) {//1. 遍历数组 求最大值 和 最小值int maxVal = array[0];int minVal = array[0];for (int i = 0; i < array.length; i++) {if(maxVal < array[i]) {maxVal = array[i];}if(minVal > array[i]) {minVal = array[i];}}//2. 定义count数组int[] count = new int[maxVal - minVal + 1];//3. 遍历array数组 把值 放入 计数数组当中for (int i = 0; i < array.length; i++) {int val = array[i];//98count[val - minVal]++;}//4. 以上3步完成之后，计数数组 已经存好了对应的数据// 接下来 开始遍历 计数数组int index = 0;//array的下标for (int i = 0; i < count.length; i++) {while (count[i] > 0) {array[index] = i+minVal;index++;count[i]--;}}
return array;}