首页 > 代码库 > java实现的集中排序算法

java实现的集中排序算法

嗯,在经典的排序算法里面,有:冒泡排序,选择排序,插入排序,希尔排序,二叉归并排序,快速排序,堆排序

下面给出java的实现方式,不过快速排序没有搞定,研究中

package net.itaem.sort;

/**
 * 数组排序
 * */
public class ArraySorted {

	/**
	 * 冒泡排序(而且是简单的冒泡排序,应该属于交换排序,不属于经典的冒泡排序)
	 * */
	public static void bubble(int[] source){
		if(source.length == 0 || source.length == 1) return;   //无空,或者是1的情况下,不需要排序

		for(int i=0; i<source.length; i++){
			for(int j=i+1; j<source.length; j++){   //简单的比较,然后交换数据...
				if(source[i] > source[j]){
					//交换
					int temp = source[i];
					source[i] = source[j];
					source[j] = temp;
				}
			}
		}
	}

	/**
	 * 经典的冒泡排序
	 * */
	public static void classicBubble(int[] source){
		if(source.length == 0 || source.length == 1) return;   //无空,或者是1的情况下,不需要排序
		boolean flag = true;

		for(int i=0; i<source.length && flag; i++){
			flag = false;   //记录下下面一个循环是否有交换数据
			for(int j=source.length-1; j>i; j--){   //从后面开始,这样子可以将小的元素在每次循环中都提前
				if(source[i] > source[j]){
					//交换
					int temp = source[i];
					source[i] = source[j];
					source[j] = temp;
					flag = true;
				}
			}
		}
	}

	/**
	 * 选择排序
	 * 这也是一种普通的交换排序
	 * */
	public static void swap(int[] source){
		if(source.length == 0 || source.length == 1) return;   //无空,或者是1的情况下,不需要排序

		for(int i=0; i<source.length; i++){
			int min = i;  //默认情况下,第i个元素为最小的元素

			for(int j=i+1; j<source.length; j++){   //找到最小的小标
				if(source[min] > source[j]){
					min = j;   //记录下
				}
			}

			if(min != i){   //如果最小元素存在,交换
				int temp = source[i];
				source[i] = source[min];
				source[min] = temp;
			}
		}
	}


	/**
	 * 插入排序
	 * 
	 * */
	public static void insert(int[] source){
		if(source.length == 0 || source.length == 1) return;   //无空,或者是1的情况下,不需要排序
		int i=1, j = 0;
		for(; i<source.length; i++){
			if(source[i] < source[i-1]){
				int temp = source[i];   //记住要插入的变量

				for(j=i-1;j>=0 &&  source[j] > temp; j--){   //移动所有比temp大的元素,也就是要插入这个大的元素
					source[j+1] = source[j];
				}
                //插入元素
				source[++j] = temp;
			}
		}
	}


	/**
	 * 堆排序
	 * */
	public static void heap(int[] source){
		if(source.length == 0 || source.length == 1) return;   //无空,或者是1的情况下,不需要排序

		int i = 0;

		//构建一个大顶堆
		for(i = source.length/2; i>=0; i--){ 
			heapAjust(source, i, source.length);
		}

		//开始排序
		for(i=source.length-1; i>=0; i--){
			swapItem(source, 0, i);   //每次将最大的元素和最小的元素进行交换
			heapAjust(source, 0, i-1);   //重新形成一个大顶堆
		}
	}

	//交换数据
	private static void swapItem(int[] source, int i, int j) {
		int temp = source[i];
		source[i] = source[j];
		source[j] = temp;
	}
    
	/**
	 * 形成一颗大顶堆树
	 * */
	private static void heapAjust(int[] source, int s, int length) {
		int temp = 0, j = 0;
		
		temp = source[s];   
        
		for(j = 2*s; j<length; j*=2){

			if(j < length-1 && source[j] < source[j+1]){
				++j;
			}

			if(temp >= source[j]){
				break;
			}
			
			source[s] = source[j]; 
			s = j;
		}

		source[s] = temp;
	}

	
	/**
	 * 二叉归并排序
	 * */
	public static void mergeSort(int[] source){
		if(source.length == 0 || source.length == 1) return;   //无空,或者是1的情况下,不需要排序
		
		//归并排序
		merge0(source, 0, source.length-1);
	}

	private static void merge0(int[] source, int start, int end) {
		
		if(start != end){
			int middle = (start+end)/2;
			merge0(source, start, middle);
			merge0(source, middle+1, end);
			merge(source, start, middle, middle+1, end);
		}
	}

	private static void merge(int[] array, int start1, int end1, int start2,
			int end2) {
		int i=start1;//左路起始索引
        int j=start2;//右路起始索引
        int k=0;
        //归并的时候,会将两个数组数据按照大小输入到一个临时数组中
        //建立临时长度为两个子列表长度的数组
        int[] temp=new int[end2-start1+1];
        //循环遍历,按顺序找出两个表中的最小数据依次放入临时表中
        //注意此时左路和右路已经是有序的了。
        //当一路有一个小的,则会索引加1,继续喝另外一路的上次索引进行比较
        while(i<=end1&&j<=end2)
        {
            //这里确定归并的次序大小
            if(array[i]>array[j])
                temp[k++]=array[j++];
            else
                temp[k++]=array[i++];
        }
        //把剩下的元素放入临时数组中,只有一路的
        while(i<=end1)
            temp[k++]=array[i++];
        while(j<=end2)
            temp[k++]=array[j++];
        k=start1;
        
        
        for(int item:temp)
            array[k++]=item;
	}

	public static void main(String[] args) {
		int[] waitedSort = new int[5];
		waitedSort[0] = 4;
		waitedSort[1] = 1;
		waitedSort[2] = 2;
		waitedSort[3] = 5;
		waitedSort[4] = 3;
		
		mergeSort(waitedSort);
		//bubble(waitSorted);
		//heap(waitedSort);
		//insert(waitedSort);
		//swap(waitSorted);
		for(int i=0; i<waitedSort.length; i++){
			System.out.println(waitedSort[i]);
		}
	}
}