常见排序

BBLLMYD

浏览: 17885 次
性别:
来自: 北京

最近访客更多访客>>

jadechenfei

sunshinecao_2014

fhsh168

dagf113225

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

博客分类：

数据结构与算法

Java 数据结构算法

排序概念:

1.内部排序：

工具类中定义交换数组元素、生成数据源等方法(用于下面的排序)：

import java.util.Random;

public class SortUtil {

	// 通过数组下标交换元素位置
	public static void swap(int[] data, int i, int j) {
		int temp = data[i];
		data[i] = data[j];
		data[j] = temp;
	}

	// 生成and显示数据源
	public static void DataSrc(int[] is) {
		for (int i = 0; i < is.length; i++) {
			is[i] = new Random().nextInt(100);
		}
		System.out.print("源数据:\t");
		for (int i = 0; i < is.length; i++) {
			System.out.print(+is[i] + " ");
		}
		System.out.println();
	}

	// 显示最终排序结果
	public static void showRes(int[] is) {
		System.out.print("排序结果:\t");
		for (int i = 0; i < is.length; i++) {
			System.out.print(+is[i] + " ");
		}
	}

	// 显示每此排序后的情况
	public static void showEach(int[] is, int i) {
		System.out.print("第" + (i + 1) + "次排序:\t");
		for (int k = 0; k < is.length; k++) {
			System.out.print(is[k] + " ");
		}
		System.out.println();
	}
}

1.1冒泡排序:

冒泡排序的基本思想是:对待排序记录关键字从后往前(逆序)进行多遍扫描,当发现相邻两个关键字的次序与排序要求的规则不符时,就将这两个数据进行交换,这样,关键字较小的记录将逐渐从后往前移动,就像气泡在水中向上浮一样,所以该算法也称为气泡排序法.

冒泡排序图解:

代码实现:

public class BubbleSort {

	public static void main(String[] args) {
		int[] is = new int[10];
		// 在工具类生成10个100以内随机数作为数据源并显示
		SortUtil.DataSrc(is);

		for (int i = 0; i < is.length - 1; i++) {
			for (int j = 0; j < is.length - i - 1; j++) {
				if (is[j] > is[j + 1]) {
					SortUtil.swap(is, j, j + 1);// 通过下标对两个数进行位置交换
				}
			}
			// 显示每一次排序的结果
			SortUtil.showEach(is, i);
		}
		// 显示最终排序结果
		SortUtil.showRes(is);

	}

}

排序结果及过程:

1.2快速排序:

快速排序使用分支策略来把排序元素序列分为两个子序列,具体步骤为:

(1):从数列中挑出一个元素,该元素称为"基准".

(2):扫描一遍数列,将所有比"基准"小的元素排在基准前面,所有比"基准"大的元素排在"基准"后面.

(3):通过递归,将各个子序列划分为更小的序列,直到把小于"基准"元素的子数列和大于基准元素的子序列排序.

快速排诉步骤:

快速排序实现:

public class QuickSort {

	public static void main(String[] args) {
		int[] is = new int[10];
		SortUtil.DataSrc(is);
		quickSort(is, 0, is.length-1);
		SortUtil.showRes(is);
	}
	
	private static void quickSort(int[] data, int i, int j) {
		int pivotIndex = (i + j) / 2;
		SortUtil.swap(data, pivotIndex, j);

		int k = partition(data, i - 1, j, data[j]);
		SortUtil.swap(data, k, j);
		if ((k - i) > 1)
			quickSort(data, i, k - 1);
		if ((j - k) > 1)
			quickSort(data, k + 1, j);
	}

	private static int partition(int[] data, int l, int r, int pivot) {
		do {
			while (data[++l] < pivot)
				;
			while ((r != 0) && data[--r] > pivot)
				;
			SortUtil.swap(data, l, r);
		} while (l < r);
		SortUtil.swap(data, l, r);
		return l;
	}
}

快速排序结果:

--------------------------------------------------------

1.3简单选择排序:

选择排序的基本思想:对n个记录进行扫描,选择最小的记录,将其输出,接着在剩下的n-1个记录中进行扫描,选择最小的记录将其输出,...不断重复这个过程,直到只剩一个记录为止.

简单选择排序:

简单选择排序实现:

public class SelectionSort {
	public static void main(String[] args) throws Exception {
		int[] is = new int[10];
		SortUtil.DataSrc(is);
		sort(is);
		SortUtil.showRes(is);
	}

	private static void sort(int[] is) {
		for (int i = 0; i < is.length - 1; i++) {
			for (int j = i + 1; j < is.length; j++) {
				if (is[i] > is[j]) {
					SortUtil.swap(is, i, j);
				}
			}
			SortUtil.showEach(is, i);
		}
	}
}

运行结果:

1.4 堆排序

堆排序是一个完全二叉树,树中的每个结点对应于原始数据的一个记录,并且每个结点应该满足以下条件:非叶结点的数据大于或等于其左、右孩子的

数据(若是按照从小到大的顺序排序,则要求非叶结点的数据小于或等于其左、右孩子结点的数据).

由堆的定义可以看出,其根结点为最大值,堆排序就是利用这一特点进行的,堆排序的过程包括两个阶段:

(1):将无序的数据构成堆(即用无序数据生成满足堆定义的完全二叉树).

(2):利用堆排序(用上一步生成的堆生成有序的数据,实际上就是对完全二叉树进行遍历).

例子:69,65,90,37,92,6,28,54:

树的生成过程:

