`
Flyingh
  • 浏览: 18217 次
  • 性别: Icon_minigender_1
  • 来自: 西安
社区版块
存档分类
最新评论

sort(Java)

    博客分类:
  • sort
阅读更多
package com.flyingh.demo;

public class Demo {
	public static void main(String[] args) {
		int[] arr = { 8, 1, 7, 2, 5, 9, 0, 3, 6, 4 };
		print(arr);
		// bubbleSort(arr);
		// selectSort(arr);
		// swapSort(arr);
		// insertSort(arr);
		// insertSort(arr,arr.length-1);
		// shellSort(arr);
		// mergeSort(arr,0,arr.length-1);
		// quickSort(arr,0,arr.length-1);
		// heapSort(arr,arr.length);
		// countingSort(arr);
		// radixSort(arr);
		// bucketSort(arr);
		print(arr);
		// System.out.println(binarySearch(arr,0,arr.length-1,5));
		System.out.println(select(arr, 1, 8, 3));
	}

	public static int select(int[] arr, int i, int j, int k) {
		if (k < 1 || k > j - i + 1) {
			return -1;
		}
		// int t = partition(arr, i, j);
		int t = partition2(arr, i, j);
		if (t == k + i - 1) {
			return arr[t];
		} else if (t < k + i - 1) {
			return select(arr, t + 1, j, k + i - 1 - t);
		} else {
			return select(arr, i, t - 1, k);
		}
	}

	public static int binarySearch(int[] arr, int m, int n, int x) {
		if (arr[m] > x || arr[n] < x) {
			return -1;
		}
		int mid = (m + n) / 2;
		if (arr[mid] > x) {
			return binarySearch(arr, m, mid, x);
		} else if (arr[mid] < x) {
			return binarySearch(arr, mid + 1, n, x);
		} else {
			return mid;
		}
	}

	public static void bucketSort(int[] arr) {
		int max = getMax(arr);
		int[] c = new int[max + 1];
		for (int i = 0; i < arr.length; i++) {
			++c[arr[i]];
		}
		for (int i = 1; i < c.length; i++) {
			c[i] += c[i - 1];
		}
		int[] tmp = new int[arr.length];
		for (int i = 0; i < tmp.length; i++) {
			tmp[--c[arr[i]]] = arr[i];
		}
		System.arraycopy(tmp, 0, arr, 0, tmp.length);
	}

	public static void radixSort(int[] arr) {
		int max = getMax(arr);
		int len = String.valueOf(max).length();
		for (int i = 0; i < len;) {
			sort(arr, i++);
		}
	}

	private static final int RADIX = 10;

	private static void sort(int[] arr, int m) {
		int[] c = new int[RADIX];
		for (int i = 0; i < arr.length; i++) {
			++c[digital(arr[i], m)];
		}
		for (int i = 1; i < c.length; i++) {
			c[i] += c[i - 1];
		}
		int[] tmp = new int[arr.length];
		for (int i = tmp.length - 1; i >= 0; --i) {
			tmp[--c[digital(arr[i], m)]] = arr[i];
		}
		System.arraycopy(tmp, 0, arr, 0, tmp.length);
	}

	private static int digital(int x, int m) {
		return (int) (x / Math.pow(RADIX, m) % RADIX);
	}

	public static void countingSort(int[] arr) {
		int max = getMax(arr);
		int[] c = new int[max + 1];
		for (int i = 0; i < arr.length; i++) {
			++c[arr[i]];
		}
		for (int i = 1; i < c.length; i++) {
			c[i] += c[i - 1];
		}
		int[] tmp = new int[arr.length];
		for (int i = tmp.length - 1; i >= 0; --i) {
			tmp[--c[arr[i]]] = arr[i];
		}
		System.arraycopy(tmp, 0, arr, 0, tmp.length);
	}

	private static int getMax(int[] arr) {
		int max = arr[0];
		for (int i = 1; i < arr.length; ++i) {
			if (max < arr[i]) {
				max = arr[i];
			}
		}
		// for (int i : arr) {
		// if(max<i){
		// max=i;
		// }
		// }
		return max;
	}

	public static void heapSort(int[] arr, int len) {
		buildHeap(arr, len);
		if (arr[0] > arr[len - 1]) {
			swap(arr, 0, len - 1);
			heapSort(arr, len - 1);
		}
	}

	private static void buildHeap(int[] arr, int len) {
		for (int i = len / 2 - 1; i >= 0; --i) {
			heapify(arr, i, len);
		}
	}

	private static void heapify(int[] arr, int i, int len) {
		int l = 2 * i + 1;
		int r = 2 * i + 2;
		if (r < len) {
			int large = i;
			if (arr[large] < arr[l]) {
				large = l;
			}
			if (arr[large] < arr[r]) {
				large = r;
			}
			if (large != i) {
				swap(arr, i, large);
				heapify(arr, large, len);
			}
		}
	}

	public static void quickSort(int[] arr, int m, int n) {
		if (m < n) {
			// int t=partition(arr,m,n);
			int t = partition2(arr, m, n);
			quickSort(arr, m, t - 1);
			quickSort(arr, t + 1, n);
		}
	}

	private static int partition2(int[] arr, int m, int n) {
		int key = arr[n];
		int i = m - 1;
		for (int j = m; j < n; j++) {
			if (arr[j] < key) {
				swap(arr, ++i, j);
			}
		}
		swap(arr, ++i, n);
		return i;
	}

	@SuppressWarnings("unused")
	private static int partition(int[] arr, int m, int n) {
		int key = arr[m];
		while (m < n) {
			while (m < n && arr[n] >= key) {
				--n;
			}
			arr[m] = arr[n];
			while (m < n && arr[m] <= key) {
				++m;
			}
			arr[n] = arr[m];
		}
		arr[m] = key;
		return m;
	}

	public static void mergeSort(int[] arr, int m, int n) {
		if (m < n) {
			int mid = (m + n) / 2;
			mergeSort(arr, m, mid);
			mergeSort(arr, mid + 1, n);
			merge(arr, m, mid, n);
		}
	}

	private static void merge(int[] arr, int m, int mid, int n) {
		int[] l = new int[mid - m + 1];
		int[] r = new int[n - mid];
		for (int i = 0; i < l.length; i++) {
			l[i] = arr[m + i];
		}
		for (int i = 0; i < r.length; i++) {
			r[i] = arr[mid + 1 + i];
		}
		int i = 0;
		int j = 0;
		while (i < l.length && j < r.length) {
			if (l[i] < r[j]) {
				arr[m++] = l[i++];
			} else {
				arr[m++] = r[j++];
			}
		}
		while (i < l.length) {
			arr[m++] = l[i++];
		}
		while (j < r.length) {
			arr[m++] = r[j++];
		}
	}

	public static void shellSort(int[] arr) {
		for (int gap = arr.length / 2; gap > 0; gap /= 2) {
			for (int i = gap; i < arr.length; i++) {
				int key = arr[i];
				int j = i - gap;
				for (; j >= 0 && arr[j] > key; j -= gap) {
					arr[j + gap] = arr[j];
				}
				arr[j + gap] = key;
			}
		}
	}

	public static void insertSort(int[] arr, int m) {
		if (m > 0) {
			insertSort(arr, m - 1);
			int key = arr[m];
			int i = m - 1;
			for (; i >= 0 && arr[i] > key; --i) {
				arr[i + 1] = arr[i];
			}
			arr[i + 1] = key;
		}
	}

	public static void insertSort(int[] arr) {
		for (int i = 1; i < arr.length; i++) {
			int key = arr[i];
			int j = i - 1;
			for (; j >= 0 && arr[j] > key; --j) {
				arr[j + 1] = arr[j];
			}
			arr[j + 1] = key;
		}
	}

	public static void swapSort(int[] arr) {
		for (int i = 0; i < arr.length - 1; i++) {
			for (int j = i + 1; j < arr.length; j++) {
				if (arr[i] > arr[j]) {
					swap(arr, i, j);
				}
			}
		}
	}

	public static void selectSort(int[] arr) {
		for (int i = 0; i < arr.length - 1; i++) {
			int k = i;
			for (int j = i + 1; j < arr.length; j++) {
				if (arr[k] > arr[j]) {
					k = j;
				}
			}
			if (k != i) {
				swap(arr, k, i);
			}
		}
	}

	public static void bubbleSort(int[] arr) {
		for (int i = 0; i < arr.length - 1; i++) {
			for (int j = 0; j < arr.length - 1 - i; j++) {
				if (arr[j] > arr[j + 1]) {
					swap(arr, j, j + 1);
				}
			}
		}
	}

	private static void swap(int[] arr, int j, int j2) {
		int tmp = arr[j];
		arr[j] = arr[j2];
		arr[j2] = tmp;
	}

	private static void print(int[] arr) {
		for (int i : arr) {
			System.out.print(i + " ");
		}
		System.out.println();
	}
}

分享到:
评论
发表评论

文章已被作者锁定,不允许评论。

相关推荐

    JAVA SortList 通用排序类

    JAVA SortList 通用排序类 从网上搜到一个java 对 List 排序的工具,自己改了下 支持 整数 和 浮点数 比较后排序,浮点数小数部分的有点问题,期待大牛帮忙优化。

    Java heap Sort

    heap Sort. In briefly, it had been done with java.

    java工具类——sort

    主要封装了冒泡排序、选择排序,其他待完善。

    java List 排序 Collections.sort

    总结起来,`Collections.sort()`是Java中对List进行排序的标准工具,它支持自然排序和自定义排序。了解其工作原理和优化技巧,可以帮助我们在编程实践中更高效地处理数据。通过阅读和理解`Collections.sort()`的源码...

    用java实现选择排序SelectSort

    用java实现选择排序SelectSort 用java实现选择排序SelectSort 用java实现选择排序SelectSort

    JavaSort.java

    几种常见的排序算法包括冒泡排序、选择排序、插入排序、快速排序的Java代码实现,有注释,容易理解。下载下来之后换一下包路径即可,欢迎留言评论

    java sort排序算法实例完整代码

    Java中的`sort`排序算法是Java集合框架的重要组成部分,主要用于对List接口的实现类进行排序。这个算法在Java中主要体现在`java.util.Arrays`和`java.util.Collections`两个类中,提供了对数组和集合的排序功能。...

    用java实现插入排序InsertSort

    用java实现插入排序InsertSort 用java实现插入排序InsertSort用 java实现插入排序InsertSort

    BinarySortTreeDemo.java

    二叉排序树,完整代码。叉排序树(Binary Sort Tree),又称二叉查找树(Binary Search Tree),亦称二叉搜索树。

    QuickSort java最快的排序

    QuickSort java最快的排序 比冒泡快得不止一点 更nb 八大排序之一

    JAVA实现StoogeSort方法排序

    JAVA实现StoogeSort方法排序,简单演示。

    用java实现Sort功能

    用java实现Sort功能,以图形界面的形式实现,有升序和降序。

    Sort.java(排序算法)

    数据结构中排序算法的java代码实现

    Bubble_Sort.java

    冒泡排序 依次比较两个相邻的元素,如果前者大于后者就交换位置 每一趟排序之后就会把这趟中的最大值放在最后一位 重复上诉过程,直到没有在需要比较的元素为止

    Code01_SelectionSort.java

    Code01_SelectionSort.java

    Sort03.java

    Sort03.java

    SortAlgorithm.java

    SortAlgorithm.java

    计数排序JAVA实现counting sort algorithm

    Java实现计数排序的关键步骤如下: 1. **初始化计数数组**:创建一个与待排序数组最大值相等长度的计数数组,所有元素初始化为0。 2. **计数过程**:遍历待排序数组,对于每个元素,将其值作为索引增加计数数组...

    sort strategy for java

    在Java编程语言中,排序策略是处理数据结构和算法的重要组成部分。本文将深入探讨Java实现的几种主要排序算法,包括冒泡排序、插入排序、合并排序、快速排序和堆排序,以及如何通过分析器对这些排序算法进行性能比较...

    Java数据结构及算法实例:插入排序 Insertion Sort

    插入排序(Insertion Sort)是一种简单直观的排序算法,它的工作原理是通过构造一个有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用...

Global site tag (gtag.js) - Google Analytics