首页 > 代码库 > 数组的高级（排序和查找）
数组的高级（排序和查找）
1.冒泡排序：相邻元素两两比较，大的向后方法，第一次完毕后，最大值就出现在了最大索引出。同理，继续，即可得到一个排好序的数组。
2.冒泡排序的规则：
1).两两比较，大的往后方法。
2).第一次比较完毕后，下一次比较的时候就会减少一个元素的比较。
3).第一次比较，有0个元素不比。
第二次比较，有1个元素不比。
第三次比较，有2个元素不比。
......
4).总共需要比较数组的长度-1次。
3.冒泡排序图解
4.代码实现
package cn;
/**
* 数组排序之冒泡排序
*/
public class ArrayDemo {
public static void main(String[] args) {
//定义一个数组
int[] arr = {24,69,80,57,33};
//遍历数组,数组排序前
printArray(arr);//[24, 69, 80, 57, 33]
//第一次比较
//arr.length -1为了防止越界
//arr.length -1 - 0 为了减少比较的次数
for (int i = 0; i < arr.length -1 - 0; i++) {
if(arr[i]>arr[i+1]){
int temp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = temp;
}
}
//第一次比较后的数组为
printArray(arr);//[24, 69, 57, 33, 80]
//第二次比较
//arr.length -1为了防止越界
//arr.length -1 -1 减少比较的次数
for (int i = 0; i < arr.length -1 -1; i++) {
if(arr[i]>arr[i+1]){
int temp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = temp;
}
}
//第二次比较后的数组为
printArray(arr);//[24, 57, 33, 69, 80]
//第三次比较
//arr.length -1为了防止越界
//arr.length -1 -2 减少比较的次数
for (int i = 0; i < arr.length -1 -2; i++) {
if(arr[i]>arr[i+1]){
int temp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = temp;
}
}
//第三次比较后的数组为
printArray(arr);//[24, 33, 57, 69, 80]
//第四次比较
//arr.length -1为了防止越界
//arr.length -1 -3 减少比较的次数
for (int i = 0; i < arr.length -1 -3; i++) {
if(arr[i]>arr[i+1]){
int temp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = temp;
}
}
//第四次比较的数组为
printArray(arr);//[24, 33, 57, 69, 80]
}
/**
* 遍历数组
* @param array
*/
public static void printArray(int[] array){
System.out.print("[");
for (int i = 0; i < array.length; i++) {
if(i == array.length -1){
System.out.println(array[i]+"]");
}else{
System.out.print(array[i]+", ");
}
}
}
}优化
package cn;
/**
* 数组排序之冒泡排序
*/
public class ArrayDemo {
public static void main(String[] args) {
//定义一个数组
int[] arr = {24,69,80,57,33};
//遍历数组,数组排序前
printArray(arr);//[24, 69, 80, 57, 33]
for (int i = 0; i < arr.length -1; i++) {//w外层控制的是比较的次数=数组的长度-1
for (int j = 0; j < arr.length - 1 - i; j++) {//内循环控制的是每次需要比较的元素
/**
* 第一次，是5个元素比较
* 第二次，是4个元素比较
* 第三次，是3个元素比较
* 第四次，是2个元素比较
* 第五次，是1个元素比较 不过 有这必要吗 没有 不需要比较 数组的元素已经排序了
*/
if(arr[j] > arr[j+1]){
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
//排序后的数组
printArray(arr);//[24, 33, 57, 69, 80]
}
/**
* 遍历数组
* @param array
*/
public static void printArray(int[] array){
System.out.print("[");
for (int i = 0; i < array.length; i++) {
if(i == array.length -1){
System.out.println(array[i]+"]");
}else{
System.out.print(array[i]+", ");
}
}
}
}5.选择排序
从0索引开始，依次和后面元素比较，小的往前方法，第一次完毕，最小值出现在了最小索引出。其他的同理，可以得到一个排好序的数组。
6.选择排序原理
7.选择排序的代码实现
package cn;
/**
* 数组排序之选择排序
*
*/
public class ArrayDemo2 {
public static void main(String[] args) {
//定义一个数组
int[] arr = new int[]{24,69,80,57,13};
//排序前的数组为
printArray(arr);//[24, 69, 80, 57, 13]
//第一次
for (int i = 1; i < arr.length; i++) {
if(arr[0] > arr[i]){
int temp = arr[i];
arr[i] = arr[0];
arr[0] = temp;
}
}
System.out.println("第一次排序后的数组");
printArray(arr);//[13, 69, 80, 57, 24]
//第二次
for (int i = 2; i < arr.length; i++) {
if(arr[1] > arr[i]){
int temp = arr[i];
arr[i] = arr[1];
arr[1] = temp;
}
}
System.out.println("第二次排序后的数组");
printArray(arr);//[13, 24, 80, 69, 57]
//第三次
for (int i = 3; i < arr.length; i++) {
if(arr[2] > arr[i]){
int temp = arr[i];
arr[i] = arr[2];
arr[2] = temp;
}
}
System.out.println("第三次排序后的数组");
printArray(arr);//[13, 24, 57, 80, 69]
//第四次
for (int i = 4; i < arr.length; i++) {
if(arr[3] > arr[i]){
int temp = arr[i];
arr[i] = arr[3];
arr[3] = temp;
}
}
System.out.println("第四次排序后的数组");
printArray(arr);//[13, 24, 57, 69, 80]
}
/**
* 遍历数组
* @param arr
*/
public static void printArray(int[] arr){
System.out.print("[");
for (int i = 0; i < arr.length; i++) {
if(i == arr.length -1){
System.out.println(arr[i]+"]");
}else{
System.out.print(arr[i]+", ");
}
}
}
}优化
package cn;
/**
* 数组排序之选择排序
*
*/
public class ArrayDemo2 {
public static void main(String[] args) {
//定义一个数组
int[] arr = new int[]{24,69,80,57,13};
//排序前的数组为
printArray(arr);//[24, 69, 80, 57, 13]
for (int i = 0; i < arr.length -1; i++) {//外层循环控制每次最小值的索引上的值进行比较
for (int j = i+1; j < arr.length; j++) {//内层循环将与外层循环的每次最小值的后一个索引上的值进行比较
if(arr[j] < arr[i]){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
System.out.println("排序后的数组：");
printArray(arr);//[13, 24, 57, 69, 80]
}
/**
* 遍历数组
* @param arr
*/
public static void printArray(int[] arr){
System.out.print("[");
for (int i = 0; i < arr.length; i++) {
if(i == arr.length -1){
System.out.println(arr[i]+"]");
}else{
System.out.print(arr[i]+", ");
}
}
}
}8.练习
package cn;
/**
* 把字符串中的字符进行排序
* 例如："dacgebf"
* 结果："abcdefg"
*
* 分析：
* 1.定义一个字符串
* 2.把字符串转换为字符数组
* 3.把字符数组进行排序
* 4.把排序后的儿子富数组转换为字符串
* 5.输出最后的字符串
*
*/
public class ArrayTest {
public static void main(String[] args) {
//方法一：使用冒泡排序
//定义一个字符串
String str = "dacgebf";
//把字符串转换为字符数组
char[] chs = str.toCharArray();
//把字符数组进行排序
bubbleSort(chs);
//把排序后的儿子富数组转换为字符串
String sortedStr = String.valueOf(chs);
//输出最后的字符串
System.out.println("排序后的字符串："+sortedStr);//排序后的字符串：abcdefg
//方法二：使用选择排序
String str2 = "dacgebf";
//把字符串转换为字符数组
char[] chas = str2.toCharArray();
//把字符数组进行排序
changeSort(chas);
//把排序后的儿子富数组转换为字符串
String sortedStr2 = new String(chas);
//输出最后的字符串
System.out.println("排序后的字符串："+sortedStr2);//abcdefg
}
/**
* 冒泡排序
* @param chs
*/
public static void bubbleSort(char[] chs){
for (int i = 0; i < chs.length -1; i++) {//外层控制的是比较的次数，是数组的长度-1
for (int j = 0; j < chs.length -1 -i; j++) {//内层循环控制的是每次比较的元素
//chs.length -1是为了防止数组越界
if(chs[j] > chs[j+1]){
char temp = chs[j];
chs[j] = chs[j+1];
chs[j+1] = temp;
}
}
}
}
/**
* 选择排序
* @param chs
*/
public static void changeSort(char[] chs){
for (int i = 0; i < chs.length-1; i++) {//外层控制的是每次循环的最小值的索引
for (int j = i+1; j < chs.length; j++) {//内层循环控制的是每次循环的最小值后面的数组中的元素的索引
if(chs[i] > chs[j]){
char temp = chs[i];
chs[i] = chs[j];
chs[j] = temp;
}
}
}
}
}9.二分查找
package cn;
/**
* 查找：
* 基本查找：数据元素无序（从头查到尾）
* 二分查找(折半查找)：数据元素有序
* 分析：
* A：定义最大索引和最小索引
* B:计算出中间索引
* c:拿中间索引的值和要查找的值进行比较
* 相等：就返回当前的中间索引
* 不相等：
* 大 左边找
* 小 右边找
* D:重新计算出中间索引
* 大 左边找
* max = mid -1
* 小 右边找
* max = mid + 1
* E:回到B
*/
public class ArrayDemo3 {
public static void main(String[] args) {
//定义一个数组
int[] arr = {11,22,33,44,55,66,77};
//调用方法
int index = getIndex(arr, 33);
System.out.println(index);//2
}
public static int getIndex(int[] arr,int value){
//定义最大索引和最下索引
int max = arr.length -1 ;
int min = 0;
//计算出中间索引
int mid = (max+min)/2;
//拿中间索引值和要查找的值进行比较
while(arr[mid] != value){
if(arr[mid] > value){
max = mid -1;
}else if(arr[mid] < value){
min = mid +1;
}
if(min > max){
return -1;
}
mid = (max+min)/2;
}
return mid;
}
}本文出自 “11831428” 博客，请务必保留此出处http://11841428.blog.51cto.com/11831428/1860358
数组的高级（排序和查找）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。