`

java 实现排序算法(冒泡,选择,快速,归并)

阅读更多
package other;

import java.util.Random;

public class Main {

	public static void main(String[] args) {
		
		int b = -100000;
		System.out.println("b的源码是:"+Integer.toBinaryString(b));

		Random r = new Random();
		Main m = new Main();

		int[] a = new int[100];
		for (int i = 0; i < a.length; i++) {
			a[i] = r.nextInt(100) + 1; // 生成[1,100]的整数
		}

		long time1 = System.currentTimeMillis();
		m.bubbleSort(a); //冒泡排序
		long time2 = System.currentTimeMillis();
		System.out.println("冒泡排序"+(time2 - time1) + "ms");

		System.out.println("冒泡排序后:数组a中元素:");
		for (int i = 0; i < a.length; i++)
			System.out.println(a[i]);
	}
	
	
	

	//矩阵乘法
	public void Multiply(int[][] A, int[][] B) { // 矩阵A和B进行相乘
		int[][] C;
		if (A[0].length != B.length) {
			System.out.println("不能进行矩阵相乘运算");
		}

		C = new int[A.length][B[0].length];

		for (int i = 0; i < A.length; i++) {
			for (int j = 0; j < B[0].length; j++)
				for (int k = 0; k < A[0].length; k++) {
					C[i][j] = A[i][k] * B[k][j] + C[i][j];
				}
		}
	}

	//-----------------------快速排序begin---------------------------------//
	public void quickSort(int[] array, int p, int r) {// 快速排序,使数组array从p到r变成有序的
	// 分治策略
		if (p < r) {
			int q = partion(array, p, r); // 分割成两部分,其中一部分的所有元素小于另一部分中的所有元素,q是中间位置

			// 分别对于两部分进行快速排序
			quickSort(array, p, q - 1);
			quickSort(array, q + 1, r); // 递归调用
		}
	}
	private int partion(int[] array, int p, int r) { // 就是对array进行原地排序,

		int x = array[r];
		int i = p - 1;
		int temp;

		for (int j = p; j <= r - 1; j++) { // j指向当前的待排序元素
			if (array[j] < x || array[j] == x) {
				i++;// i指向小于x的部分的最后一个数

				temp = array[j];
				array[j] = array[i];
				array[i] = temp;
			}
		}

		temp = array[i + 1];
		array[r] = temp;
		array[i + 1] = x; // 将中轴换到两个部分的中间位置

		return i + 1; // 中轴的位置,中轴左侧都是小于等于中轴值,中轴右侧部分都大于中轴值
	}
	//-----------------------快速排序end---------------------------------//
	
	//-----------------------选择排序begin---------------------------------//
	public void selectionSort(int[] array) { // 选择排序
		int j;
		int temp = 0;
		int min = 0;
		for (int i = 0; i < array.length - 1; i++) { //注意这个边界是array.length-1,因为如果前面n-1个有序了,最后一个肯定是最大的
			min = i;
			for (j = i+1 ; j <= array.length - 1; j++) {
				if (array[min] > array[j])
					min = j;
			}
				temp = array[i];
				array[i] = array[min];
				array[min] = temp;
		}
	}
	//-----------------------选择排序end---------------------------------//
	
	//-----------------------归并排序begin---------------------------------//

	public void mergeSort(int[] a, int p, int r) { // 归并排序,从数组a的p位置到r位置排序
		int q;
		if (p < r) {
			q = (p + r) / 2;
			mergeSort(a, p, q);
			mergeSort(a, q + 1, r);
			merge(a, p, q, r);// 将已经有序的a[p...q]和a[q+1...r]归并成一个有序的a[p...r]
		}

	}
	private void merge(int[] a, int p, int q, int r) {  //归并两个有序序列a[p...q]和a[q+1...r]成为有序的a[p...r]

		int n1 = q - p + 1;
		int n2 = r - q;
		int[] L = new int[n1]; //辅助数组
		int[] R = new int[n2];//辅助数组

		for (int i = 0; i < n1; i++) {
			L[i] = a[i + p];
		}
		for (int i = 0; i < n2; i++) {
			R[i] = a[i + q + 1];
		}
		int i = 0, j = 0;// 分别指向L和R两个数组中元素的指针
		int k = p; // 指向结果数组元素的指针
		while (i < n1 && j < n2) {
			if (L[i] <= R[j]) { //两个有序数组的元素进行比较,谁小就加入到结果数组中,并将指针往前移一步
				a[k] = L[i];
				i++;
				k++;
			} else {
				a[k] = R[j];
				j++;
				k++;
			}
		}

		if (i < n1) {//while条件不满足了,肯定是 j=n2了,R先插入完,
			while (i < n1) {
				a[k] = L[i];
				k++;
				i++;
			}

		}

		if (j < n2) {  //while条件不满足了,肯定是 i=n2了,L先插入完
			while (j < n2) {
				a[k] = R[j];
				k++;
				j++;
			}
		}

	}
	
	//-----------------------归并排序end---------------------------------//
	
	
	//-----------------------插入排序begin---------------------------------//
	
	public void insertSort(int[] a){
		int i,j,key;
		for(i=1;i<a.length;i++){
			j=i-1;  //有序列的最后一个元素下标
			key = a[i];//当前待插入的元素
			
			//将当前元素插入到已经排好序的a[0...i-1]中	
			while(key<a[j]&&j>0){
				a[j+1]=a[j];  //将元素往后移
				j--;
			}
		a[j+1] = key; //插入当前元素
		
	}
	}
		//-----------------------插入排序end---------------------------------//
		
		
		
		//-----------------------冒泡排序begin---------------------------------//
		public void bubbleSort(int[] a){
			int temp;
			for(int i=0;i<a.length;i++){
				for(int j=0;j<a.length-1-i;j++){
					if(a[j]>a[j+1]){  //逆序时,交互相邻两个元素
						temp  = a[j];
						a[j] = a[j+1];
						a[j+1] = temp;
					}
						
				}
			}
			
			
		}
		//-----------------------冒泡排序end---------------------------------//
		

		
		
	
}
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics