选择排序和插入排序

package chuangyeyilu.sort;
 
/**
 * 选择排序和插入排序
 * @author Pan Chong
 *
 */
public class Sort {
 
	/**
	 * 选择排序: 首先在数组中查找最小值, 如果该值不在第一个位置, 那么将其
	 * 和处在第一个位置的元素交换,然后从第二个位置重复此过程,将剩下元素中
	 * 最小值交换到第二个位置 。当到最后一位 时,数组排序结束
	 * @param array
	 */
	static void selectionSort(int[] array) {
		for (int i = 0; i < array.length - 1; i++) {
			int min_idx = i;
 
			for (int j = i + 1; j < array.length; j++) {
				if (array[j] < array[min_idx]) {
					min_idx = j;
				}
			}
 
			if (min_idx != i) {
				swap(array, min_idx, i);
			}
 
		}
	}
 
	/**
	 * 交换数组数据
	 * 
	 * @param array
	 * @param min_idx
	 * @param i
	 */
	private static void swap(int[] array, int min_idx, int i) {
		int temp = array[min_idx];
		array[min_idx] = array[i];
		array[i] = temp;
	}
 
	/**
	 * 插入排序 通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,
	 * 找到相应位置并插入。核心思想是假设第一个元素排好,之后的元素对排好的部
	 * 分从后向前比较并逐一移动。
	 * @param array
	 */
	public static void insertSort(int[] array) {
		int in, out;
		for (out = 1; out < array.length; out++) {
			int temp = array[out];
			in = out;
			while (in > 0 && array[in - 1] >= temp) {
				array[in] = array[in - 1];
				--in;
			}
			array[in] = temp;
		}
	}
 
	public static void main(String[] args) {
		int[] array = new int[] { 1, 2, 6, 5, 7, 9, 0, 121, 4545 };
		long startTime = System.nanoTime();
		selectionSort(array);
		for (int i : array) {
			System.out.println(i);
		}
		long endTime = System.nanoTime();
		System.out.println("选择排序耗时:" + (endTime - startTime));
		int[] array2 = new int[] { 1, 2, 6, 5, 7, 9, 0, 121, 4545 };
		long startTime1 = System.nanoTime();
		insertSort(array2);
		for (int i : array2) {
			System.out.println(i);
		}
		long endTime1 = System.nanoTime();
		System.out.println("插入排序耗时:" + (endTime1 - startTime1));
	}
}
打赏

作者:

操千曲而后晓声,观千剑而后识器

暂无关键词!