Java基本排序方法总结

冒泡排序法(Bubble Sort)

冒泡排序(Bubble Sort)的基本思想是:通过对待排序序列从后向前(从下标较大的元素开始),依次比较相邻元素的排序码,若发现逆序则交换,使排序码较小的元素逐渐从后部移向前部(从下标较大的单元移向下标较小的单元),就象水底下的气泡一样逐渐向上冒。

因为排序的过程中,各元素不断接近自己的位置,如果一趟比较下来没有进行过交换,就说明序列有序,因此要在排序过程中设置一个标志flag判断元素是否进行过交换。从而减少不必要的比较。

class Bubble{
	public void sort(int [] arr) {

		int temp;	//创建一个临时变量用于交换数据
		//外层循环决定走几趟
		for (int i=0; i < arr.length-1; i++) {	//length-1是因为最后一个数字不必再做交换
			//内层循环比较前后两个数大小 若前一个数比后一个数大,则交换
			for (int j=0; j < arr.length-1-i; j++) { //length-1-i 是因为最大数交换至数组尾部 不必再参与比较 if (arr[j]>arr[j+1]) {
				//若前一个大于后一个数,则交换
				temp = arr[j];		
				arr[j]=arr[j+1];
				arr[j+1]=temp;
				}
			}
		}	
	}
}

选择排序法(Selection Sort)

选择排序(Selection Sort)也是一种简单的排序方法。它的基本思想是:第一次从R[0]-R[n-1]中选取最小值,与R[0]交换,第二次从R[1]-R[n-1]中选取最小值,与R[1]交换,第三次从R[2]-R[n-1]中选取最小值,与R[2]交换,...,第i次从R[i-1]-R[n-1]中选取最小值,与R[i-1]交换,...,第n-1次从R[n-2]-R[n-1]中选取最小值,与R[n-2]交换,总共通过n-1次,得到一个按排序码从小到大排列的有序序列。

例如,给定n=8,数组R中的8个元素的排序码为:(8,3,2,1,7,4,6,5),选择排序过程。

//选择排序法 Selection Sort
class Select{
	public void sort(int [] arr) {
		int temp;
		for (int i=0; i<arr.length-1;i++) {  //一共进行length-1轮比较
			int min =arr[i];	//先假设每轮第一个数是最小的
			int minIndex = i;	//记录最小数的下标
			//将这个数与后面的所有数字挨个比较 找出后面数中的最小值和其下标
			for (int j=i+1; j < arr.length; j++) { 
                                if (min>arr[j]) {
				         min = arr[j];
				         minIndex = j;
				}
			//将循环后的找到的最小值放与每轮第一个数字交换	
			temp = arr[i];
			arr[i] = arr[minIndex];
			arr[i+1]=temp;
			}
		}
	}
}

插入排序法(Insertion Sort)

插入排序(Insertion Sort)的基本思想是:把n个待排序的元素看成为一个有序表和一个无序表,开始有序表只包含一个元素,无序表中包含有n-1个元素,排序过程中每次从无序表中取出第一个元素,把它的排序码依次与有序表元素的排序码进行比较,将它插入到有序表中的适当位置,使之成为新的有序表。

//插入排序法 Insertion Sort
class Insert{
	public void sort(int []arr) {
		for (int i=1; i< arr.length; i++) { int insertVal = arr[i]; //需要的插入的数提取出来,准备和前面的数比较 int index = i-1; 
                             //index位需要插入的数前面的数的下标 
                        while (index >=0 && insertVal < arr[index]) {
				arr[index+1]= arr[index];	//将index那一位数字向后移动一个
				index--;	//index向前进一个,准备和再前面的数字比较
			}
			arr[index+1]= insertVal;	//insertVal插入到适当的位置
		}
	}
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

微信扫一扫,分享到朋友圈

Java基本排序方法总结
返回顶部

显示

忘记密码?

显示

显示

获取验证码

Close