java自学——排序（冒泡、选择、插入、二分查找）

• 冒泡排序
• • 原理
  • 原理示例
  • 代码示例：
• 选择排序
• • 原理
  • 原理示例
  • 代码示例：
• 直接插入排序
• • 原理
  • 原理示例：
  • 代码示例
• 二分查找
• • 原理

假设有一组没有规律数列进行排序，排序的方式如下：

• 比较相邻的元素，假如第一个比第二个大，就交换他们两个
• 对每一对相邻元素做同样的工作，从第一对到结尾的最后一对进行循环比较，最终，最后的元素应该会是最大的数
• 针对所有的元素重复以上的步骤，除了最后一个
• 持续每次对越来越少额元素重复以上的步骤，直到没有任何一对数据需要比较
• 相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法

11,22,34,8,45,0,12 序列
11,22,8,34,0,12,45 第一次比较，前后比较，前面比后面大就交换，比较6次
11,8,22,0,12,34 最后一个数 不需要交换，比较5次
8,11,0,12,22 最后两个数 不需要交换，比较4次
8,0,11,22 最后三个数 不需要交换，比较3次
0,8,11 最后四个数 不需要交换，比较2次
0,8 最后五个数 不需要交换，比较1次

package class_0921;

public class class_paixu {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] nums = {11,22,34,8,45,0,12,45};
		paixu(nums);
	}
	public static void paixu(int[] data_list){
		int length_data = data_list.length;
		int a = data_list[0] ;
		//外循环控制轮数，比较次数等于长度减一
		for(int i=0;i data_list[j+1]){
					data_list[j+1] = data_list[j+1]+data_list[j];
					data_list[j] = data_list[j+1]-data_list[j];
					data_list[j+1] = data_list[j+1]-data_list[j];
				}
			}
		}
		for(int n:data_list){
			System.out.println(n);
		}
	}

}

• 将第一个元素作为最小/最大值，然后将循环中比第一个元素小的数值下标记录下来，比较完后交换一次
• 选择排序不是稳定的排序方法
• 通俗的说：先插找位置，记下下标，然后直接交换
• 选择排序比冒泡排序的效率要高

11,22,34,8,45,0,12 序列
0,11,22,34,8,45,12 第1轮，全部比较，比较6次，最小值放在第一位
0,8,11,22,34,45,12 第2轮，后六位比较，比较5次，最小值放在第二位
0,8,11,22,34,45,12 第3轮，后五位比较，比较4次，最小值放在第三位
0,8,11,12,22,34,45 第4轮，后四位比较，比较3次，最小值放在第四位
0,8,11,12,22,34,45 第5轮，后三位比较，比较2次，不用调换位置
0,8,11,12,22,34,45 第6轮，后二位比较，比较1次，不用调换位置

package class_0921;

public class class_select_paixu {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] nums = {11,22,34,8,45,0,12,45};
		select(nums);
	}
	public static void select(int [] data_list){
		int minindex = 0;//用于记录每次比较的最小值的下标
		int dlen = data_list.length;
		for (int i = 0; i data_list[j]){
					minindex =j;
				}
			}
			//判断需要交换数的下标是否为自己；如果是自己，就不需要进行交换
			if(minindex !=i){
				data_list[minindex]=data_list[minindex]+data_list[i];
				data_list[i] =data_list[minindex]-data_list[i];
				data_list[minindex] = data_list[minindex]-data_list[i];
			}
		}
		//输出结果
		for(int n:data_list){
			System.out.println(n);
		}
	}

}

• 原理：从后往前找到合适的位置后插入
• 每步将一个待排序数值记录下来，按其顺序码大小插入到前面已经排序的子序列的合适位置
• 从后往前找到合适位置后，直到全部插入顺序完为止

package class_0921;


public class class_check {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] nums_data = {11,22,34,8,45,0,12,45};
		chick(nums_data);
	}
	public static void chick(int[] data_list){
		//控制比较的轮数
		int len_data = data_list.length;
		for(int i =1;i=0
			//j是往前对比的，因此j--
			for(j=i-1;j>=0;j--){
				//如果列表中下标为j的是指，大于变量
				if(data_list[j]>temp){
					//就将列表的数值往会后推一位，也就是将下标为j的数值赋值为j+1
					data_list[j+1]=data_list[j];	
				}else {
					break;
				}
			}
			//这里是j+1的原因是，j在上面已经j--
			if(data_list[j+1]!=temp){
				//如果j+1不等于变量，就将变量赋值给j+1
				data_list[j+1] = temp;
			}
		}
		for(int n:data_list){
			System.out.println(n);
		}
	}

}
//i=1;j=0,列表中的数值为22和11，变量为22
//i=2;j=1,列表中的数值为34和22，变量为34；因为34大于22，直接break
//i=3;j=2,列表中的数值为8和34，变量为8；j--,j=1,j=0,
//判断8是否大于下标的值，不是，则数组移位
//以此类推

• 二分查找，有成为折半查找
• 前提是：在已经排好序的数组中，通过将待查找的元素与中间索引值对应的元素进行比较，若大于中间索引对应的元素，去除有半部分查找，否则去左半部分查找，以此类推，直到找到位置，找不到返回一个负数
• 注意：第一：必须保证序列是有序的，如果无序，可使用排序算法先进行排序
• 二分查找的效率是非常高的
• 代码示例：

package class_1004;

public class class_avg_select {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] num_data = {11,33,55,77,99,101};//序列
		int index = avgselect(num_data,200);// 查找的值
		if(index==-1){
			System.out.println("序列中没有这个值，返回值是："+index);
		}else {
			System.out.println("数字的序列中的下标是："+index);
		}

	}
	public static int avgselect(int[] num, int key){
		int start = 0;//序列来时的下标
		int end = num.length-1;//序列最后一个数值的下标，结尾的下标
		//因为是有序的序列，所以end的数值一定大于start的数值
		while(start <= end){
			int middle = (start+end)/2;//中间值的下标，也可以用位移来表示，>>>1
			//如果中间值比key大，要在左边进行查找，所以end重新赋值，中间值+1
			if(num[middle]key){
				//如果中间值比key小，要在右边进行查找，所以end重新赋值，中间值+1
				end = middle-1;
			}else {
				return middle;
			}
		}
		return -1;
	}

}