常见排序

排序概念:

?

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.外部排序：

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

常见排序

原文：http://bbllmyd.iteye.com/blog/2305608