排序算法二(归并排序、快速排序、希尔排序)


作者:xcbeyond
疯狂源自梦想,技术成就辉煌!微信公众号:《程序猿技术大咖》号主,专注后端开发多年,拥有丰富的研发经验,乐于技术输出、分享,现阶段从事微服务架构项目的研发工作,涉及架构设计、技术选型、业务研发等工作。对于Java、微服务、数据库、Docker有深入了解,并有大量的调优经验。 






   
一、归并排序:(MergeSort)

   将数组分成两半,先对每一半分别排序,然后把有序的两半归并(merge)为一个有序的数组。
  • 1

如:【38,16,27,39,12,27】
在这里插入图片描述






















Java代码:

package 排序算法;
 
import java.util.Arrays;
 
/**
 * 归并排序
 * @author xcbeyond
 * @date 2012-6-21 上午11:33:15
 */
public class mergeSort {
	public static void main(String[] args) {
		int a[] ={13,15,37,89,60,39,12,109,56,72} ;
		mergeSort(a,0,a.length-1);
		
		System.out.println(Arrays.toString(a));
	}
	/**
	 * 归并排序
	 * @param array
	 * @param first 数组起始下标
	 * @param last 数组末尾下标
	 */
	public static void mergeSort(int[] array,int first,int last) {
		if(first<last) {
			int mid = (first+last)/2;
			mergeSort(array,first,mid);
			mergeSort(array,mid+1,last);
			merge(array,first,mid,last);
		}
	}
	private static void merge(int[] array, int first, int mid, int last) {
		int[] tempArray = new int[array.length];
		int first1 = first;
		int last1 = mid;
		int first2 = mid + 1;
		int last2 = last;
		
		int index  = first;
		
		while((first1<=last1) && (first2 <= last2)) {
			if(array[first1]<array[first2]) {
				tempArray[index] = array[first1];
				first1 ++ ;
			}
			else {
				tempArray[index] = array[first2];
				first2 ++ ;
			}
			index++;
		}
		
		while(first1<=last1) {
			tempArray[index] = array[first1];
			first1++;
			index++;
		}
		while(first2<=last2) {
			tempArray[index] = array[first2];
			first2++;
			index++;
		}
		
		for (index = first; index <= last; index++) {
			array[index] = tempArray[index];
		}
		
	}
	
}

二、快速排序:(quickSort)

  在当前无序区R[1..H]中任取一个数据元素作为比较的"基准"(不妨记为X),用此基准将当前无序区划分为左右两个较小的无序区:R[1..I-1]和R[I+1..H],且左边的无序子区中数据元素均小于等于基准元素,右边的无序子区中数据元素均大于等于基准元素,而基准X则位于最终排序的位置上,即R[1..I-1]≤X.Key≤R[I+1..H](1≤I≤H),当R[1..I-1]和R[I+1..H]均非空时,分别对它们进行上述的划分过程,直至所有无序子区中的数据元素均已排序为止。
  • 1





排序过程:
初始关键字 [49 38 65 97 76 13 27 49]
一趟排序之后 [27 38 13] 49 [76 97 65 49]
二趟排序之后 [13] 27 [38] 49 [49 65]76 [97]
三趟排序之后 13 27 38 49 49 [65]76 97
最后的排序结果 13 27 38 49 49 65 76 97

程序代码:

package 排序算法;
 
import java.util.Arrays;
 
public class QuickSort {
	public static void main(String[] args) {
		int a[] ={13,15,37,89,60,39,12,109,56,72} ;
		quickSort(a,0,a.length-1);
		
		System.out.println(Arrays.toString(a));
	}
	/**
	 * 快速排序
	 * @param array
	 * @param first
	 * @param last
	 */
	public static void quickSort(int[] array,int first,int last) {
		int pIndex ;
		if(first<last) {
			pIndex = partition(array,first,last);//“基准”值位置
			
			quickSort(array,first,pIndex-1);
			quickSort(array,pIndex+1,last);
		}
	}
	/**
	 * 一次划分,找到基准的位置
	 * @param array
	 * @param first
	 * @param last
	 * @return  基准的位置
	 */
	private static int partition(int[] array,int first,int last) {
		int p =array[first];
		
		while(first<last) {
			while(first<last && array[last]>=p)
				last--;
			array[first] = array[last];
			
			while(first<last && array[first]<=p)
				first++;
			array[last] = array[first];
		}
		array[first] = p;
		return first;
	}
	
}

三、希尔排序:(shellSort)

  先将要排序的一组数按某个增量d(n/2,n为要排序数的个数)分成若干组,每组中记录的下标相差d.对每组中全部元素进行直接插入排序,然后再用一个较小的增量(d/2)对它进行分组,在每组中再进行直接插入排序。当增量减到1时,进行直接插入排序后,排序完成。
  • 1

排序过程:

待排序序列:39,80,76,41,13,29,50,78,30,11,100,7,41,86

取步长d分别为5,3,1

d=5 39,80,76,41,13,29,50,78,30,11,100,7,41,86

        |-------------------------------|-----------------------------|

                |------------------------------|------------------------------|

                        |-----------------------------|------------------------------|

                                 |----------------------------|------------------------------|

                                          |-------------------------------|

各自序列分别为:{39,29,100}{80,50,7}{76,78,41}{41,30,86}{13,11}

对每个自序列进行直接插入排序,顺序调入各个自序列对应排序元素,得到第一趟排序结果:

d=3 29,7,41,30,11,39,50,76,41,13,100,80,78,86

         |-----------------|-----------------|-----------------|------------------|

                 |----------------|------------------|-----------------|------------------|

                        |------------------|-----------------|-------------------|
  • 1
  • 2
  • 3
  • 4
  • 5

各自序列分别为:{29,30,50,13,78}{7,11,76,100,86}{41,39,41,80}。对每个自序列进行直接插入排序,顺序调入各个自序列对应排序元素,得到第二趟排序结果:

d=1 13,7,39,29,11,41,30,76,41,50,86,80,78,100

此时,序列基本“有序”,对其直接进行插入排序,得到最终结果:

7,11,13,29,30,39,41,41,50,76,78,80,86,100

Java程序代码:

package 排序算法;
 
import java.util.Arrays;
 
/**
 * 希尔排序:有步长的直接插入排序
 * @author xcbeyond
 * @date 2012-7-8 上午11:27:32
 */
public class ShellSort {
	public static void main(String[] args) {
		int a[] ={13,15,37,89,60,39,12,109,56,72} ;
		shellSort(a);
		
		System.out.println(Arrays.toString(a));
	}
	
	public static void shellSort(int[] array){
		int temp; 
		int d =array.length;//步长
		while(true){ 
			d= d/2; 
		
			for(int i=0;i<d;i++){ 
				for(int j=i+d;j<array.length;j+=d){ 
					int k=j-d; 
					temp=array[j]; 
					for(;k>=0&&temp<array[k];k-=d){ 
						array[k+d]=array[k]; 
					} 
					array[k+d]=temp; 
				} 
			} 
		if(d==1) 
			break; 
 
		}
	}

      }