数组的排序（冒泡排序、选择排序、插入排序）

冒泡排序相邻比较并交换思路通过重复遍历数组依次比较相邻元素若前面的元素比后面的元素大则交换位置每一轮遍历都会让当前未排序部分最大的元素浮到末尾算法步骤从第一个元素开始比较相邻的两个元素如果左边元素右边元素则交换它们的位置继续比较下一对相邻元素直至末尾最大的元素会被移动到最后一个位置忽略已排好序的最后一个元素重复以上步骤直到整个序列有序//冒泡排序 int[] arr1 {10, 6, 3, 8, 9, 7, 2, 1, 5, 4}; for (int j 0; j arr1.length - 1; j) { int c 0; for (int i 0; i arr1.length - 1-j; i) { if (arr1[i] arr1[i 1]) { //交换 int temp1 arr1[i]; arr1[i] arr1[i 1]; arr1[i 1] temp1; c; } } if (c 0) { break; } System.out.println(第 j 次 Arrays.toString(arr1)); } System.out.println(完成排序 Arrays.toString(arr1));外层循环j控制轮数最多n-1轮内层循环i从0到n-1-j减去已确定的最大元素比较范围逐渐缩小c记录交换次数若c0代表没有交换数组已排好序选择排序选择最小值再交换思路每次从待排序的序列中找到最小元素将其与未排序的第一个元素交换位置此方法通过选择最小值一次交换到位算法步骤在未排序部分中找到最小元素的下标将最小元素与未排序部分的第一个元素交换位置将未排序部分范围缩小一位重复以上步骤直至所有元素排好序//选择排序 int[] arr2{40,18,22,1,9,38,5,8,47,14}; for(int i0;i arr2.length;i){ int minIndexi;//假设当前位置就是最小值位置 //在i1到末尾之间找真正的最小值下标 for(int ji1;jarr2.length;j){ if(arr2[j]arr2[minIndex]){ minIndexj; } } //如果最小值不是当前位置就交换 if(minIndex!i){ int temp2arr2[i]; arr2[i]arr2[minIndex]; arr2[minIndex]temp2; } System.out.println(第i次Arrays.toString(arr2)); } System.out.println(完成排序Arrays.toString(arr2));外层循环i遍历数组所有元素表示当前要放置最小元素的位置内层循环j遍历未排序部分找到真正的最小值下标minIndex若minIndexi则将arr2[i]与 arr2[minIndex] 交换位置插入排序将元素插入有序序列思路将序列分为未排序和已排序两个部分每次从未排序部分取出一个元素插入到已排序部分的合适位置算法步骤从第二个元素开始在已排序部分从后向前扫描如果已排序部分的元素大于当前元素则将该元素向后移动一位重复上一步骤直到找到已排序部分中小于或等于当前元素的位置将当前元素插入该位置重复以上步骤直到所有元素被排好序//插入排序 int[] arr3{32,4,47,28,0,13,27,36,20,14}; for(int i0;iarr3.length;i){ int currentarr3[i]; int ji-1; //已排序部分的最右边开始向左扫描只要遇到比 current 大的元素就把它向右移动一位 while(j0arr3[j]current){ arr3[j1]arr3[j];//将排序后的元素向右移动一位 j--; } arr3[j1]current; System.out.println(第i次Arrays.toString(arr3)); } System.out.println(完成排序Arrays.toString(arr3));