java算法收集,欢迎评论留下源代码!

GoogleVip8 1年前 ⋅ 889 阅读

1366700675_1111.JPG

你知道java中有哪些算法吗?什么时候使用什么算法呢?

请在评论区留言,我会统计发布并通知大家看的

插入排序:内部排序、O(n2)、稳定

 
	static int data[] = { 9, 2, 7, 19, 100, 97, 63, 208, 55, 78 };
 
	public static void insertSort() {
		int tmp, j = 0;
		for (int k = 0; k < data.length; k++) {//-----1-----
			tmp = data[k];
			j = k - 1;
			while (j >= 0 && tmp < data[j]) {//-----2-----
				data[j + 1] = data[j];
				j--;
			}
			data[j + 1] = tmp;//------3-------
		}
	}
 
	public static void main(String[] args) {
		print();
		System.out.println();
		insertSort();
		System.out.println();
		print();
	}
 
	static void print() {
		for (int i = 0; i < data.length; i++) {
			System.out.print(data[i] + " ");
		}
	}

选择排序:O(n2)、不稳定

static int data[] = { 9, 2, 7, 19, 100, 97, 63, 208, 55, 78 };
 
	public static void selectSort() {
		int i, j, k, tmp = 0;
		for (i = 0; i < data.length - 1; i++) {
			k = i;
			for (j = i + 1; j < data.length; j++)
				if (data[j] < data[k])
					k = j;
			if (k != i) {
				tmp = data[i];
				data[i] = data[k];
				data[k] = tmp;
			}
		}
	}
	public static void main(String[] args) {
		print();
		System.out.println();
		selectSort();
		System.out.println();
		print();
	}
 
	static void print() {
		for (int i = 0; i < data.length; i++) {
			System.out.print(data[i] + " ");
		}
	}

快速排序:O(nlogn)、不稳定

 
	static class QuickSort {
 
		public int data[];
 
		private int partition(int array[], int low, int high) {
			int key = array[low];
			while (low < high) {
				while (low < high && array[high] >= key)
					high--;
				array[low] = array[high];
				while (low < high && array[low] <= key)
					low++;
				array[high] = array[low];
			}
			array[low] = key;
			return low;
		}
 
		public int[] sort(int low, int high) {
			if (low < high) {
				int result = partition(data, low, high);
				sort(low, result - 1);
				sort(result + 1, high);
			}
			return data;
		}
	}
 
	static void print(int data[]) {
		for (int i = 0; i < data.length; i++) {
			System.out.print(data[i] + " ");
		}
	}
 
	public static void main(String[] args) {
		int data[] = { 20, 3, 10, 9, 186, 99, 200, 96, 3000 };
		print(data);
		System.out.println();
		QuickSort qs = new QuickSort();
		qs.data = data;
		qs.sort(0, data.length - 1);
		print(data);
	}

冒泡排序:稳定、基本有序可达O(n),最坏情况为O(n2)

static int data[] = { 9, 2, 7, 19, 100, 97, 63, 208, 55, 78 };
 
	public static void bubbleSort() {
		int i, j, tmp = 0;
		for (i = 0; i < data.length - 1; i++) {
			for (j = data.length - 1; j > i; j--) {
				if (data[j] < data[j - 1]) {
					tmp = data[j];
					data[j] = data[j - 1];
					data[j - 1] = tmp;
				}
			}
		}
	}
 
	public static void main(String[] args) {
		print();
		System.out.println();
		bubbleSort();
		System.out.println();
		print();
	}
 
	static void print() {
		for (int i = 0; i < data.length; i++) {
			System.out.print(data[i] + " ");
		}
	}

堆排序

