黑马程序员_java中的常见算法

   ------- android培训、java培训、期待与您交流！ ----------

本人最近收集整理的一些排序算法，希望对大家有所帮助！

1、选择排序（Selection sort）、插入排序（Insertion sort）与气泡排序（Bubble sort）这三个排序方式是初学排序所必须知道的三个基本排序方式，它们由于速度不快而不实用。

public class BasicSort {
	public static void selectionSort(int[] number) {
		for (int i = 0; i < number.length - 1; i++) {
			int m = i;
			for (int j = i + 1; j < number.length; j++)
				if (number[j] < number[m])
					m = j;
			if (i != m)
				swap(number, i, m);
		}
	}

	public static void injectionSort(int[] number) {
		for (int j = 1; j < number.length; j++) {
			int tmp = number[j];
			int i = j - 1;
			while (tmp < number[i]) {
				number[i + 1] = number[i];
				i--;
				if (i == -1)
					break;
			}
			number[i + 1] = tmp;
		}
	}

	public static void bubbleSort(int[] number) {
		boolean flag = true;
		for (int i = 0; i < number.length - 1 && flag; i++) {
			flag = false;
			for (int j = 0; j < number.length - i - 1; j++) {
				if (number[j + 1] < number[j]) {
					swap(number, j + 1, j);
					flag = true;
				}
			}
		}
	}

	private static void swap(int[] number, int i, int j) {
		int t;
		t = number[i];
		number[i] = number[j];
		number[j] = t;
	}
}

 

2、合并排序法

合并排序法基本是将两笔已排序的资料合并并进行排序，如果所读入的资料尚未排序，可以先利用其它的排序方式来处理这两笔资料，然后再将排序好的这两笔资料合并。

 

public class MergeSort {
	public static int[] sort(int[] number1, int[] number2) {
		int[] number3 = new int[number1.length + number2.length];
		int i = 0, j = 0, k = 0;
		while (i < number1.length && j < number2.length) {
			if (number1[i] <= number2[j])
				number3[k++] = number1[i++];
			else
				number3[k++] = number2[j++];
		}
		while (i < number1.length)
			number3[k++] = number1[i++];
		while (j < number2.length)
			number3[k++] = number2[j++];
		return number3;
	}
}

 3、基数排序法

基数排序法又称“桶子法”（bucket sort）它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，在某些时候，基数排序法的效率高于其它的比较性排序法。

public class RadixSort {
	public static void sort(int[] number, int d) {
		int k = 0;
		int n = 1;
		int[][] temp = new int[number.length][number.length];
		int[] order = new int[number.length];
		while (n <= d) {
			for (int i = 0; i < number.length; i++) {
				int lsd = ((number[i] / n) % 10);
				temp[lsd][order[lsd]] = number[i];
				order[lsd]++;
			}
			for (int i = 0; i < number.length; i++) {
				if (order[i] != 0)
					for (int j = 0; j < order[i]; j++) {
						number[k] = temp[i][j];
						k++;
					}
				order[i] = 0;
			}
			n *= 10;
			k = 0;
		}
	}

	public static void main(String[] args) {
		int[] data = { 73, 22, 93, 43, 55, 14, 28, 65, 39, 81, 33, 100 };
		RadixSort.sort(data, 100);
		for (int i = 0; i < data.length; i++) {
			System.out.print(data[i] + " ");
		}
	}
}

 

 不足之处希望指正！