- 一、排序
- 1.1冒泡排序:
- 1.2选择排序
- 1.3插入排序
升序
1、相邻两个数比较,小的在前,大的在后,如果不符合,就交换
2、直到不需要再交换为止
长度为6时,第一趟:比较5次,挑出1个最大数
第二趟:比较4次,挑出2个最大数
第三趟:比较3次
第四趟:比较2次
第五趟:比较1次
外层:趟数
内层:比较的次数
public class Demo01MaoPao {
public static void main(String[] args) {
int[] arr = {13, 2, 5, 4, 8, 156, 78, 14};
for (int i = 0; i < arr.length - 1; i++) {
boolean flag = false;//true 交换过 false 没有交换过
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
flag = true;
}
}
//没有发生交换过,已经有序,排序可以结束
if (!flag){
break;
}
}
for (int i : arr) {
System.out.print(i + " ");
}
}
}
public class Demo02MaoPaoJiang {
public static void main(String[] args) {
int[] arr = {1, 2, 58, 7, 15, 123};
for (int i = 0; i < arr.length - 1; i++) {
boolean flag = false; //交换为true 没有交换为false
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] < arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
flag = true;
}
}
//判断有没有交换,如果有序,排序结束
if (!flag){
break;
}
}
for (int i : arr) {
System.out.print(i+" ");
}
}
}
1.2选择排序
依次挑选其后数据中的一个最小值的位置,与当前数据交换
1.3插入排序从第二个数开始,把当前数插入到前面的序列中,使数列仍然有序。直到最后一个数据插入完成。
public static void main(String[] args) {
int[] nums = {71, 2, 44, 23, 13, 9};
for (int j = 1; j < nums.length; j++) {
int n = nums[j];
//1、确定插入点的位置index
int index = j;
for (int i = 0; i < j; i++) {
if (nums[i] > nums[j]) {
index = i;
break;
}
} //优化, index == j,不用移动
if (index == j) {
continue;
} //2、[j - 1, index]依次往后移
for (int i = j - 1; i >= index; i--) {
nums[i + 1] = nums[i];
} //3、nums[index] = n
nums[index] = n;
}
for (int num : nums) {
System.out.print(num + " ");
}
}
public class Demo03ChaRu {
public static void main(String[] args) {
int[] arr = new int[6];
arr[0] = 78;
arr[1] = 68;
arr[2] = 58;
arr[3] = 38;
arr[4] = 28;
int a = 100;
//1、确定插入点的位置,默认插入到最后
int index = arr.length - 1;
for (int i = 0; i < arr.length - 1; i++) {
//判断插入的位置,如果所有数都大于a,a就在最后
if (arr[i] < a) {
index = i;
break;
}
}
//2、arr.length-2后面的依次往后挪 [arr.length-2,index]
//倒叙往前找
for (int i = arr.length - 2; i >= index; i--) {
arr[i + 1] = arr[i];
}
//3、arr[index] = a
arr[index] = a;
for (int i : arr) {
System.out.print(i + " ");
}
}
}
作业
public class Work01 {
public static void main(String[] args) {
char[] arr = {'m', 'b', 'p', 'f', 'a', 'u', 'z'};
for (int i = 0; i < arr.length - 1; i++) {
boolean flag = false;//true 交换过 false 没有交换过
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]){
char temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
flag = true;
}
}
if (!flag){
break;
}
}
for (char c : arr) {
System.out.print(c+" ");
}
}
}
public class Work02 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("请输入一个字符:");
char[] arr ={'a','b','c','e','f','p','u','z',0};
char c = sc.next().charAt(0);
//1、确定插入点的位置,默认插入到最后
int index = arr.length-1;
for (int i = 0; i < arr.length - 1; i++) {
if (arr[i] > c){
index = i;
break;
}
}
//2、arr.length-2后面的依次往后挪 [arr.length-2,index]
//倒叙往前找
for (int i = arr.length - 2;i >= index; i--) {
arr[i + 1] = arr[i];
}
//3、arr[index] = a
arr[index] = c;
for (char a : arr) {
System.out.print(a+" ");
}
}
}
public class Work03 {
public static void main(String[] args) {
int[] arr = {1, 2, 3, 10, 100, 10000};
int len = arr.length;
int count = 0;//倒叙计数器
int count1 = 0;//正序计数器
for (int i = 0; i < len - 1; i++) {
//如果现在的值始终比后面的值大 倒叙计数器+1
if (arr[i] >= arr[i + 1]) {
count++;
}
//如果现在的值始终比后面的值小 正序计数器+1
if (arr[i] <= arr[i + 1]) {
count1++;
}
}
if (count1 == len - 1 || count == len - 1) {
System.out.println("此数组有序");
} else {
System.out.println("此数组无序");
}
}
}



