记录一些常用排序算法
冒泡排序
两层嵌套循环，每次会通过两两比较交换位置来选出最大的一个数放在最后面，之后的遍历就不会遍历到最大值，所以外层循环控制遍历元素数量，里层循环判断大小，交换位置。
比如：
| 初始数组 | 3 , 9 , 7 , 6 , 1 , 5 , 2 , 4 , 8 , 0 |
|---|---|
| 第一次后 | 3 , 7 , 6 , 1 , 5 , 2 , 4 , 8 , 0 , 9 |
| 第二次后 | 3 , 6 , 1 , 5 , 2 , 4 , 7 , 0 , 8 , 9 |
| 第三次后 | 3 , 1 , 5 , 2 , 4 , 6 , 0 , 7 , 8 , 9 |
| 第四次后 | 1 , 3 , 2 , 4 , 5 , 0 , 6 , 7 , 8 , 9 |
| 第五次后 | 1 , 2 , 3 , 4 , 0 , 5 , 6 , 7 , 8 , 9 |
| 第六次后 | 1 , 2 , 3 , 0 , 4 , 5 , 6 , 7 , 8 , 9 |
| 第七次后 | 1 , 2 , 0 , 3 , 4 , 5 , 6 , 7 , 8 , 9 |
| 第八次后 | 1 , 0 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 |
| 第九次后 | 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 |
结束！
1 | public static void main(String[] args) { |
2 | //初始数组 |
3 | int nums[]=new int[]{3,9,7,6,1,5,2,4,8,0}; |
4 | for (int i = 0;i < nums.length-1; i++){ |
5 | //从第一个数开始与后面进行比较，循环结束后，下次遍历元素数量减1 |
6 | for (int j = 0; j < nums.length-i-1; j++) { |
7 | //如果前者大于后者，则两数交换 |
8 | if(nums[j]>nums[j+1]){ |
9 | nums[j]=nums[j]^nums[j+1]; |
10 | nums[j+1]=nums[j]^nums[j+1]; |
11 | nums[j]=nums[j]^nums[j+1]; |
12 | }else { |
13 | continue; |
14 | } |
15 | } |
16 | } |
17 | for (int i = 0; i < nums.length; i++) { |
18 | System.out.println(nums[i]); |
19 | } |
20 | } |
结果很理想
直接选择排序
同样两层嵌套循环，每次循环假定索引为0(第一个)的是最大值，每次将最大值和后面的值比较，如果有更大的，则将更大的值的索引记为最大值的索引，最终选出最大的一个值与最后面的值交换。
初始数组：3 , 9 , 7 , 6 , 1 , 5 , 2 , 4 , 8 , 0
代码：
1 | public static void main(String[] args) { |
2 | //初始数组 |
3 | int nums[]=new int[]{3,9,7,6,1,5,2,4,8,0}; |
4 | for (int i = 0; i < nums.length; i++) { |
5 | //int max=nums[0]; |
6 | int max_index=0; |
7 | for (int j = 0; j < nums.length-i; j++) { |
8 | //如果当前元素大于最大值，则令当前值为最大值 |
9 | if(nums[j]>=nums[max_index]){ |
10 | max_index=j; |
11 | }else { |
12 | continue; |
13 | } |
14 | } |
15 | if(max_index!=nums.length-i-1) { |
16 | nums[max_index] = nums[max_index] ^ nums[nums.length - i - 1]; |
17 | nums[nums.length - i - 1] = nums[max_index] ^ nums[nums.length - i - 1]; |
18 | nums[max_index] = nums[max_index] ^ nums[nums.length - i - 1]; |
19 | } |
20 | List ns=new ArrayList(); |
21 | for (int x = 0; x < nums.length; x++) { |
22 | ns.add(nums[x]); |
23 | } |
24 | System.out.println(ns); |
25 | } |
26 | } |
直接插入排序
假定第一个元素为一个已排序数组，后面的元素逐一与该数组最大值比较，如果大于最大值，接在后面且数组长度+1，小于则往前挪到合适位置。
代码：
1 | public static void main(String[] args) { |
2 | //初始数组 |
3 | int nums[] = new int[]{3, 9, 7, 6, 1, 5, 2, 4, 8, 0}; |
4 | for (int i = 1; i < nums.length; i++) { |
5 | //如果当前元素大于已排序数组最大值，接到数组后面且长度+1，小于则往前挪 |
6 | if(nums[i]<nums[i-1]){ |
7 | //循环比较 |
8 | for (int j = i; j >0 ; j--) { |
9 | if(nums[j]<nums[j-1]){ |
10 | //往前挪一位 |
11 | nums[j]=nums[j]^nums[j-1]; |
12 | nums[j-1]=nums[j]^nums[j-1]; |
13 | nums[j]=nums[j]^nums[j-1]; |
14 | }else { |
15 | break; |
16 | } |
17 | } |
18 | List ns=new ArrayList(); |
19 | for (int x = 0; x < nums.length; x++) { |
20 | ns.add(nums[x]); |
21 | } |
22 | System.out.println(ns); |
23 | }else { |
24 | continue; |
25 | } |
26 | } |
27 | for (int i = 0; i < nums.length; i++) { |
28 | System.out.println(nums[i]); |
29 | } |
30 | } |
