排序_安科网

1. 排序的分类

在介绍有关排序的算法之前，先来介绍与排序相关的基本概念。本节主要介绍排序的基本概念及相关概念。排序：把一个无序的元素序列按照元素的关键字递增或递减排列为有序的序列。

稳定排序和不稳定排序：在排列过程中，如果存在两个关键字相等即ki=kj(1≤i≤n,1≤j≤n,i≠j)，在排序前对应的元素Ei在Ej之前。
内排序和外排序：根据排序过程中，所利用的内存储器和外存储器的情况，将排序分为两类：内部排序和外部排序。
内排序的方法：按照排序过程中采用的策略将排序分为几个大类：插入排序、选择排序、交换排序和归并排序。这些排序方法各有优点和不足，在使用时，可根据具体情况选择比较合适的方法。

排序分类如下所示：

（1）插入排序（直接插入排序、折半插入排序、希尔排序）；

（2）交换排序（冒泡泡排序、快速排序）；

（3）选择排序（直接选择排序、堆排序）；

（4）归并排序；

（5）基数排序。

2. 排序的比较

比较各种排序算法的性能主要是考察各种排序算法的时间复杂度、空间复杂度和稳定性。

3. JAVA实现

（1）插入排序

插入排序的算法思想是：在一个有序的元素序列中，不断地将新元素插入到该已经有序的元素列表中的合适位置，直到所有元素都插入到合适位置则完成排序。

<1> 直接插入排序

直接插入排序的基本思想是：假设前i-1个元素已经有序，将第i个元素的关键字与前i-1个元素的关键字进行比较，找到合适的位置，将第i个元素插入。按照类似的方法，将剩下的元素依次插入到已经有序的序列中，完成插入排序。

示例代码：

/**
 * @author [email protected]
 * 
 *         Time: 2011-8-3 下午12:40:02
 */
public class InsertSort implements Sort {

	/* (non-Javadoc)
	 * @see sort.Sort#sort(int[], java.lang.String)
	 */
	@Override
	public int[] sortArray(int[] data, String sortType) {
		if(data == null || data.length == 0)
			return null;
		if (sortType.equals("asc")) { // 正排序，从小排到大
			// 比较的轮数
			for (int i = 1; i < data.length; i++) {
				// 保证前i+1个数排好序
				int temp = data[i];
				int j;
				for (j = i; j > 0 && data[j - 1] > temp; j--) {
					data[j] = data[j - 1];
				}
				data[j] = temp;
			}
		} else if (sortType.equals("desc")) { // 倒排序，从大排到小
			// 比较的轮数
			for (int i = 1; i < data.length; i++) {
				// 保证前i+1个数排好序
				int temp = data[i];
				int j;
				for (j = i; j > 0 && data[j - 1] < temp; j--) {
					data[j] = data[j - 1];
				}
				data[j] = temp;
			}
		} else {
			System.out.println("您输入的排序类型错误！");
		}
		return data;
	}

}

图直接插入排序过程示意图

<2> 折半插入排序

由于插入排序算法的基本思想是，将待排序元素插入到已经有序的元素序列的正确位置，因此，在查找正确插入位置时，可以采用折半查找的思想寻找插入位置。将这种插入排序称为折半插入排序。

示例代码：

/**
 * @author [email protected]
 *
 * Time: 2011-8-3 下午02:22:23
 */
public class BinInsertSort implements Sort {

