欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Java数据结构实例(冒泡、选择、插入、希尔排序)

程序员文章站 2022-03-10 10:51:13
冒泡排序:两两交换,交换完最大的值跑到了最后面,所以内层循环的数量不超过外层循环的次数 for (int i = 0,t; i < arr.length-1; i++) { for (int j = 0; j arr[j+1]){ t=arr[j]; arr[j]=ar...

冒泡排序:两两交换,交换完最大的值跑到了最后面,所以内层循环的数量不超过外层循环的次数

 for (int i = 0,t; i < arr.length-1; i++) { for (int j = 0; j <arr.length-1-i ; j++) { if (arr[j]>arr[j+1]){ t=arr[j]; arr[j]=arr[j+1]; arr[j+1]=t; } } } for (int c : arr) { System.out.println(c); }` 

选择排序:假设第一个最大值,从第二位开始(内层循环从i+1开始),遍历数组,比较后找到最大值,更新最大值的索引,最后把最大值放在本轮循环最后的位置(最大值已经在最后面了,所以内层循环每轮都要减一,也就是减i)。(选择排序也可以先找出最小值放在前面,假设第一个是最小值,从i开始遍历,找到最小的值,然后更新最小值索引,交换最小值和第一位的位置(最小值在第一位后,内层循环就要从i开始了))

 int[] arr = new int[]{54,4,75,6,21,9,5,7,44,22}; for (int i = 0,t; i <arr.length-1 ; i++) { int maxValIx=0; int maxIx = arr.length-1-i; for (int j = 1; j <=arr.length-1-i ; j++) { if (arr[maxValIx]<arr[j]){ maxValIx = j; } } if (maxIx!=maxValIx){//增加判断,减少循环次数 t=arr[maxIx]; arr[maxIx]=arr[maxValIx]; arr[maxValIx]=t; } } for (int c : arr) { System.out.println(c); } 

插入排序:拿出arr[i]赋值给t,j在i前面一位,比较arr[j]和t(arr[i])的值,若arr[j]大,往后挪,遇到小的不挪,把t插进去

 int [] arr = new int[]{14,12,13,64,5,6,57,8,91,10}; for (int i = 0,t,j; i <arr.length ; i++) { t=arr[i]; for ( j = i-1; j>=0&&arr[j]>t; j--) { arr[j+1]=arr[j]; } arr[j+1]=t; } for (int c : arr) { System.out.println(c); } 

希尔排序:希尔增量是arr.length/2,希尔增量不断缩减,构成第一个循环;第二个循环从第二个希尔区间的开头算起,一直跑到结尾;第三个循环是在for里面依次对比第二个希尔区间值和第一个希尔区间值的大小,若前一个更大,则执行循环里两个值交换代码。

 int [] arr = new int[]{14,112,13,64,15,6,57,1,8,91,10}; int N=arr.length,t; for (int h = N/2; h >0 ; h/=2) { for (int i = h; i <N ; i++) { for (int j = i; j>=h&&arr[j] <arr[j-h] ; j=j-h) { t=arr[j]; arr[j]=arr[j-h]; arr[j-h]=t; } } } for (int c : arr) { System.out.println(c); } 

本文地址:https://blog.csdn.net/xiaoxaoyu/article/details/108873613