了解一下Java常用排序算法

冒泡排序算法：主要从头（或从尾）依次比较相邻两个算法，经过一次多伦的比较交换，最小的值会优先排好。

static void bubbleSort(int[] data){
		int temp;
		
		for (int i = 1; i < data.length; i++) {
			for (int j = 0; j < data.length-i; j++) {
				if (data[j]>data[j+1]) {
					temp=data[j+1];
					data[j+1]=data[j];
					data[j]=temp;
				}
			}
			
			System.out.print(i+"次排序:");
			for (int j = 0; j < data.length; j++) {
				System.out.print(" "+data[j]);
			}
			System.out.println("/n");
		}
		
	}
复制代码

假设输入的值是：118,101,105,127,112。那么打印结果如下：

1次排序: 101 105 118 112 127

2次排序: 101 105 112 118 127

3次排序: 101 105 112 118 127

4次排序: 101 105 112 118 127
复制代码

快速排序算法

快速排序算法：取一个值（通常为数组第一个元素或中间的元素）作为分界值。从数组右侧（尾部）依次取出元素与中间值比较，直到有小于分界值的元素i，然后从左侧开始，依次取出元素与中间值比较，直到有大于中间值的元素j,交换元素i和j的位置。但元素j的位置小于元素i的位置时，以元素j的位置为分界处重复上述操作（递归）；

算法实现：

static void quickSort(int[] data,int begin,int end){
		int left=begin,right=end;
		int temp=data[(right+left)/2],value;
		
		while (left<right) {
			while (data[right]>temp) {
				 right--;
			}
			
			while (data[left]<temp) {
				left++;
			}
			
			if (left<=right) {
				value=data[left];
				data[left]=data[right];
				data[right]=value;
				right--;
				left++;
			}
			
			for (int i = 0; i < data.length; i++) {
				System.out.print(" "+data[i] );
			}
			
			System.out.println("");
			
			if (left==right) {
				left++;
			}
			
			if (begin<right) {
				quickSort(data,begin,left-1);
			}
			
			if (left<end) {
				quickSort(data, right+1, end);
			}
		}
		
		
	}
复制代码

假设数组元素为：118,101,105,127,112。那么打印结果如下：

105 101 118 127 112
 101 105 118 127 112
 101 105 118 112 127
 101 105 112 118 127
复制代码

选择排序

选择排序

选择排序主要思想是遍历数组，选择数组中最小的元素放在第一个位置，第二小放在第二个位置，依次类推。

下面是算法的实现：

static void selectSort(int[] data) {
	int temp; //用于交换数据的临时变量
	for (int i = 0; i < data.length - 1; i++) {
	    //从i+1位置开始，与i的位置比较
		for (int j = i + 1; j < data.length; j++) {
			//如果j的位置元素小于i的值，则与i位置的元素交换
			//这样就保持了i位置相对于后面的元素都是最小的
			if (data[i] > data[j]) {
				temp = data[i];
				data[i] = data[j];
				data[j] = temp;
			}
		}
		//将每次排序后的元素打印出来，方便查看
		System.out.print(i+": ");
		for (int j = 0; j < data.length; j++) {
			System.out.print(" "+data[j]);
		}
		System.out.println();
	}
}
复制代码

假如排序的数据为：118,101,105,127,112。那么打印出来的结果如下所示：

0:  101 118 105 127 112
1:  101 105 118 127 112
2:  101 105 112 127 118
3:  101 105 112 118 127
复制代码

堆排序

堆排序相对于选择排序来说，比较复杂，主要是堆的构造过程（大根堆和小更堆）。然后选择堆的根节点与最后一个叶节点交换，并输出交换后最后一个叶节点（不再参与后面的堆构造过程）。重新构造堆得反复过程。

堆结构：堆结构是一种树结构，准备说法是完全二叉树，因为涉及到完全二叉树的一些特性，假设树有n个节点，第m个节点具有如下特性：

• 如果2*m<=n，有左子树，下标为2*m+1;
• 如果2*m+1<=n,有右子树，下标为2*m+2;

大根堆：如果按照从小到大的顺序排序，要求非叶节点的数据要大于或等于左右子树。

小根堆：如果按照从到到小的顺序排序，要求非叶节点的数据要小于或等于子树。

算法实现：