	/* (non-Javadoc)
	 * @see sort.Sort#sortArray(int[], java.lang.String)
	 */
	@Override
	public int[] sortArray(int[] data, String sortType) {
		if(data == null || data.length == 0)   
            return null;
		int low = 0,high = 0, mid = 0;
        if (sortType.equals("asc")) { // 正排序，从小排到大   
            // 比较的轮数   
            for (int i = 0; i < data.length -1; i++) {   /* 前i个元素已经有序，从第i+1个元素开始与前i个的有序的关键字比较 */
                // 保证前i+1个数排好序   
                int temp = data[i+1];
                low = 0;
                high = i;
                while(low <= high){                   /*利用折半查找思想寻找当前元素的合适位置 */
                	mid = (low + high) / 2;
                	if(data[mid] > temp) 
                		high = mid - 1;
                	else
                		low = mid + 1;
                }
                int j;   
                for (j = i; j >= low; j--) {           /*移动元素，空出要插入的位置*/
                    data[j+1] = data[j];   
                }
                data[low] = temp;                      /*将当前元素插入合适的位置*/
            }   
        } else if (sortType.equals("desc")) { // 倒排序，从大排到小   
        	// 比较的轮数   
            for (int i = 0; i < data.length -1; i++) {   /* 前i个元素已经有序，从第i+1个元素开始与前i个的有序的关键字比较 */
                // 保证前i+1个数排好序   
                int temp = data[i+1];
                low = 0;
                high = i;
                while(low <= high){                   /*利用折半查找思想寻找当前元素的合适位置 */
                	mid = (low + high) / 2;
                	if(data[mid] < temp) 
                		high = mid - 1;
                	else
                		low = mid + 1;
                }
                int j;   
                for (j = i; j >= low; j--) {           /*移动元素，空出要插入的位置*/
                    data[j+1] = data[j];   
                }
                data[low] = temp;                      /*将当前元素插入合适的位置*/
            }   
        } else {   
            System.out.println("您输入的排序类型错误！");   
        }   
        return data;  
	}

}

<3> 希尔排序

希尔排序也称为缩小增量排序，它的基本思想是：通过将待排序的元素分为若干个子序列，利用直接插入排序思想对子序列进行排序。然后将该子序列缩小，接着对子序列进行直接插入排序。按照这种思想，直到所有的元素都按照关键字有序排列。

示例代码：

/**
 * @author [email protected]
 *
 * Time: 2011-8-3 下午04:52:35
 */
public class ShellInsertSort implements Sort {

	private int[] delta = {5,3,1};
	/* (non-Javadoc)
	 * @see sort.Sort#sortArray(int[], java.lang.String)
	 */
	@Override
	public int[] sortArray(int[] data, String sortType) {
		/*希尔排序，每次调用算法ShellInsert,delta是存放增量的数组*/
		if(data == null || data.length == 0)   
            return null;
		if(sortType.equals("asc")){
			for(int i=0; i<delta.length; i++){
				shellInsertASC(data,delta[i]);
			}
		}
		else if(sortType.equals("desc")){
			for(int i=0; i<delta.length; i++){
				shellInsertDESC(data,delta[i]);
			}
		}
		else{
			System.out.println("您输入的排序类型错误！");
		}
		return sortData;
	}
	
	private int[] shellInsertASC(int[] data, int c){
		for(int i=c; i<data.length; i++){         /*将距离为c的元素作为一个子序列进行排序*/
			if(data[i] < data[i-c]){                /*如果后者小于前者，则需要移动元素*/
				int temp = data[i];
				int j;
				for(j=i-c; j>=0 && data[j] > temp; j=j-c){
					data[j+c] = data[j];
				}
				data[j+c] = temp;                   /*依次将元素插入到正确的位置*/
			}
		}
		return data;
	}
	
	private int[] shellInsertDESC(int[] data, int c){
		for(int i=c; i<data.length; i++){         /*将距离为c的元素作为一个子序列进行排序*/
			if(data[i] > data[i-c]){                /*如果前者小于后者，则需要移动元素*/
				int temp = data[i];
				int j;
				for(j=i-c; j>=0 && data[j] < temp; j=j-c){
					data[j+c] = data[j];
				}
				data[j+c] = temp;                   /*依次将元素插入到正确的位置*/
			}
		}
		return data;
	}

}

图希尔排序过程示意图

（2）交换排序

交换排序的基本思想是：通过依次交换逆序的元素实现排序。

<1> 冒泡排序

冒泡排序的基本思想是：从第一个元素开始，依次比较两个相邻的元素，如果两个元素逆序，则进行交换，即如果L.data[i].key>L.data[i+1].key，则交换L.data[i]与L.data[i+1]。假设元素序列中有

