八大经典排序算法--Java实现

八大排序算法–Java实现

插入排序

• 基本思想：每步将一个待排序的纪录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。
• 算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。
• 代码：

public static void insertionSort(int[] array){
				int tmp;
				for(int i=1;i<array.length;i++){
					tmp = array[i];  //将当前位置的数给tmp
					int j = i;
					for(;j>0&&array[j-1]>tmp;j--){
					/*
					往右移，腾出左边的位置,
					array[j-1]>tmp:大于号是升序排列，小于号是降序排列
				   */
					array[j] = array[j-1];
			}
			//将当前位置的数插入到合适的位置
			array[j] = tmp;
		}
	}

冒泡排序

• 基本思想：持续比较相邻的元素。如果第一个比第二个大，就交换他们两个。直到没有任何一对数字需要比较。
• 冒泡排序最好的时间复杂度为O(n)。冒泡排序的最坏时间复杂度为O(n^2)。因此冒泡排序总的平均时间复杂度为O(n^2)。
• 算法适用于少量数据的排序，是稳定的排序方法。
• 代码：

   public static void bubbleSort(int[] array){
  	int tmp;
  	boolean flag = false;  //设置是否发生交换的标志
  	for(int i = array.length-1;i >= 0;i--){
  		for(int j=0;j<i;j++){          //每一轮都找到一个最大的数放在右边
  			if(array[j]>array[j+1]){
  				tmp = array[j];
  				array[j] = array[j+1];
  				array[j+1] = tmp;
  				flag = true;   //发生了交换
  			}
  		}
  		if(!flag)  break;   //这一轮循环没有发生交换，说明排序已经完成，退出循环
  	}
  }
  

选择排序

• 基本思想：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
• 选择排序是不稳定的排序方法。时间复杂度 O(n^2)。
• 代码：

  public static void selectSort(int[] array){
  		for(int i = 0;i<array.length-1;i++){
  			int	min = array[i];
  			int minindex = i;
  			for(int j = i;j<array.length;j++){
  				if(array[j]<min){  //选择当前最小的数
  					min = array[j];
  					minindex = j;
  				}
  			}
  			if(i != minindex){ //若i不是当前元素最小的，则和找到的那个元素交换
  				array[minindex] = array[i];
  				array[i] = min;
  			}
  		}
  	}
  

希尔排序

• 基本思想：先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-1…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。
• 在使用增量dk的一趟排序之后，对于每一个i，我们都有a[i]<=a[i+dk],即所有相隔dk的元素都被排序。
• 如图：增量序列为5，3，1，每一趟排序之后，相隔对应增量的元素都被排序了。当增量为1时，数组元素全部被排序。
  
• 希尔排序不稳定，时间复杂度 平均时间 O(nlogn) 最差时间O(n^2)
• 代码：

  public static void shellSort(int[] array){
  			int j;
  			for(int gap = array.length/2; gap>0; gap /= 2){
  				//定义一个增长序列，即分割数组的增量,d1=N/2   dk=(d(k-1))/2
  				for(int i = gap; i<array.length;i++){
  					int tmp = array[i];
  					for( j =i; j>=gap&&tmp<array[j-gap]; j -= gap){
  						//将相距为Dk的元素进行排序
  						array[j] = array[j-gap];
  					}
  					array[j] = tmp;
  				}
  			}
  		}
  

堆排序

• 预备知识：

二叉堆是完全二元树（二叉树）或者是近似完全二元树（二叉树）。
二叉堆有两种：最大堆和最小堆。
大根堆：父结点的键值总是大于或等于任何一个子节点的键值；
小根堆：父结点的键值总是小于或等于任何一个子节点的键值。
二叉堆一般用数组来表示。例如，根节点在数组中的位置是0，第n个位置的子节点分别在2n+1和 2n+2。因此，第0个位置的子节点在1和2，1的子节点在3和4。以此类推。这种存储方式便於寻找父节点和子节点。
例如初始要排序的数组为：49, 38, 65, 97, 76, 13, 27, 49
构造成大根堆之后的数组为：97 76 65 49 49 13 27 38
实际树形结构如图（最大堆）：

