排序算法二（归并排序、快速排序、希尔排序）

关注
发布于: 2020 年 08 月 18 日
一、归并排序1、算法思想﻿
将数组分成两半，先对每一半分别排序，然后把有序的两半归并（merge）为一个有序的数组。
﻿
如：【38,16,27,39,12,27】
﻿
﻿
2、算法代码﻿
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];
		}
		
	}
	
}
﻿
﻿
二、快速排序1、算法思想﻿
在当前无序区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]均非空时，分别对它们进行上述的划分过程，直至所有无序子区中的数据元素均已排序为止。
﻿
   排序过程：
﻿
       初始关键字 ［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
﻿
2、算法代码
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;
	}
	
}
﻿
﻿
三、希尔排序1、算法思想﻿
先将要排序的一组数按某个增量d（n/2,n为要排序数的个数）分成若干组，每组中记录的下标相差d.对每组中全部元素进行直接插入排序，然后再用一个较小的增量（d/2）对它进行分组，在每组中再进行直接插入排序。当增量减到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
﻿
             |-----------------|-----------------|-----------------|------------------|
﻿
                     |----------------|------------------|-----------------|------------------|
﻿
                            |------------------|-----------------|-------------------|
﻿
各自序列分别为：｛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
﻿
2、算法代码﻿
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; 
 
		}
	}
}
﻿
﻿
﻿
发布于: 2020 年 08 月 18 日阅读数: 56
原文链接:【http://xie.infoq.cn/article/ebb41eab6090af933aec4e99b】。文章转载请联系作者。
xcbeyond

关注
不为别的，只为技术沉淀、分享。 2019.06.20 加入
公众号：程序猿技术大咖知识星球：技术那些事
发布
暂无评论
创作场景

排序算法二（归并排序、快速排序、希尔排序）

一、归并排序

1、算法思想

2、算法代码

二、快速排序

1、算法思想

2、算法代码

三、希尔排序

1、算法思想

2、算法代码

xcbeyond

评论
