数据结构相关的内容在这里。
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程序员应该熟悉的基本工具。 1. **冒泡排序（Bubble Sort）** 冒泡排序是一种简单的排序算法，通过重复遍历数组，比较相邻...
1. 排序算法：冒泡排序、选择排序、插入排序、快速排序、归并排序等，它们用于将数据按特定顺序排列。 2. 搜索算法：线性搜索、二分搜索、深度优先搜索（DFS）和广度优先搜索（BFS）等，用于在数据集中查找目标元素...
2. Java常用算法和数据结构：冒泡排序、选择排序、插入排序、链表、树等。 3. Java网络编程基础知识：TCP/IP协议、Socket编程、HTTP协议等。 4. Java Web开发基础知识：Servlet、JSP、JavaBean、MVC模式等。 本书...
8. **排序算法**：包括冒泡排序、插入排序、选择排序、快速排序、归并排序、堆排序等，了解它们的原理和性能特点。 9. **搜索算法**：如深度优先搜索（DFS）和广度优先搜索（BFS），以及在图中应用这些算法的方式。...
在Java中，策略模式可以应用于排序算法、加密算法、 compression算法等场景。 2. 观察者模式（Observer Pattern） 观察者模式是一种行为型设计模式，定义了一对多的依赖关系，使得一个对象的状态改变能够自动通知...
本项目涵盖了数据结构中的七个重要的排序算法，选择，插入，冒泡，归并，希尔，快速和堆排序，可实现任何的List类型和数组类型，进行排序，除String类型外都可以进行排序，为使用开发者和学习者使用这七种经典算法...
【标题】：“毕业设计-路径推荐算法的设计与实现（java版本）.zip”指的是一个包含毕业设计项目的压缩文件，该项目专注于路径推荐算法的开发，并采用了Java编程语言。 【描述】：“计算机类毕业设计源码”表明这是...
分类文档 基础原则 六大设计原则 创建模式 单例模式 简单工厂模式 工厂方法模式 抽象工厂模式 原型模式 ...结构与算法 ...排序与查找算法 二叉树与多叉树 应用场景 RSA算法签名验签流程 树结构业务应用
这本《Java数据结构和算法》书很经典，市面上数据结构的实现很多都是用C语言实现的，而这本书是用Java实现的，浅显易懂，其中有排序，链表，树，图等等数据结构的实现，如果你比较擅长Java，同时希望用Java来实现...
【压缩包子文件的文件名称】"LightningSort-split_file" 这个文件名可能是参赛者自创的一种快速排序算法，或者是对现有排序算法（如快速排序）的改进版。"LightningSort"可能是一个命名，象征快速和高效，暗示该排序...
5. **排序算法**：常见的排序算法有冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序等。每种算法都有其适用场景，理解它们的工作原理对于优化代码性能至关重要。 6. **对象和属性**：在学生成绩管理系统...
熟悉数组、链表、堆栈、队列、哈希表和二叉树等基本数据结构，以及排序算法（如插入、冒泡、快速、堆、合并排序）和查找算法（如顺序、二分查找）。同时，理解算法的时间和空间复杂度分析，以及递推、递归、穷举、...
10. **编程实践**：使用C++、Java、Python等语言实现算法，掌握良好的编程规范，提高代码的可读性和可维护性。 虽然标题提示了压缩包内容可能存在不足，但在实际学习过程中，应参考高质量的教材、论文和在线资源，...
7. **算法实现**：练习题4、7、16、17、18、19、22、29和30要求编写算法来解决特定问题，比如求质数、找最大最小值、排序、计算梯形面积、输出九九乘法表、解决鸡兔同笼问题、计算购买鸡的方案等。 8. **异常处理**...
9. **算法与数据结构**：虽然Java面试通常不会深入到算法竞赛级别，但基础的排序算法（冒泡、选择、插入、快速、归并）、查找算法（二分查找、哈希查找）以及常用数据结构（链表、队列、栈、树、图）的知识是必备的...
5. **数据结构与算法**：在Java编程中，熟练掌握数据结构（如数组、链表、树、图等）和算法对于高效处理大数据至关重要。练习题可能涵盖排序、查找、图遍历等常见问题。 6. **集合框架**：Java集合框架包括接口（如...
1. **算法基础**：ACM竞赛的核心是算法，包括排序、搜索、图论、动态规划、贪心算法等。学习笔记可能包含了这些基本算法的实现和应用实例，帮助初学者建立坚实的算法基础。 2. **数据结构**：熟悉链表、树、堆、...
2. **排序算法**：基础的排序算法包括冒泡排序、选择排序和插入排序，它们的时间复杂度分别是O(n^2)。快速排序、归并排序和堆排序是更高效的排序算法，时间复杂度分别为O(nlogn)。基数排序则适用于特定场景，如整数...
8. **新闻分类与搜索功能**：源码可能包含对新闻进行分类的逻辑，以及实现搜索功能的代码，这涉及到数据筛选和排序算法。 9. **版本控制**：文件名cniao5-news-master暗示了使用Git进行版本控制，源码可能包含多个...