数据结构相关的内容在这里。
package sort;
import java.util.Arrays;
public class ArraySorter {
/**
* int数组的排序工具 复习五种排序方法： 交换排序 插入排序 选择排序 归并排序 分配排序
* 相应方法都是用来复习面试的,不讨论数据量和数据大小等问题
* 菜鸟收集整理之作
* @author Peter Zhang
*/
//private static int[] arr = { 5, 9, 8, 7, 2, 4, 1, 3, 0, 6 };//待测数组
private static int[] arr = {1234,5425,38,35,46,13,89,356,123,78963,51,62};
public static void main(String[] args) {
System.out.println("待测数组");
print(arr);
//Arrays.sort(arr);
bubbleSort(arr);
//bubbleSort2(arr);
// quickSort(arr);
// insertSort(arr);
// shellSort(arr);
// shellSort2(arr);
// selectSort(arr);
// heapSort(arr);
// mergeSort(arr);
//radixSort(arr);
//radixSort2(arr);
print(arr);
}
// 显示打印的方法
private static void print(int[] arr) {
for (int i : arr) {
System.out.print(i + " ");
}
System.out.println();
}
// 交换元素的方法
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// 交换排序
/**
* 冒泡排序 数组中相邻左右两个元素相互比较,大的向后
*
* @param arr
*/
public static void bubbleSort2(int[] arr) {
for (int i = 0; i < arr.length; i++) {
for (int j = i + 1; j < arr.length - 1; j++) {
if (arr[i] > arr[j]) {
swap(arr, i, j);
}
}
}
}
public static void bubbleSort(int[] arr){
for(int i=0;i<arr.length;i++){
for(int j=arr.length-1;j>i;j--){
if(arr[j] <arr[j-1]){
swap(arr, j, j-1);
}
}
}
}
/**
* 快速排序 选出一个关键字,比他小的放到他的左边,大的放到右边, 设置两个指针,同时与关键字进行比较。
* 先确定中间位置的数(关键字)key一般都是第一个元素以及开始元素begin和结束元素end
* 再从右向左递减index,如果有元素比中间数小,就放在左边,和左边begin元素交换,begin+1
* 再从左向右递增index,如果有元素比中间数大,就放在右边,和右边的end元素交换,end+1 再递归左边和右边
*
* @param arr
* @param begin
* @param end
*/
private static void quick(int[] arr, int begin, int end) {
int i = begin;
int j = end;
if (i < j) {
int key = arr[i];
while (j > i) {
while (j > i && arr[j] > key) {// 右边递减寻找比关键字小的元素
j--;
}
if (j > i) {// 找到比关键字小的元素 下标为j
arr[i++] = arr[j]; // 和左边的元素交换 左边元素递增
}
while (j > i && arr[i] < key) {// 左边递增寻找比关键字大的元素
i++;
}
if (j > i) {// 找到比关键字大的元素 下标为i
arr[j--] = arr[i]; // 再右边递减寻找比关键字小的元素
}
}
arr[i] = key;
quick(arr, begin, j - 1);// 递归key左边
quick(arr, j + 1, end);// 递归key右边
}
}
// 外部方法
public static void quickSort(int[] arr) {
quick(arr, 0, arr.length - 1);
}
// 插入排序
/**
* 直接插入排序 左右分成两个部分,右边第一个元素和左边所有元素比较,小就交换,大就不变
*
* @param arr
*/
public static void insertSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
for (int j = 0; j < i; j++) {
if (arr[j] > arr[i]) {
swap(arr, i, j);
}
}
}
}
/**
* 希尔排序 先设定一个增量(间隔),再根据增量分组,每个分组排序；再分组,再排序
*
* @param arr
*/
public static void shellSort(int[] arr) {
int len = arr.length;
for (int increment = len / 2; increment > 0; increment /= 2) {// 分组
for (int i = increment; i < len; i++) {
if (arr[i] < arr[i - increment]) {// 增量间隔的两个数,大的放后,小的放前
for (int j = 0; j < i; j += increment) {
if (arr[j] > arr[i]) {
swap(arr, i, j);
}
}
}
}
}
}
public static void shellSort2(int[] arr) {
int len = arr.length;
int j;
for (int increment = len / 2; increment > 0; increment /= 2) {
for (int i = increment; i < len; i++) {
int temp = arr[i];
for (j = i - increment; j >= 0 && arr[j] > temp; j -= increment) {
arr[j + increment] = arr[j];
}
arr[j + increment] = temp;
}
}
}
// 选择排序
/**
* 直接选择排序 每次选择一个最小的
*
* @param arr
*/
public static void selectSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int min = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[min] > arr[j]) {
min = j;
}
}
if (min != i) {
swap(arr, i, min);
}
}
}
/**
* 堆排序 大顶堆排序 k0 k1 k2 k3 ……kn 利用大顶堆父节点比子节点大的原理,
* 先构造一个大顶堆,调整它保证根节点的元素是最大的
* 交换根节点和最后一个元素,移除最后一个元素,调整length-1个元素的堆,保持结构；
* 再交换此时的根节点和此时的最后一个元素,再移除此时的最后一个元素,调整剩下的堆；
* 以此类推,直到就剩根节点
*
* @param arr
*/
public static void heapSort(int[] arr) {
// 创建大顶堆堆 从最后一个父节点开始向根递减
int n = arr.length - 1; // 最后一个元素的index
for (int i = (n - 1) / 2; i > 0; i--) {
heapify(arr, i, n);// 从最后一个根节点开始调整堆
}
for (int i = n; i > 0; i--) {
swap(arr, i, 0);// 交换根和最后一个元素,n-1
heapify(arr, (i - 1 - 1) / 2, i - 1);// 从最后一个根节点开始调整
}
}
/**
* 调整堆 顶为0 左子节点为2i+1 从最后一个根节点开始调整堆的结构
*
* @param arr
* @param index 最后一个父节点
* @param n 最后一个元素的下标
*/
private static void heapify(int[] arr, int index, int n) {// n lastIndex
if (n == 0) {// 根节点 不调整
return;
}
for (int i = index; i >= 0; i--) {
int left = 2 * i + 1;// 左子节点
if (left < n) {// 有右子节点
if (arr[left] < arr[left + 1]) {
left++; // 方便在有右子节点的时候用left下标表示
}
}
if (arr[left] > arr[i]) {// 子节点比父节点大,交换
swap(arr, i, left);
}
}
}
// 归并排序
/**
* 归并排序 把待排序序列分为若干个子序列,每个子序列是有序的,
* 再把有序子序列合并为整体有序序列
*
* @param arr
*/
public static void mergeSort(int[] arr) {
merge(arr, 0, arr.length - 1);
}
// 分治法 自顶向下 递归分割数组并归并
private static void merge(int[] arr, int begin, int end) {
if (begin < end) {
int middle = (begin + end) / 2;
merge(arr, begin, middle);// 分割左边部分
merge(arr, middle + 1, end);// 分割右边部分
doMerge(arr, begin, middle, end);// 归并成一个有序的区间
}
}
// 归并
private static void doMerge(int[] arr, int begin, int middle, int end) {
int[] tmp = new int[arr.length];// 临时数组
int temp = begin;// 临时数组下标
int copy = begin;// 数组复制下标
int right = middle + 1;
while (begin <= middle && right <= end) {// 两部分从左边开始互相比较
if (arr[begin] <= arr[right]) {// 小的元素放入临时数组
tmp[temp++] = arr[begin++];
} else {
tmp[temp++] = arr[right++];
}
}
// 剩下的元素接着复制到临时数组中
while (begin <= middle) {
tmp[temp++] = arr[begin++];
}
while (right <= end) {
tmp[temp++] = arr[right++];
}
// 复制数组
while (copy <= end) {
arr[copy] = tmp[copy++];
}
}
// 分配排序
// 基数排序
/**
* int[] 单关键字十进制 基数就是10 循环装箱的次数就是数组中最大数的位数
* 用一个容量为 10*待测数组长度 的二维数组存放数据 new int[radix][arr.length]
* 即 10行 arr.length列的规则矩阵,每一行分别是序号为0-9的箱子
* 第一次循环装入个位数字与箱子序号数字对应的元素
* 再从0号箱子开始到9号箱子结束把依次所有元素装进数组中
* 第二次为十位
* 再从0号箱子开始到9号箱子结束把依次所有元素装进数组中
* 以此类推直到数组中最大数的最高位
* @param arr
*/
public static void radixSort(int[] arr) {
int len = arr.length;
int radix = 10;
int d = getMax(arr);// 最大数的位数
int[][] temp = new int[radix][len];//序号为0-9的箱子
int[] count = new int[radix];//箱子中元素的计数器
for (int m=0,n=1;m<d;m++,n *=radix) {//从个位到最大数的最高位
for (int i = 0; i < len; i++) {
int digit = (arr[i] / n % radix);//元素当前位的数值,对应箱子序号
temp[digit][count[digit]++] = arr[i];//把元素放入对应的箱子中
//count[digit]++; //对应序号箱子的计数器加1
}
int k=0; //数组下标,依次,
for (int i = 0; i < radix; i++) {
if (count[i] != 0){
for (int j = 0; j < count[i]; j++) {
arr[k] = temp[i][j];
k++;
}
}
count[i] = 0;
}
}
}
/**
* http://blog.csdn.net/skylinesky/article/details/6612119
* @author skylinesky
*/
public static void radixSort2(int[] array) {
int d = getMax(arr);
int radix = 10;
int[] temp = new int[arr.length];
int[] count = new int[radix];
int length = array.length;
int divide = 1;
for (int i = 0; i < d; i++) {
System.arraycopy(array, 0,temp, 0, length);
Arrays.fill(count, 0);
// for (int j = 0; j < array.length; j++) {
// temp[j] = arr[j];
// }
// for (int j = 0; j < count.length; j++) {
// count[j] = 0;
// }
for (int j = 0; j < length; j++) {
int tempKey = (temp[j] / divide) % radix;
count[tempKey]++;
}
for (int j = 1; j < radix; j++) {
count[j] = count[j] + count[j - 1];
}
// 个人觉的运用计数排序实现计数排序的重点在下面这个方法
for (int j = length - 1; j >= 0; j--) {
int tempKey = (temp[j] / divide) % radix;
count[tempKey]--;
array[count[tempKey]] = temp[j];
}
divide = divide * radix;
}
}
private static int getMax(int[] arr) {
int max = 0;
for (int i : arr) {
if (i > max) {
max = i;
}
}
return (max+"").length();
}
}
分享到：
相关推荐
java排序算法使用及场景说明 文档后面有一些别人的链接，多在google上搜索Java排序算法，及维基百科上面也有很全的算法介绍。
java实现的常用的几种基本排序算法，插入、交换、选择、归并
Java排序算法实现 Java排序算法实现 Java排序算法实现
Java排序算法代码.
java排序算法java排序算法插入选择冒泡java排序算法插入选择冒泡
实现合并排序，插入排序，希尔排序，快速排序，冒泡排序，桶排序算法的java实现。
Java排序算法 Java排序算法.rar
尚硅谷Java排序算法PPT
Java所有排序算法大全 Java所有排序算法大全 Java所有排序算法大全 Java所有排序算法大全
该工具包含有Java一些比较常见的排序算法和查找算法。 排序算法包括：冒泡排序、选择排序 、插入排序、希尔排序、快速排序、归并排序、基数排序(桶排序) 查找算法包括：线性查找、二分查找、插值查询、斐波那契...
Java排序算法 Java排序算法 Java排序算法
Java各种排序算法代码.rar
java产生多个随机数写入文件中，比较四种排序算法的效率
国外牛人的排序算法，内容丰富，适合初学者，爱挑战脑力的童鞋。
Java 排序算法大结合， 都是Java程序说明，希望对大家有用的
JAVA排序汇总,java应用中一些比较经典的排序算法
java排序算法-大全.rar 集合了多种java排序算法
快速排序等经典排序算法C++、Java、python等版本 快速排序等经典排序算法C++、Java、python等版本 快速排序等经典排序算法C++、Java、python等版本 快速排序等经典排序算法C++、Java、python等版本 快速排序等经典...
Java常见排序算法源码集，包括了字符、数字、数组的常用排序算法，是初学者非常不错的Java排序参考代码。
Java排序算法实现资源 这个资源是关于Java中排序算法实现的简单示例。排序算法是计算机科学中的基础概念，用于按升序或降序排列数据集。这里提供了两种常见的排序算法实现：冒泡排序和选择排序。 冒泡排序（Bubble ...