• 堆排序基本思想：在排序过程中，将R[l..n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系【参见二叉树的顺序存储结构】，在当前无序区中选择关键字最大(或最小)的记录。堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征，使得在当前无序区中选取最大(或最小)关键字的记录变得简单。

• 堆排序是一种选择排序,其时间复杂度为O(nlogn)。堆排序是不稳定的

• 代码：

  /*
  		 * 堆排序
  		 * 调整最大堆，交换根元素和最后一个元素。
  		 * 参数说明：
  		 *     a -- 待排序的数组
  		 */
  		public static void heapSort(int[] a) {
  		    int n = a.length;
  		    int i,tmp;
  		    // 从(n/2-1) --> 0逐次遍历。遍历之后，得到的数组实际上是一个(最大)二叉堆。
  		    for (i = n / 2 - 1; i >= 0; i--)
  		        maxHeapDown(a, i, n-1);
  		    // 从最后一个元素开始对序列进行调整，不断的缩小调整的范围直到第一个元素
  		    for (i = n - 1; i > 0; i--) {
  		        // 交换a[0]和a[i]。交换后，a[i]是a[0...i]中最大的。
  		        tmp = a[0];
  		        a[0] = a[i];
  		        a[i] = tmp;
  		        // 调整a[0...i-1]，使得a[0...i-1]仍然是一个最大堆。
  		        // 即，保证a[i-1]是a[0...i-1]中的最大值。
  		        maxHeapDown(a, 0, i-1);
  		    }
  		}
  		/*
  		 * 注：数组实现的堆中，第N个节点的左孩子的索引值是(2N+1)，右孩子的索引是(2N+2)。
  		 *     其中，N为数组下标索引值，如数组中第1个数对应的N为0。
  		 *
  		 * 参数说明：
  		 *     a -- 待排序的数组
  		 *     start -- 被下调节点的起始位置(一般为0，表示从第1个开始)
  		 *     end   -- 截至范围(一般为数组中最后一个元素的索引)
  		 */
  		public static void maxHeapDown(int[] a, int start, int end) {
  		    int c = start;            // 当前(current)节点的位置
  		    int l = 2*c + 1;        // 左(left)孩子的位置
  		    int tmp = a[c];            // 当前(current)节点的大小
  		    for (; l <= end; c=l,l=2*l+1) {
  		        // "l"是左孩子，"l+1"是右孩子
  		        if ( l < end && a[l] < a[l+1])
  		            l++;        // 左右两孩子中选择较大者，即m_heap[l+1] 
  		        if (tmp >= a[l])
  		            break;        // 调整结束
  		        else {            // 交换值
  		            a[c] = a[l];
  		            a[l]= tmp;
  		        }
  		    }
  		}
  

归并排序

• 归并排序的原理

  • 将待排序的数组分成前后两个部分，再递归的将前半部分数据和后半部分的数据各自归并排序，得到的两部分数据，然后使用merge合并算法（算法见代码）将两部分算法合并到一起。
    例如：如果N=1；那么只有一个数据要排序，N=2，只需要调用merge函数将前后合并，N=4，……….. 也就是将一个很多数据的数组分成前后两部分，然后不断递归归并排序，再合并，最后返回有序的数组。

• 归并排序的时间复杂度

  • 归并排序的最好、最坏和平均时间复杂度都是O(nlogn)，而空间复杂度是O(n)，比较次数介于(nlogn)/2和(nlogn)-n+1，赋值操作的次数是(2nlogn)。因此可以看出，归并排序算法比较占用内存，但却是效率高且稳定的排序算法。

• 代码：

  public class MergeSort {
  		private static void mergeSort(int[] array,int[] tmp,int left,int right){
  			if(left<right){
  				int center = ( left + right ) / 2;//取数组的中点
  				mergeSort(array,tmp,left,center);//归并排序数组的前半部分
  				mergeSort(array,tmp,center+1,right);//归并排序数组的后半部分
  				merge(array,tmp,left,center+1,right);//将数组的前后半部分合并
  			}
  		}
  		/*
  		 * 超简单的合并函数
  		 */
  		private static void merge(int[] array, int[] tmp, int leftPos, int rightPos, int rightEnd) {
  			// TODO Auto-generated method stub
  			int leftEnd = rightPos - 1;
  			int tmpPos = leftPos;
  			int numElements = rightEnd - leftPos + 1;
  			while(leftPos <= leftEnd && rightPos <= rightEnd){
  				if(array[leftPos]<=array[rightPos]){
  					tmp[tmpPos++] = array[leftPos++];
  				}else{
  					tmp[tmpPos++] = array[rightPos++];
  				}
  			}
  			while(leftPos <= leftEnd){
  				tmp[tmpPos++] = array[leftPos++];
  			}
  			while(rightPos <= rightEnd){
  				tmp[tmpPos++] = array[rightPos++];
  			}
  			for(int i=0;i<numElements;i++,rightEnd--){
  				array[rightEnd] = tmp[rightEnd];
  			}
  		}
  		public static void mergeSort(int[] array){
  			int[] tmp = new int[array.length];//声明一个用来合并的数组
  			mergeSort(array,tmp,0,array.length-1);//调用排序函数，传入数字的起点和终点
  		}
  	}
  

快速排序

• 快速排序原理：

  1. 如果数组S中元素是0或者1，则返回；
  2. 区数组S中任一元素v，称之为枢纽元；
  3. 将S-{v}（S中剩余的元素）划分成连个不相交的集合：S1={S-{v}|x<=v}和S2={S-{v}|x>=v};
  4. 返回{quicksort(s1)}后跟v，继而返回{quicksort(S2)}。

• 选取枢纽元（三数中值分割法）

• 一般的做法是使用左端、右端和中心位置上的三个元素的中值作为基元。
  分割策略：
  在分割阶段吧所有小元素移到数组的左边，大元素移到数组右边。，大小是相对于枢纽元素而言的。
  当i在j的左边时，将i右移，移过哪些小于枢纽元的元素，并将j左移，已过那些大于枢纽元的元素，当i和j停止时，i指向一个大元素，而j指向一个小元素，如果i在j的左边，那么将这两个元素交换，其效果是把一个大元素推向右边，而把小元素推向左边。效果如图：

• 快速排序平均时间复杂度为O(nlogn)，最坏情况为O(n^2)，n越大，速度越快。不是稳定的排序算法。
• 代码：

  /*
  	 * 快速排序
  	 * 两个方向，左边的i下标一直往右走，当a[i] <= a[center_index]，
  	 * 其中center_index是中枢元素的数组下标，而右边的j下标一直往左走，当a[j] > a[center_index]
  	 * 如果i和j都走不动了，i <= j, 交换a[i]和a[j],重复上面的过程，直到i>j
  	 * 交换a[j]和a[center_index]，完成一趟快速排序
  	 * 枢轴采用三数中值分割法可以优化
  	 */
  	//递归快速排序
  	public static void quickSort(int a[]){
  	    qSort(a, 0, a.length - 1);
  	}
  	//递归排序，利用两路划分
  	public static void qSort(int a[],int low,int high){
  	    int pivot = 0;
  	    if(low < high){
  	        //将数组一分为二
  	        pivot = partition(a,low,high);
  	        //对第一部分进行递归排序
  	        qSort(a,low,pivot);
  	        //对第二部分进行递归排序
  	        qSort(a,pivot + 1,high);
  	    }
  	}
  	//partition函数，实现三数中值分割法
  	public static int partition(int a[],int low,int high){
  	    int pivotkey = a[low];   //选取第一个元素为枢轴记录
  	    while(low < high){
  	        //将比枢轴记录小的交换到低端
  	        while(low < high && a[high] >= pivotkey){
  	            high--;
  	        }
  	        //采用替换而不是交换的方式操作
  	        a[low] = a[high];
  	        //将比枢轴记录大的交换到高端
  	        while(low < high && a[low] <= pivotkey){
  	            low++;
  	        }
  	        a[high] = a[low];
  	    }
  	    //枢纽所在位置赋值
  	    a[low] = pivotkey;
  	    //返回枢纽所在的位置
  	    return low;
  	}
  

桶式排序

• 桶式排序不再是一种基于比较的排序方法，它是一种比较巧妙的排序方式，但这种排序方式需要待排序的序列满足以下两个特征：
  待排序列所有的值处于一个可枚举的范围之类；
  待排序列所在的这个可枚举的范围不应该太大，否则排序开销太大。

• 排序的具体步骤如下：

  (1)对于这个可枚举范围构建一个buckets数组，用于记录“落入”每个桶中元素的个数；
  (2)将（1）中得到的buckets数组重新进行计算，按如下公式重新计算：

buckets[i] = buckets[i] +buckets[i-1] (其中1<=i<buckets.length);

• 桶式排序是一种非常优秀的排序算法，时间效率极高，它只要通过2轮遍历：第1轮遍历待排数据，统计每个待排数据“落入”各桶中的个数，第2轮遍历buckets用于重新计算buckets中元素的值，2轮遍历后就可以得到每个待排数据在有序序列中的位置，然后将各个数据项依次放入指定位置即可。
• 桶式排序的空间开销较大，它需要两个数组，第1个buckets数组用于记录“落入”各桶中元素的个数，进而保存各元素在有序序列中的位置，第2个数组用于缓存待排数据.
• 桶式排序是稳定的。如果待排序数据的范围在0~k之间，那么它的时间复杂度是O(k+n)的.
• 但是它的限制多，比如它只能排整形数组。而且当k较大，而数组长度n较小，即k>>n时，辅助数组C[k+1]的空间消耗较大。当数组为整形，且k和n接近时, 可以用此方法排序。
• 代码实现：

  //min的值为0，max的值为待排序数组中最大值+1
  public static void bucketSort(int[] data, int min, int max) {  
  	        // 缓存数组  
  	        int[] tmp = new int[data.length];  
  	        // buckets用于记录待排序元素的信息  
  	        // buckets数组定义了max-min个桶  
  	        int[] buckets = new int[max - min];  
  	        // 计算每个元素在序列出现的次数  
  	        for (int i = 0; i < data.length; i++) {  
  	            buckets[data[i] - min]++;  
  	        }  
  	        // 计算“落入”各桶内的元素在有序序列中的位置  
  	        for (int i = 1; i < max - min; i++) {  
  	            buckets[i] = buckets[i] + buckets[i - 1];  
  	        }  
  	        // 将data中的元素完全复制到tmp数组中  
  	        System.arraycopy(data, 0, tmp, 0, data.length);  
  	        // 根据buckets数组中的信息将待排序列的各元素放入相应位置  
  	        for (int k = data.length - 1; k >= 0; k--) {  
  	            data[--buckets[tmp[k] - min]] = tmp[k];  
  	        }  
  	    }  
  

总结

• 下面是一个总的表格，大致总结了我们常见的所有的排序算法的特点。

  排序法	平均时间	最差情形	稳定度	额外空间	备注
  冒泡	O(n2)	O(n2)	稳定	O(1)	n小时较好
  选择	O(n2)	O(n2)	不稳定	O(1)	n小时较好
  插入	O(n2)	O(n2)	稳定	O(1)	大部分已排序时较好
  Shell(希尔)	O(nlogn)	O(ns)	不稳定	O(1)	s是所选分组
  快速	O(nlogn)	O(n2)	不稳定	O(nlogn)	n大时较好
  归并	O(nlogn)	O(nlogn)	稳定	O(1)	n大时较好
  堆	O(nlogn)	O(nlogn)	不稳定	O(1)	n大时较好
  桶式	O(k+n)	O(k+n)	稳定	O(1)	只能排整形数组

• 性能测试

  

往期精彩文章

• Spring整合hibernate和Struts
• Sping入门
• Java必读电子书_文档教程_高清PDF下载
• 深入理解Java中的List、Set与Map集合
• 由浅入深，解析Java Servlet开发以及工作的过程
• Java Map使用多个映射案例
• 推荐7款好用的终端工具
• 8张图 带你理解Java内存区域
• Java八大基本数据类型详解