private static int[] sort = new int[] { 1, 0, 10, 20, 3, 5, 6, 4, 9, 8, 12,
			17, 34, 11 };
 
	public static void main(String[] args) {
		buildMaxHeapify(sort);
		heapSort(sort);
		print(sort);
	}
 
	private static void buildMaxHeapify(int[] data) {
		// 没有子节点的才需要创建最大堆,从最后一个的父节点开始
		int startIndex = getParentIndex(data.length - 1);
		// 从尾端开始创建最大堆,每次都是正确的堆
		for (int i = startIndex; i >= 0; i--) {
			maxHeapify(data, data.length, i);
		}
	}
 
	/**
	 * 创建最大堆
	 * 
	 * @param data
	 * @param heapSize
	 *            需要创建最大堆的大小,一般在sort的时候用到,因为最多值放在末尾,末尾就不再归入最大堆了
	 * @param index
	 *            当前需要创建最大堆的位置
	 */
	private static void maxHeapify(int[] data, int heapSize, int index) {
		// 当前点与左右子节点比较
		int left = getChildLeftIndex(index);
		int right = getChildRightIndex(index);
 
		int largest = index;
		if (left < heapSize && data[index] < data[left]) {
			largest = left;
		}
		if (right < heapSize && data[largest] < data[right]) {
			largest = right;
		}
		// 得到最大值后可能需要交换,如果交换了,其子节点可能就不是最大堆了,需要重新调整
		if (largest != index) {
			int temp = data[index];
			data[index] = data[largest];
			data[largest] = temp;
			maxHeapify(data, heapSize, largest);
		}
	}
 
	/**
	 * 排序,最大值放在末尾,data虽然是最大堆,在排序后就成了递增的
	 * 
	 * @param data
	 */
	private static void heapSort(int[] data) {
		// 末尾与头交换,交换后调整最大堆
		for (int i = data.length - 1; i > 0; i--) {
			int temp = data[0];
			data[0] = data[i];
			data[i] = temp;
			maxHeapify(data, i, 0);
		}
	}
 
	/**
	 * 父节点位置
	 * 
	 * @param current
	 * @return
	 */
	private static int getParentIndex(int current) {
		return (current - 1) >> 1;
	}
 
	/**
	 * 左子节点position 注意括号,加法优先级更高
	 * 
	 * @param current
	 * @return
	 */
	private static int getChildLeftIndex(int current) {
		return (current << 1) + 1;
	}
 
	/**
	 * 右子节点position
	 * 
	 * @param current
	 * @return
	 */
	private static int getChildRightIndex(int current) {
		return (current << 1) + 2;
	}
 
	private static void print(int[] data) {
		int pre = -2;
		for (int i = 0; i < data.length; i++) {
			if (pre < (int) getLog(i + 1)) {
				pre = (int) getLog(i + 1);
				System.out.println();
			}
			System.out.print(data[i] + " |");
		}
	}
 
	/**
	 * 以2为底的对数
	 * 
	 * @param param
	 * @return
	 */
	private static double getLog(double param) {
		return Math.log(param) / Math.log(2);
	}

归并排序

	// 将有序数组a[]和b[]合并到c[]中
	static void MemeryArray(int a[], int n, int b[], int m, int c[]) {
		int i, j, k;
 
		i = j = k = 0;
		while (i < n && j < m) {
			if (a[i] < b[j])
				c[k++] = a[i++];
			else
				c[k++] = b[j++];
		}
 
		while (i < n)
			c[k++] = a[i++];
 
		while (j < m)
			c[k++] = b[j++];
	}
	
	public static void main(String[] args) {
		int a[] = { 2, 7, 8, 10, 299 };
		int b[] = { 5, 9, 14, 20, 66, 88, 92 };
		int c[] = new int[a.length + b.length];
		MemeryArray(a, 5, b, 7, c);
		print(c);
	}
 
	private static void print(int[] c) {
		for (int i = 0; i < c.length; i++) {
			System.out.print(c[i] + " ");
		}
	}

希尔排序:O(nlogn)、不稳定

 
	static void shellsort(int[] a, int n) {
		int i, j, temp;
		int gap = 0;
		while (gap <= n) {
			gap = gap * 3 + 1;
		}
		while (gap > 0) {
			for (i = gap; i < n; i++) {
				j = i - gap;
				temp = a[i];
				while ((j >= 0) && (a[j] > temp)) {
					a[j + gap] = a[j];
					j = j - gap;
				}
				a[j + gap] = temp;
			}
			gap = (gap - 1) / 3;
		}
	}
 
	static void print(int data[]) {
		for (int i = 0; i < data.length; i++) {
			System.out.print(data[i] + " ");
		}
	}
 
	public static void main(String[] args) {
		int data[] = { 2, 68, 7, 19, 1, 28, 66, 200 };
		print(data);
		System.out.println();
		shellsort(data, data.length);
		print(data);
	}

多路快排

JDK1.8中Arrays.sort()采用的排序算法,具有较快的时间复杂度和稳定性,基本思路为:

1. 选取两个中轴P1, P2。

2. 假设P1<P2,否则交换。

3. 过程中原数组会分为四个部分:小于中轴1,大于中轴2,介于两个中轴之间,未排序部分(刚开始除了两个中轴,其它元素都属于这部分)。

4. 开始后,从未排序部分选取一个数,和两个中轴作比较,然后放到合适的位置,一直到未排序部分无数据,结束一趟排序。

5. 递归地处理子数组,稳定排序,时间复杂度稳定为O(nlogn)。

1366700799_2653.png


全部评论: 0

    我有话说: