数组排序
目录
一. 冒泡排序
二. 选择排序
三. 优化选择排序
一. 冒泡排序
将数组元素按[从小到大排序] 为例
思路: 依次对临近的两个元素对比, 将最大值放在数组最后; 再将剩余的元素对比, 大值放在剩余元素的最后. . . 以此循环, 最后元素就是按从小到大排列.
1.1. 做之前, 先了解这个操作: 把数组的最大值放在末尾
将元素 1 和元素 2 对比, 如果元素 1 的值大, 则元素 2 和元素 1 的值互换(此时元素 2 为大值); 再让元素 2 和元素 3 对比. . ( 保留大值). . 元素 3 和元素 4 对比 . . . 依次类推, 对比完全部的元素后(因是按照当前元素和下一个元素进行的对比, 所以当前元素为倒数第二个元素时, 就可完成全部的元素对比, 也就是对比了[数组长度 - 1 次] ), 则最后的元素就是最大值;
- 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;
- }
1.2. [1.1] 的基础上, 将其余的元素按照从小到大循环排序:
使用[1.1] 的方法, 将剩下的元素再进行最大值的对比(对比的次数比[1.1] 的少一次, 就可进行剩余元素的对比); 按此思路循环即可(循环一次, 大值就放在[循环元素的] 后面; 当循环到第二个元素时, 第一个元素就是最小值, 也就是循环了[数组长度 - 1 次] ).
- int[] arr = {1,3,5,1,2,7,9};
- //2, 循环一次, 就将一个大值放在数组后面; 当循环到第二个元素时, 第一个元素就已经是最小值, 故循环[数组长度 - 1 次] 即可.
- for(int j = 0 ;j <arr.length - 1 ;j++){
- for (int i = 0; i < arr.length - 1 - j; i++) {
- //1, 若当前元素比下一个元素大, 则将这两个元素互换
- if(arr[i]> arr[i+1]){
- int temp = arr[i];
- arr[i] = arr[i+1];
- arr[i+1] = temp;
- }
- }
- }
- for (int i = 0; i <arr.length; i++) {
- System.out.print(arr[i]+" ");
- }
二. 选择排序法
将数组元素按[从小到大排序] 为例
思路: 将第一个元素与之后的元素对比, 若有值比其大的元素, 则将这两个元素互换(保证第一个元素为最小值); 然后第二个元素与之后的元素对比 . . . 依次循环.
2.1. 做之前, 先了解这个操作: 将数组的最小值放在最前面
思路: 将第一个元素, 与之和的元素挨个对比, 期间若有值比其大的元素, 则将这两个元素互换(循环到[数组长度 - 1 次] 后, 则完成所有元素的对比).
- for (int i = 0; i < arr.length - 1; i++) {
- // 如果第一个元素比之后的元素大, 则和其元素互换, 循环完毕后, arr[0]是数组的最小值.
- if(arr[0]> arr[i+1]){
- int temp = arr[0];
- arr[0] = arr[i + 1];
- arr[i + 1] = temp;
- }
- }
2.2. [2.1] 的基础上, 将其余的元素按照从小到大循环排序:
使用 [2.1] 的(内部) 循环后, 再将第二个元素与之后的所有元素进行对比 (因是第二元素个开始, 故循环的次数比[2.1] 少一次), 按此思路(外部) 循环即可(每次循环对比的次数, 都比上一次少一次)
分析 1:(外部)循环第一次, 用第一个元素和其他元素对比; 循环第二次, 用第二个元素与其他元素对比 . . . 故 (外部) 循环的次数[i] 与做对比的元素索引符合[arr[i]]
分析 2:(内部)循环对比的次数, 每次比上次少一次, 将外部循环的次数[i] , 符合内部循环的循环初始值.
- int[] arr = {1,3,5,1,2,7,9};
- for (int j = 0; j <arr.length; j++) {
- //2, 因每完成一次循环, 下次循环次数需要少一次; 外部循环的值给内部循环, 可达到该效果
- for (int i = j; i < arr.length - 1; i++) {
- //1, 如果第一个元素比之后的元素大, 则和其元素互换, 循环完毕后, arr[j]是其在内与之后元素中的的最小值.
- if(arr[j]> arr[i+1]){
- int temp = arr[j];
- arr[j] = arr[i + 1];
- arr[i + 1] = temp;
- }
- }
- }
三. 优化选择排序法
将数组元素按[从小到大排序] 为例
因选择排序法需要进行某元素与之后所有的元素对比, 并进行元素互换的过程, 若数组的长度很长, 则元素互换需要耗费较多资源
优化思路: 再选择排序法的基础上, 设置变量 index(代表起点对比元素的索引), 和变量 value(代表起点元素的值), 当出现比其值小的元素时, 将该元素的值和索引赋值给变量(赋值耗费的资源大大低于元素互换); 然后将代表最小值的变量索引与起点元素索引对比, 若不相同, 则将起点元素与最小值元素互换(这样循环下去, 以较少的元素互换次数, 即可完成排序).
- for (int i = 0; i <arr.length - 1; i++) {
- int index = i;
- int value = arr[i];
- // 若出现比起点元素值更好的元素, 将该元素的索引和值赋给起点元素变量.
- for (int j = i + 1; j < arr.length; j++) {
- if (value> arr[j]) {
- value = arr[j];
- index = j;
- }
- }
- // 若最小值的索引 (index) 与起点索引不同, 则将最小值的元素和起点元素互换
- if (i != index) {
- int temp = arr[i];
- arr[i] = arr[index];
- arr[index] = temp;
- }
- }
java 基础(16), 数组的高级应用 -- 冒泡排序, 选择排序
来源: http://www.bubuko.com/infodetail-2567306.html