目录
1. 冒泡排序
Java内置排序Arrays.sort()
2.数组是否有序
3. 二分查找
4. 数组的拷贝
5. 数组转字符串
6. 数组逆序
7. 数组按奇偶排列
8. 找出出现一次的数字
1. 冒泡排序
给定一个整型数组, 实现冒泡排序(升序排序)
注意设置flg，如果前面循环中发现数组有序，则直接break终止循环
//冒泡排序
public class test {
public static void bubbleSort(int[] array) {
int length = array.length;
for (int i = 0; i < length-1; i++) {
//每趟都要置为false
boolean flg = false;
for (int j = 0; j < length-i-1; j++) {
if (array[j] > array[j+1]) {
int tmp = array[j];
array[j] = array[j+1];
array[j+1] = tmp;
flg = true;
}
}
if (flg == false) {
//没有交换
break;
}
}
}
public static void main(String[] args) {
int[] array = {15, 94, 56, 78, 12, 35};
System.out.println(Arrays.toString(array));
bubbleSort(array);
System.out.println(Arrays.toString(array));
}
}
Java内置排序Arrays.sort()
Arrays.sort(array); //直接执行，没有返回值
public static void main(String[] args) {
int[] arr = {9, 5, 2, 7};
Arrays.sort(arr);
System.out.println(Arrays.toString(arr));
}
2.数组是否有序
Arrays.sort(array); //直接执行，没有返回值
给定一个整型数组, 判定数组是否有序（递增）
因为判断的是array[i] 和 array[i + 1]的大小，因此在循环时只需for (int i = 0; i< array.length -1,i++)
//数组是否有序
public class test {
public static boolean isSort(int[] array) {
for (int i = 0; i < array.length-1; i++) {
if (array[i] > array[i+1]) {
return false;
}
}
return true;
}
public static void main(String[] args) {
int[] array1 = {15, 94, 56, 78, 12, 35};
int[] array2 = {1, 2, 3, 4, 5};
System.out.println(isSort(array1));
System.out.println(isSort(array2));
}
}
3. 二分查找
给定一个有序整型数组, 实现二分查找
//二分查找
public class test {
public static int binarySearch(int[] array, int key) {
int low = 0;
int hight = array.length-1;
while (low <= hight) {
int mid = (low + hight)/2;
if (array[mid] < key) {
low = mid+1;
} else if(array[mid] > key) {
hight = mid-1;
} else {
return mid;
}
}
return -1;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int[] array = {10, 27, 35, 46, 55, 67, 78, 88, 90, 100};
int key = sc.nextInt();
System.out.println(binarySearch(array, key));
}
}
4. 数组的拷贝
实现一个方法 copyOf, 对一个整型数组进行拷贝, 得到一个新的数组.
//数组的拷贝
public class test {
public static int[] copyOf (int[] array){
if (array == null) {
return null;
}
if (array.length == 0) {
return new int[0];
}
int[] ret = new int[array.length];
for (int i = 0; i < array.length; i++) {
ret[i] = array[i];
}
return ret;
}
public static void main(String[] args) {
int[] array = {1, 2, 3, 4, 5};
int[] ret = copyOf(array);
System.out.println(Arrays.toString(ret));
}
}
5. 数组转字符串
实现一个方法 toString, 把一个整型数组转换成字符串. 例如数组 {1, 2, 3} , 返回的字符串为 "[1, 2, 3]", 注意 逗号 的位置和数量.
//数组转字符串
public class test {
public static String toString(int[] array) {
if (array == null) {
return null;
}
if (array.length == 0) {
return "";
}
String s = "[";
for (int i = 0; i < array.length; i++) {
s += array[i];
if (i != array.length - 1) {
s += ", ";
}
}
return s += "]";
}
public static void main(String[] args) {
int[] array = {1, 2, 3, 4, 5};
System.out.println(toString(array));
}
}
6. 数组逆序
给定一个数组, 将里面的元素逆序排列
while（left < right）即可
//数组逆序
public class test {
public static void reverse(int[] array) {
int left = 0;
int right = array.length-1;
while (left < right) {
int tmp = array[left];
array[left] = array[right];
array[right] = tmp;
left++;
right--;
}
}
public static void main(String[] args) {
int[] array = {1, 2, 3, 4, 5};
reverse(array);
System.out.println(Arrays.toString(array));
}
}
7. 数组按奇偶排列
给定一个整型数组, 将所有的偶数放在前半部分, 将所有的奇数放在数组后半部分
//数组按奇偶排列
public class test {
public static void func(int[] array) {
int left = 0;//偶数
int right = array.length -1;//奇数
while (left < right) {
while (left < right && array[left] % 2 == 0) {
left++;
}
while (left < right && array[right] % 2 != 0) {
right--;
}
int tmp = array[left];
array[left] = array[right];
array[right] = tmp;
}
}
public static void main(String[] args) {
int[] array = {1, 2, 3, 4, 5, 6};
func(array);
System.out.println(Arrays.toString(array));
}
}
8. 找出出现一次的数字
有一组数据，只有一个数字是出现一次，其他是两次，请找出这个数字。
注意出现没有找到的情况。
先给数组排序，然后判断头尾是不是那个只出现了一次的数，是的话直接return
遍历i，判断其是否与前后相等，&&后和前后均不等则就是那个数，return
//找出现只出现了一次的数
public class test {
public static int findNum(int[] array) {
int num = -1;
if (array[0] != array[1]) {
return array[0];
}
if (array[array.length-1] != array[array.length-2]) {
return array[array.length-1];
}
for (int i = 1; i < array.length-2; i++) {
if(array[i] != array[i-1] && array[i] != array[i+1]) {
num = array[i];
}
}
return num;
}
public static void main(String[] args) {
int [] array = {1, 3, 2, 4, 2, 1, 4};
Arrays.sort(array);
System.out.println(findNum(array));
}
}
还有一种比较精妙的方法（异或）
其他数字都出现了两次，则自己异或自己为0；
因此直接拿0依次异或就可以了。
//用异或的方式,一个数字与0异或为自己本身，一个元素与自身异或结果为0，剩下的数字就是只出现一次的
public static int findNum1(int[] nums){
int ret=0;
for(int i=0;i
