java实现、配图解，附源码十大经典排序算法( 四 ) _排序算法

般的初次取序列的一半为增量，以后每次减半，直到增量为1 。

文章插图

文章插图

6.2 动图演示

文章插图

6.3实例展示

 1 import java.util.Arrays; 2 public class ShellSort { 3public static void main(String[] args) { 4int[] array = new int[]{15,63,97,12,235,66}; 56 //实现增量变化 7for (int gap = array.length/2;gap>0;gap/=2){ 89for (int i=gap;i<array.length;i++){10 11for (int j=i-gap;j>=0;j-=gap){12if (array[j]>array[j+gap]){13int temp = 0;14temp = array[j];15array[j] = array[j+gap];16array[j+gap] = temp;17}18}19}20}21System.out.println(Arrays.toString(array));22}23 }

文章插图

文章插图

7.归并排序归并排序（Merge Sort）是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
7.1实现原理

第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置
第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置重复步骤3直到某一指针超出序列尾将另一序列剩下的所有元素直接复制到合并序列尾

文章插图

我们需要将两个已经有序的子序列合并成一个有序序列，比如上图最后一次合并，将[2,4,5,6]和[1,3,7,8]已经有序的子序列合并最终序列[1,2,3,4,5,6,7,8]

文章插图

7.2 动图演示

文章插图

7.3实例展示

文章插图

 1 import java.util.Arrays; 2 public class MSort { 3public static void main(String[] args) { 4int[] array = new int[]{15,63,97,12,235,66}; 5//临时数组 6int[] temp = new int[array.length]; 7sort(array,0,array.length-1,temp); 8System.out.println(Arrays.toString(array)); 9 10}11public static void sort(int[] array,int left,int right,int[] temp){12if (left<right){13 14 //求出中间值15int mid = (left+right)/2;16 17 //向左边分解18sort(array,left,mid,temp);19 //向右边分解20sort(array,mid+1,right,temp);21 //合并数据22sum(array,left,right,mid,temp);23}24}25/**26* 合并元素27* @param array28* @param left29* @param right30* @param mid31* @param temp32*/33public static void sum(int[] array,int left,int right,int mid,int[] temp){34int i = left;35int j = mid+1;36 37 //指向临时数组下标38int t = 0;39 40 //开始循环比较左右两遍数组元素比较41while (i<=mid && j<=right){42 43if (array[i]<=array[j]){44temp[t] = array[i];45t++;46i++;47}else {48temp[t] = array[j];49t++;50j++;51}52}53 54 //把剩余的元素直接存放在临时数组中55while(i<=mid){56temp[t] = array[i];57t++;58i++;59}60while (j<=right){61temp[t] = array[j];62t++;63j++;64}65 66 //临时数组中的元素拷贝至原数组中67int tempIndex = left;68int k = 0;69while (tempIndex<=right){70array[tempIndex] = temp[k];71k++;72tempIndex++;73}74}75 }

文章插图

排序结果展示：

文章插图

8.计数排序计数排序是一个非基于比较的排序算法，该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法。当然这是一种牺牲空间换取时间的做法，而且当O(k)>O(n*log(n))的时候其效率反而不如基于比较的排序（基于比较的排序的时间复杂度在理论上的下限是O(n*log(n)), 如归并排序，堆排序）