n个待比较的元素，在第一趟排序结束，就会将元素序列中关键字最大的元素移到序列的末尾，即第n个位置。在第二趟排序结束，就会将关键字次大的元素移动到第n-1个位置。

/**
 * @author [email protected]
 * 
 *         Time: 2011-8-3 下午06:38:15
 */
public class BubbleSort implements Sort {

	/*
	 * (non-Javadoc)
	 * 
	 * @see sort.Sort#sortArray(int[], java.lang.String)
	 */
	@Override
	public int[] sortArray(int[] data, String sortType) {
		if (sortType.equals("asc")) { // 正排序，从小排到大
			// 比较的轮数
			for (int i = 1; i < data.length; i++) {
				// 将相邻两个数进行比较，较大的数往后冒泡
				for (int j = 0; j < data.length - i; j++) {
					if (data[j] > data[j + 1]) {
						// 交换相邻两个数
						swap(data, j, j + 1);
					}
				}
			}
		} else if (sortType.equals("desc")) { // 倒排序，从大排到小
			// 比较的轮数
			for (int i = 1; i < data.length; i++) {
				// 将相邻两个数进行比较，较大的数往后冒泡
				for (int j = 0; j < data.length - i; j++) {
					if (data[j] < data[j + 1]) {
						// 交换相邻两个数
						swap(data, j, j + 1);
					}
				}
			}
		} else {
			System.out.println("您输入的排序类型错误！");
		}
		return data;
	}

	private void swap(int[] data, int x, int y) {
		int temp = data[x];
		data[x] = data[y];
		data[y] = temp;
	}

}

图冒泡排序示意图

<2> 快速排序

快速排序算法是冒泡排序的一种改进，与冒泡排序类似，只是快速排序是将元素序列中的关键字与指定的元素进行比较，将逆序的两个元素进行交换。快速排序的基本算法思想是：设待排序的元素序列的个数为n，分别存放在数组data[1…n]中，令第一元素作为枢轴元素，即将a[1]作为参考元素，令pivot=a[1]。

/**
 * @author [email protected]
 * 
 *         Time: 2011-8-4 下午12:47:34
 */
public class QuickSort implements Sort {

	/*
	 * (non-Javadoc)
	 * 
	 * @see sort.Sort#sortArray(int[], java.lang.String)
	 */
	@Override
	public int[] sortArray(int[] data, String sortType) {
		if (sortType.equals("asc")) { // 正排序，从小排到大
			qsort_asc(data, 0, data.length - 1);
		} else if (sortType.equals("desc")) { // 倒排序，从大排到小
			qsort_desc(data, 0, data.length - 1);
		} else {
			System.out.println("您输入的排序类型错误！");
		}
		return data;
	}

	/**
	 * 
	 * 快速排序的具体实现，排正序
	 * 
	 * @param data
	 * @param low
	 * @param high
	 */

	private void qsort_asc(int data[], int low, int high) {
		int i, j, x;
		if (low < high) { // 这个条件用来结束递归
			i = low;
			j = high;
			x = data[i];
			while (i < j) {
				while (i < j && data[j] > x) {
					j--; // 从右向左找第一个小于x的数
				}
				if (i < j) {
					data[i] = data[j];
					i++;
				}
				while (i < j && data[i] < x) {
					i++; // 从左向右找第一个大于x的数
				}
				if (i < j) {
					data[j] = data[i];
					j--;
				}
			}
			data[i] = x;
			qsort_asc(data, low, i - 1);
			qsort_asc(data, i + 1, high);
		}
	}

	/**
	 * 
	 * 快速排序的具体实现，排倒序
	 * 
	 * @param data
	 * @param low
	 * @param high
	 */

	private void qsort_desc(int data[], int low, int high) {

		int i, j, x;
		if (low < high) { // 这个条件用来结束递归
			i = low;
			j = high;
			x = data[i];
			while (i < j) {
				while (i < j && data[j] < x) {
					j--; // 从右向左找第一个小于x的数
				}
				if (i < j) {
					data[i] = data[j];
					i++;
				}
				while (i < j && data[i] > x) {
					i++; // 从左向右找第一个大于x的数
				}
				if (i < j) {
					data[j] = data[i];
					j--;
				}
			}
			data[i] = x;
			qsort_desc(data, low, i - 1);
			qsort_desc(data, i + 1, high);
		}
	}
}

