快速排序、归并排序

感觉好久之前不写这些基础的东西忽然觉着，想复习一下，就简单温习一下排序的例子

package com.ruishenh.algoritmic;


public class Sort {

	public static void main(String[] args) {
		// 冒泡排序
		int[] arrs=getRandomArrs(20000);
//		printMsg(arrs);
		long start = System.currentTimeMillis();
		bubblingSort(arrs);
		long end = System.currentTimeMillis();
//		printMsg(arrs);
		System.out.println("冒泡结果："+(end - start));
		System.out.println("----------------------");

		// 归并排序
		arrs = getRandomArrs(5000000);
		start = System.currentTimeMillis();
		mergerSort(arrs);
		end = System.currentTimeMillis();
		System.out.println("归并结果："+(end - start));
		System.out.println("----------------------");

		
		// 快排排序
		arrs = getRandomArrs(5000000);
		start = System.currentTimeMillis();
		quickSort(arrs,0,arrs.length-1);
		end = System.currentTimeMillis();
		System.out.println("快排结果："+(end - start));
		System.out.println("----------------------");
		
		
	}
	static void printMsg(int [] arrs){
		for (int i : arrs) {
			System.out.print(i);
			System.out.print(",");
		}
		System.out.println();
		
	}
	static int [] getRandomArrs(int num){
		int [] ret=new int[num];
		for (int i = 0; i < num; i++) {
			ret[i]=(int) Math.floor(Math.random()*num);
		}
		return ret;
		
	};
	/**
	 * 冒泡排序
	 * @param arrs
	 */
	static void bubblingSort(int [] arrs){
		for (int i = 0; i < arrs.length; i++) {
			for (int j = 0; j < arrs.length-1-i; j++) {
				if (arrs[j]>arrs[j+1]) {
					int tmp=arrs[j];
					arrs[j]=arrs[j+1];
					arrs[j+1]=tmp;
				}
			}
		}
	}
	/**
	 * 归并排序
	 * @param arrs
	 */
	static void mergerSort(int [] arrs){
		mergerSort_split(arrs, 0, arrs.length-1, new int[arrs.length]);
	}
	static void mergerSort_merge(int [] a,int first,int mid,int last, int []  temp){
		{  
		    int i = first, j = mid + 1;  
		    int m = mid,   n = last;  
		    int k = 0;  
		      
		    while (i <= m && j <= n)  
		    {  
		        if (a[i] <= a[j])  
		            temp[k++] = a[i++];  
		        else  
		            temp[k++] = a[j++];  
		    }  
		      
		    while (i <= m)  
		        temp[k++] = a[i++];  
		      
		    while (j <= n)  
		        temp[k++] = a[j++];  
		      
		    for (i = 0; i < k; i++)  
		        a[first + i] = temp[i];  
		}  
	}
	static void mergerSort_split(int [] arrs,int first,int last, int []  temp){
		 if (first < last)  
		    {  
		        int mid = (first + last) / 2; 
		        //递归循环调用执行对半合并
		        mergerSort_split(arrs, first, mid, temp);    //左边有序  
		        mergerSort_split(arrs, mid + 1, last, temp); //右边有序  
		        mergerSort_merge(arrs, first, mid, last, temp); //再将二个有序数列合并  
		    }  
	}
	
	
    /**
     * 快速排序
     * @param list
     * @param low
     * @param high
     * @return
     */
    private static int[] quickSort(int [] list,int low ,int high){
        if(low<high){
            int middle=getMiddle(list, low, high); //将list数组进行一分为二
            quickSort(list, low, middle-1);       //对比key小的进行递归排序
            quickSort(list, middle+1, high);      //对比key大的进行递归排序
        }
        return list;
    }
    private static int getMiddle(int [] list,int low,int high){
        int tmp=list[low];          //数组第一个作为key
        while(low<high){
            while(low<high&&list[high]>=tmp){
                high--;
            }
            list[low]=list[high];   //比key小的纪录移到低端
            while(low<high&&list[low]<=tmp){
                low++;
            }
            list[high]=list[low];  //比key大的纪录移到高端
        }
        list[low]=tmp;              //key纪录到末尾
        return low;                 //返回key的位置
    }
	
	
}

打印结果

冒泡结果：679
----------------------
归并结果：840
----------------------
快排结果：504
----------------------

快速排序、归并排序,布布扣,bubuko.com

快速排序、归并排序

原文：http://blog.csdn.net/ruishenh/article/details/19982561