Java数组的排序方式
2016-12-17 本文已影响119人
字节码
1.选择排序
将第0个位置元素与每一个元素进行比较，如果比第0个元素大，就交换位置
/**
* 直接排序(选择排序)
* 将一个数组中的元素，按照从大到小排序
*/
import java.nio.charset.MalformedInputException;
public class Test1 {
public static void main(String[] args) {
int[] arr = new int[6];
arr[0] = 1;
arr[1] = 10;
arr[2] = 29;
arr[3] = 3;
arr[4] = 399;
arr[5] = 31;
selectionShort(arr);
for (int i = 0; i<arr.length; i++) {
System.out.println(arr[i] + ",");
}
}
/// 选择排序方法
public static void selectionShort(int[] arr) {
/*
* 选择排序
*/
for (int j = 0; j<arr.length - 1; j++) {
for (int i = j; i < arr.length; i++) {
if (arr[i] > arr[j]) {
/// 交换位置
int temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
}
}
}
}
2.冒泡排序
/*
* 数组的冒泡排序:
* 如果要按照升序排序，将数组中相邻的两个元素进行比较，交换相邻数组的位置
*/
public class BubbleSort {
public static void main(String[] args) {
int[] arr = {1, 20, 30, 50, 3, 45};
bubbleSort(arr);
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i] + ",");
}
}
public static void bubbleSort(int[] arr) {
for (int j = 0; j < arr.length - 1; j++) { /// 控制遍历的次数
for (int i = 0; i < arr.length-1; i++) { /// 找出相邻最新元素，交换位置
if (arr[i] > arr[i + 1]) {
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
}
}
}
3.二分查找法:
前提：二分查找的前提是需要查找的数组必须是已排序的，我们这里的实现默认为升序
需求: 给定一个值，从数组中查找这个值所对应的索引
思路:
先定义3个变量分别记录数组最大的索引、最小的索引、中间的索引，
然后每次遍历数组时，用要查询值与中间索引对应的元素比较，
当要查询的值小于中间索引对应的元素时，缩小查找范围，让最大的索引等于中间的索引-1；
当要查询的值大于中间索引对应的元素时，缩小查找范围，让最小的索引等于中间的索引+1；
当要最大的索引小于最小的索引时，说明找不到要查询的值；
当要查询的值等于中间索引对应的元素时，即找到了，返回中间的索引即可；
/*
* 需求： 给定一个值，查找数组中这个值对应的索引
*/
public class DichotomySearch {
public static void main(String[] args) {
int[] arr = {10, 20, 30, 40, 50};
int target = dichotomySearch(arr, 40);
System.out.println(target);
}
public static int dichotomySearch(int[] arr, int target) {
// 1.定义3个变量，分别记录要查询的数组的最大索引、最小索引、中间索引
int max = arr.length - 1;
int min = 0;
int mid = (max + min) / 2;
// 2.遍历数组
while (true) {
if (target > arr[mid]) {
min = mid + 1;
} else if (target < arr[mid]) {
max = mid - 1;
} else if (target == arr[mid]) {
return mid;
}
if (max < min) {
return -1;
}
// 重新计算mid
mid = (max + min) / 2;
}
}
}
4.给定一个char类型的数组，将这个数组中的所有元素反转排序，比如原来是{'a', 'c', 'b'}; 要求结果是{'b', 'c', 'a'};
思路: 变量这个数组中的每一个元素，交换相邻两个数组元素的位置，
注意：已经交换过的就不要在交换了
/*
* 给定一个char类型的数组，反转数组中的每一个元素
*/
public class Demo1 {
public static void main(String[] args) {
char[] arr = {'a', 'b', 'c', 'd', 'e', 'f'};
invertedOrder(arr);
for (int j = 0; j < arr.length; j++) {
System.out.print(arr[j] + ",");
}
}
public static void invertedOrder(char[] arr) {
for (int j = 0; j < arr.length - 1; j++) {
for (int i = 0; i < arr.length - j - 1; i++) { // 减1是为了防止数组越界，减j是为了让已经排序过的就不再排序了
// 交换相邻两个数组元素的位置
char temp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = temp;
}
}
}
5.Arrays的简单使用
数组的工具类为Arrays
使用前需要导包import java.util.*;
将数组类型转换为字符串的函数toString();
对数组排序的方法Arrays.sort(arr);
查找某个元素在数组中的位置(二分查找发)Arrays.binarySearch(arr, 33);返回元素所在的索引值，如果找不到元素会返回负数
public class Demo {
public static void main(String[] args) {
/// 通过sun提供的接口对数组进行排序
int[] arr = {10, 20, 30, 33, 22, 11};
Arrays.sort(arr); /// sort内部使用的是选择排序
/// 通过sun提供的接口查找数组中的某个元素
int index = Arrays.binarySearch(arr, 33); /// binarySearch内部使用的是二分查找法
/// 将数组转换为字符串
String info = Arrays.toString(arr);
System.out.println("数组中的元素：" + info + "查找元素所在的索引:" + index);
}
}
6.二维数组的简单使用
二维数组可以看成以数组为元素的数组；
Java中二维数组的声明和初始化应按照从高维到低维的顺序进行.
public static void main(String[] args) {
/// 动态初始化二维数组
int[][] arr = new int[2][];
arr[0] = new int[3];
arr[1] = new int[4];
arr[0][0] = 10;
arr[0][1] = 20;
arr[0][2] = 22;
arr[1][0] = 54;
arr[1][1] = 98;
arr[1][2] = 22;
arr[1][3] = 13;
/// 遍历数组中每一个元素
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr[i].length; j++) {
System.out.println(arr[i][j] + ",");
}
System.out.println();
}
/// 静态二维数组
int[][] arr1 = {{10, 20, 11, 33}, {8, 11, 22, 19, 111}};
for (int i = 0; i < arr1.length; i++) {
for (int j = 0; j < arr1[i].length; j++) {
System.out.println(arr1[i][j] + ",");
}
System.out.println();
}
}
总结：Java数组的特点
1. 数组只能存储同一种 数据类型的数据。
2. 数组是会给存储到数组中 的元素分配一个索引值的，索引值从0开始，最大的索引值是length-1；
3. 数组一旦初始化，长度固定。
4. 数组中的元素与元素之间的内存地址是连续的。