图快速排序过程示意图

（3）选择排序

选择排序的基本思想是：从待排序的元素序列中选择关键字最小或最大的元素，将其放在已排序元素序列的最前面或最后面，其余的元素构成新的待排序元素序列，并从待排序元素序列中选择关键字最小的元素，将其放在已排序元素序列的最前面或最后面。

<1> 简单选择排序

简单选择排序的基本思想是：假设待排序的元素序列有n个，第一趟排序经过n-1次比较，从n个元素序列中选择关键字最小的元素，并将其放在元素序列的最前面即第一个位置。第二趟排序从剩余的n-1个元素中，经过n-2次比较选择关键字最小的元素，将其放在第二个位置。

/**
 * @author [email protected]
 * 
 *         Time: 2011-8-4 下午04:48:52
 */
public class SelectSort implements Sort {

	/*
	 * (non-Javadoc)
	 * 
	 * @see sort.Sort#sortArray(int[], java.lang.String)
	 */
	@Override
	public int[] sortArray(int[] data, String sortType) {
		if (sortType.equals("asc")) { // 正排序，从小排到大
			int index;
			for (int i = 1; i < data.length; i++) {
				index = 0;
				for (int j = 1; j <= data.length - i; j++) {
					if (data[j] > data[index]) {
						index = j;
					}
				}
				// 交换在位置data.length-i和index(最大值)两个数
				swap(data, data.length - i, index);
			}
		} else if (sortType.equals("desc")) { // 倒排序，从大排到小
			int index;
			for (int i = 1; i < data.length; i++) {
				index = 0;
				for (int j = 1; j <= data.length - i; j++) {
					if (data[j] < data[index]) {
						index = j;
					}
				}
				// 交换在位置data.length-i和index(最大值)两个数
				swap(data, data.length - i, index);
			}
		} else {
			System.out.println("您输入的排序类型错误！");
		}
		return data;
	}

	private void swap(int[] data, int x, int y) {
		int temp = data[x];
		data[x] = data[y];
		data[y] = temp;
	}

}

图简单选择排序过程示意图

<2> 堆排序

n个关键字序列K_l，K₂，…，K_n称为堆，当且仅当该序列满足如下性质(简称为堆性质)：

(1)k_i≤K_2i且k_i≤K_2i+1或(2)K_i≥K_2i且k_i≥K_2i+1(1≤i≤[n/2])

若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。

根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小根堆。

根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者，称为大根堆。

注意：

　①堆中任一子树亦是堆。

　②以上讨论的堆实际上是二叉堆(BinaryHeap)，类似地可定义k叉堆。

堆排序(HeapSort)是一树形选择排序。

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

/**
 * @author [email protected]
 *
 * Time: 2011-8-8 下午04:28:01
 */
public class HeapSort implements Sort {

	/* (non-Javadoc)
	 * @see sort.Sort#sortArray(int[], java.lang.String)
	 */
	@Override
	public int[] sortArray(int[] data, String sortType) {
		if(data == null || data.length == 0){
			return null;
		}
		if(sortType.equals("asc")){
			//该for循环用于创建一个堆，从n/2-1开始向前调整
	        for(int i = data.length/2-1; i>=0; i--){//r.length/2-1为最后一个非终端节点，向前调整
	        	adjustHeapASC(data,i,data.length);
	        }   
	        //该for循环用于把堆顶元素和无序区的最后一个元素交换，成为有序区的第一个元素，并进行堆调整
	        for(int j=data.length-1; j>0; j--){//每次调整出一个元素，则进行n-1趟排序
	            int temp = data[j];
	            data[j] = data[0];
	            data[0] = temp;
	            adjustHeapASC(data,0,j);
	        }
		}
		else if(sortType.equals("desc")){
			//该for循环用于创建一个堆，从n/2-1开始向前调整
	        for(int i = data.length/2-1; i>=0; i--){//r.length/2-1为最后一个非终端节点，向前调整
	        	adjustHeapDESC(data,i,data.length);
	        }   
	        //该for循环用于把堆顶元素和无序区的最后一个元素交换，成为有序区的第一个元素，并进行堆调整
	        for(int j=data.length-1; j>0; j--){//每次调整出一个元素，则进行n-1趟排序
	            int temp = data[j];
	            data[j] = data[0];
	            data[0] = temp;
	            adjustHeapDESC(data,0,j);
	        }
		}
		else{
			System.out.println("您输入的排序类型错误！");
		}
        return data;
	}
	