堆排序输出过程(每生成一个数后要树的结构改变,要重新生成一次):

堆排序实现:

public class DeapSort {

	public static void main(String[] args) {
		int[] is = new int[10];
		SortUtil.DataSrc(is);
		sort(is);
		SortUtil.showRes(is);
	}

	public static void sort(int[] data) {
		MaxHeap h = new MaxHeap();
		h.init(data);
		for (int i = 0; i < data.length; i++)
			h.remove();
		System.arraycopy(h.queue, 1, data, 0, data.length);
	}

	private static class MaxHeap {
		private int size = 0;
		private int[] queue;

		void init(int[] data) {
			this.queue = new int[data.length + 1];
			for (int i = 0; i < data.length; i++) {
				queue[++size] = data[i];
				fixUp(size);
			}
		}

		public void remove() {
			SortUtil.swap(queue, 1, size--);
			fixDown(1);
		}

		// fixdown
		private void fixDown(int k) {
			int j;
			while ((j = k << 1) <= size) {
				if (j < size && queue[j] < queue[j + 1])
					j++;
				if (queue[k] > queue[j]) // 不用交换
					break;
				SortUtil.swap(queue, j, k);
				k = j;
			}
		}

		private void fixUp(int k) {
			while (k > 1) {
				int j = k >> 1;
				if (queue[j] > queue[k])
					break;
				SortUtil.swap(queue, j, k);
				k = j;
			}
		}
	}
}

1.5 直接插入排序法:

插入排序(InsertionSort)的算法描述是一种简单直观的排序算法.它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应的位置并插入.插入排序在实现上,在从后向前扫描的过程中,需要反复把已经排序的元素逐步向后移动,为最新元素提供插入空间.

直接插入排序:

直接插入排序实现:

public class InsertSort {

	public static void main(String[] args) {
		int[] is = new int[10];
		SortUtil.DataSrc(is);
		sort(is);
		SortUtil.showRes(is);
	}

	private static void sort(int[] is) {
		for (int i = 1; i < is.length; i++) {// 默认只有一个元素时是有序的,所以不用排序
			for (int j = i; j > 0; j--) {
				if (is[j] < is[j - 1])
					SortUtil.swap(is, j, j - 1);
			}
		}
	}
}

1.6希尔排序:

希尔排序又称为缩小增量排序,也属于插入排序类的算法,是对直接插入排序的一种改进.

基本思想就是:将需要排序的序列划分为若干个较小的序列,对这些序列进行直接插入排序,通过这样的操作可使用需要排列的数列基本有序,最后再使用一次直接插入排序,这样,首先对数量较小的序列进行直接插入排序可提高效率,最后对基本有序的序列进行直接插入排序,也可提高效率,排序过程的效率得到提升.

希尔排序过程图解:

希尔排序实现:

public class ShellSort {

	public static void main(String[] args) {
		int[] is = new int[10];
		SortUtil.DataSrc(is);
		sort(is);
		SortUtil.showRes(is);
	}

	public static void sort(int[] data) {
		for (int i = data.length / 2; i > 2; i /= 2) {
			for (int j = 0; j < i; j++) {
				insertSort(data, j, i);
			}
		}
		insertSort(data, 0, 1);
	}

	private static void insertSort(int[] data, int start, int inc) {
		for (int i = start + inc; i < data.length; i += inc) {
			for (int j = i; (j >= inc) && (data[j] < data[j - inc]); j -= inc) {
				SortUtil.swap(data, j, j - inc);
			}
		}
	}
}

1.7合并排序(MergeSort):

就是将两个或多个有序表合并成一个有序表.

合并排序图解:

合并排序实现:

public class MergeSort {

	public static void main(String[] args) {
		int[] is = new int[10];
		SortUtil.DataSrc(is);
		sort(is);
		SortUtil.showRes(is);
	}

	public static void sort(int[] data) {
		int[] temp = new int[data.length];
		mergeSort(data, temp, 0, data.length - 1);
	}

	private static void mergeSort(int[] data, int[] temp, int l, int r) {
		int mid = (l + r) / 2;
		if (l == r)
			return;
		mergeSort(data, temp, l, mid);
		mergeSort(data, temp, mid + 1, r);

		for (int i = l; i <= r; i++) {
			temp[i] = data[i];
		}
		int i1 = l;
		int i2 = mid + 1;
		for (int cur = l; cur <= r; cur++) {
			if (i1 == mid + 1)
				data[cur] = temp[i2++];
			else if (i2 > r)
				data[cur] = temp[i1++];
			else if (temp[i1] < temp[i2])
				data[cur] = temp[i1++];
			else

				data[cur] = temp[i2++];
		}
	}
}

2.外部排序：

外部排序指的是大文件的排序，当待排序的文件很大时，无法将整个文件的所有记录同时调入内存进行排序，只能将文件存放在外存，这种排称为外部排序。外部排序的过程主要是依据数据的内外存交换和“内部归并”两者结合起来实现的。

一般提到排序都是指内排序，比如快速排序，堆排序，归并排序等，所谓内排序就是可以在内存中完成的排序。RAM的访问速度大约是磁盘的25万倍，我们当然希望如果可以的话都是内排来完成。但对于大数据集来说，内存是远远不够的，这时候就涉及到外排序的知识了。

外部排序最常用的算法是多路归并排序，即将原文件分解成多个能够一次性装入内存的部分分别把每一部分调入内存完成排序。然后，对已经排序的子文件进行归并排序。