static void headSort(int[] data,int n){
	int i,j,h,k;
	int temp;
	
	//将数组构建成大根堆
	for (i=n/2-1;i>=0;i--) {
		while (2*i+1<n) { //第i个元素有右子树（意味着也有左子树）
			j=2*i+1; //左子树下标
			
			if (data[j]<data[j+1]) { //左子树小于右子树
				j++; //j指向右子树
			}
			
			//i元素与左右子树最大值进行比较，构造大根堆
			if (data[i]<data[j]) {
				temp=data[i];
				data[i]=data[j];
				data[j]=temp;
				i=j;//交换会导致子树堆结构被破坏，需要重新构造
			}else {
				break;//子树堆未被破坏
			}
		}
	}
	
	System.out.print("原始数据构造成的堆：");
	for (int l = 0; l < data.length; l++) {
		System.out.print(" "+data[l]);
	}
	
	System.out.println();
	
	for(i=n-1;i>0;i--){
		//堆得根第一个元素（数值最大）与最后一个元素（i元素，数值最小）交换
		temp=data[0];
		data[0]=data[i];
		data[i]=temp;
		
		k=0;
		//每一步排序后需要重新构造堆，算法与上面构造初始堆是一致的
		while (2*k+1<i) {
			j=2*k+1;
			if (data[j+1]<i) {
				j++;
			}
			if (data[k]<data[j]) {
				temp=data[k];
				data[k]=data[j];
				data[j]=temp;
				k=j;
			}else {
				break;
			}
			
		}
		
		System.out.print("第"+(n-i)+"次排序结果：");
		for (int l = 0; l < data.length; l++) {
			System.out.print(" "+data[l]);
		}
		System.out.println();
	}
}
复制代码

假如排序的数据为：118,101,105,127,112。那么打印出来的结果如下所示：

原始数据构造成的堆： 127 118 105 101 112
第1次排序结果： 118 112 105 101 127
第2次排序结果： 112 101 105 118 127
第3次排序结果： 105 101 112 118 127
第4次排序结果： 101 105 112 118 127
复制代码

归为选择排序算法估计就是每次挑堆中最大（或最小）的元素输出。

插入排序

插入排序

插入排序主要是后面元素与前面排序好的元素比较，然后插入到合适的位置。

算法实现：

static void insetSort(int[] data){
	int temp;
	for (int i = 1; i < data.length; i++) {
		temp=data[i];//保存i元素，下面元素后移会覆盖数组i下标的值
		int j=i-1;
		
		while(j>=0&&temp<data[j]){//i元素与依次与前面比较，直到大于前面元素为止
			data[j+1]=data[j];//前面元素后移，方便i元素插入
			j--;
		}
		data[j+1]=temp;
	
		System.out.print("第"+i+"次排序结果：");
		for (int l = 0; l < data.length; l++) {
			System.out.print(" "+data[l]);
		}
		System.out.println();
	}
}
复制代码

假如排序的数据为：118,101,105,127,112。那么打印出来的结果如下所示：

第1次排序结果： 101 118 105 127 112
第2次排序结果： 101 105 118 127 112
第3次排序结果： 101 105 118 127 112
第4次排序结果： 101 105 112 118 127
复制代码

Shell排序算法

主要是将有n个元素的数组分成n/2个数字序列，第1个数据和第n/2+1数据组成一对，一对数据进行比较，后者大则调换位置进行排序。然后n/4,n/8..重复排序，直到最后n/(2*k)=1，进行插入排序算法进行排序。Shell排序比较适合数组元素比较多情况。

算法实现：

static void shellSort(int[] data){
	int x=0;
	int temp;
	
	for (int n = data.length/2; n >=1; n/=2) {//解决序列问题，即分组
		
		int j;
		
		for (int i = n; i < data.length; i++) {
			temp=data[i];
			j=i-n;//j坐标所在元素与i坐标所在元素成对
			
			while (j>=0&&temp<data[j]) {
				data[j+n]=data[j];
				j-=n;
			}
			data[j+n]=temp;
			
			
			System.out.print("第"+(x++)+"次排序结果：");
			for (int l = 0; l < data.length; l++) {
				System.out.print(" "+data[l]);
			}
			System.out.println();
		}
	}

}

}
复制代码

这里特意将打印信息，放到第一个循环内，可以清楚看出序列排序。假设属于数组为：118,121,105,127,112,30。 则打印结果如下：

//因为共分成6/2=3对序列，所以下标3、0,4、1,5、2一起组成3对序列，进行比较交换
//105-127
第0次排序结果： 118 121 105 127 112 30
//121-112
第1次排序结果： 118 112 105 127 121 30
//102-30
第2次排序结果： 118 112 30 127 121 105
//此时。6/4=1对序列，采用插入排序算法
第3次排序结果： 112 118 30 127 121 105
第4次排序结果： 30 112 118 127 121 105
第5次排序结果： 30 112 118 127 121 105
第6次排序结果： 30 112 118 121 127 105
第7次排序结果： 30 105 112 118 121 127
复制代码