	private void adjustHeapASC(int[] data,int s,int m){   
        int temp = data[s];//暂存   
        for(int j=2*s+1; j<m; j=j*2){   
            if(j<m-1 && data[j]<data[j+1]){//找出这个根节点的两个子节点中的最大的   
                j++;    //j<m-1防止最后一个只有一个子节点，越界   
            }   
            if(temp > data[j]){//如果该元素已经是最大元素，则不用进行交换，直接跳出循环，自己与自己交换   
                break;   
            }else{//否则，需要进行交换   
            	data[s] = data[j];
                s = j;//s被赋予新值，接着从该节点向下遍历子节点   
            }   
        }   
        data[s] = temp;//一直找到大于或小于两个子节点的时候，把根节点放入该位置   
    }
	
	private void adjustHeapDESC(int[] data,int s,int m){   
        int temp = data[s];//暂存   
        for(int j=2*s+1; j<m; j=j*2){   
            if(j<m-1 && data[j]>data[j+1]){//找出这个根节点的两个子节点中的最大的   
                j++;    //j<m-1防止最后一个只有一个子节点，越界   
            }   
            if(temp < data[j]){//如果该元素已经是最大元素，则不用进行交换，直接跳出循环，自己与自己交换   
                break;   
            }else{//否则，需要进行交换   
            	data[s] = data[j];
                s = j;//s被赋予新值，接着从该节点向下遍历子节点   
            }   
        }   
        data[s] = temp;//一直找到大于或小于两个子节点的时候，把根节点放入该位置   
    }
}

堆排序的时间，主要由建立初始堆和反复重建堆这两部分的时间开销构成，它们均是通过调用Heapify实现的。

堆排序的最坏时间复杂度为O(nlgn)。堆排序的平均性能较接近于最坏性能。

由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。

堆排序是就地排序，辅助空间为O(1)，

它是不稳定的排序方法。

（4）归并排序

归并排序(Merge Sort)是利用"归并"技术来进行排序。归并是指将若干个已排序的子文件合并成一个有序的文件。

设两个有序的子文件(相当于输入堆)放在同一向量中相邻的位置上：R[low..m]，R[m+1..high]，先将它们合并到一个局部的暂存向量R1(相当于输出堆)中，待合并完成后将R1复制回R[low..high]中。

/**
 * @author [email protected]
 * 
 *         Time: 2011-8-8 下午05:49:49
 */
public class MergeSort implements Sort {

	/*
	 * (non-Javadoc)
	 * 
	 * @see sort.Sort#sortArray(int[], java.lang.String)
	 */
	@Override
	public int[] sortArray(int[] data, String sortType) {
		if(data == null || data.length == 0){
			return null;
		}
		gBSort(data,0,data.length-1,sortType); 
		return data;
	}
	
	private void gBSort(int[] data,int low,int high,String sortType){
        if(low<high){//区间长度大于1 
        	int m=(low+high)/2;   
         	gBSort(data,low,m,sortType);   
         	gBSort(data,m+1,high,sortType);
         	if(sortType.equals("asc")){
         		mergeASC(data,data.length,low,m,high);
         	}
         	else if(sortType.equals("desc")){
         		mergeDESC(data,data.length,low,m,high);
         	}
         	else{
         		System.out.println("您输入的排序类型错误！");
         	}
        }   
    }
	private void mergeASC(int[] data, int tempSize, int low, int m, int high) {
		int i = low;
		int j = m + 1;
		int p = 0;
		int[] temp = new int[tempSize];// 动态创建临时的空间
		while (i <= m && j <= high) {
			temp[p++] = (data[i] < data[j]) ? data[i++] : data[j++];// 把小的放到temp中
		}
		while (i <= m) {
			temp[p++] = data[i++];// 把剩余的元素放到临时数组中
		}
		while (j <= high) {
			temp[p++] = data[j++];// 把剩余的元素放到临时数组中
		}
		for (int z = 0, x = low; x <= high; x++, z++) {
			data[x] = temp[z];// 把数组赋值给数组
		}
	}
	
	private void mergeDESC(int[] data, int tempSize, int low, int m, int high) {
		int i = low;
		int j = m + 1;
		int p = 0;
		int[] temp = new int[tempSize];// 动态创建临时的空间
		while (i <= m && j <= high) {
			temp[p++] = (data[i] > data[j]) ? data[i++] : data[j++];// 把小的放到temp中
		}
		while (i <= m) {
			temp[p++] = data[i++];// 把剩余的元素放到临时数组中
		}
		while (j <= high) {
			temp[p++] = data[j++];// 把剩余的元素放到临时数组中
		}
		for (int z = 0, x = low; x <= high; x++, z++) {
			data[x] = temp[z];// 把数组赋值给数组
		}
	}

}

归并排序是一种稳定的排序。可用顺序存储结构。也易于在链表上实现。对长度为n的文件，需进行趟二路归并，每趟归并的时间为O(n)，故其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlgn)。需要一个辅助向量来暂存两有序子文件归并的结果，故其辅助空间复杂度为O(n)，显然它不是就地排序。

（5）基数排序

基数排序的基本思想是：从低位到高位依次对K^j(j=d-1，d-2，…，0)进行箱排序。在d趟箱排序中，所需的箱子数就是基数rd，这就是"基数排序"名称的由来。

若排序文件不是以数组R形式给出，而是以单链表形式给出(此时称为链式的基数排序)，则可通过修改出队和人队函数使表示箱子的链队列无须分配结点空间，而使用原链表的结点空间。人队出队操作亦无需移动记录而仅需修改指针。虽然这样一来节省了一定的时间和空间，但算法要复杂得多，且时空复杂度就其数量级而言并未得到改观。

基数排序的时间是线性的(即O(n))。

基数排序所需的辅助存储空间为O(n+rd)。

基数排序是稳定的。

补充代码：

/**
 * @author [email protected]
 *
 * Time: 2011-8-3 下午01:12:39
 */
public class SortContext {
	private Sort sort;
	/**
     * 初始化测试数组的方法
     * 
     * @return 一个初始化好的数组
     */
	public int[] createArray() {
		Random random = new Random();
		int[] array = new int[10];
		for (int i = 0; i < 10; i++) {
			array[i] = random.nextInt(100) - random.nextInt(100);// 生成两个随机数相减，保证生成的数中有负数
		}
		System.out.println("==========原始序列==========");
		printArray(array);
		return array;
	}

	/**
	 * 
	 * 打印数组中的元素到控制台
	 * 
	 * @param source
	 */

	public void printArray(int[] data) {
		for (int i : data) {
			System.out.print(i + ",");
		}
		System.out.println();
	}
	
	/**
	 * @return the sort
	 */
	public Sort getSort() {
		return sort;
	}

	/**
	 * @param sort the sort to set
	 */
	public void setSort(Sort sort) {
		this.sort = sort;
	}
	
	public void sort(int[] data, String sortType){
		int[] sortData = sort.sortArray(data, sortType);
		printArray(sortData);
	}
}

/**
 * @author [email protected]
 * 
 *         Time: 2011-8-3 下午01:01:10
 */
public class SortTest {
	
	public static void main(String[] args){
		SortContext test = new SortContext();
		int[] data = test.createArray();
		
		test.setSort(new MergeSort());
		//test.setSort(new InsertSort());
		//test.setSort(new BinInsertSort());
		//test.setSort(new QuickSort());
		//test.setSort(new SelectSort());
		//test.setSort(new BubbleSort());
		test.sort(data, "asc");
		test.sort(data, "desc");
	}

}

排 序

相关推荐

排序