当前位置:首页 > 开发 > 编程语言 > 算法 > 正文

简单总结下各种排序算法

发表于: 2012-02-05   作者:bylijinnan   来源:转载   浏览次数:
摘要: public static void bubbleSort(int[] c){ for(int i=0,len=c.length;i<len;i++){ for(int j=0;j<len-i-1;j++){ if(c[j]>c[j+1]){ Helper.swap(c, j+1, j); } } } }
	public static void bubbleSort(int[] c){
		for(int i=0,len=c.length;i<len;i++){
			for(int j=0;j<len-i-1;j++){
				if(c[j]>c[j+1]){
					Helper.swap(c, j+1, j);
				}
			}
		}
	}
	public static void selectionSort(int[] c){
		for(int i=0,len=c.length;i<len;i++){
			int k=i;
			for(int j=i+1;j<len;j++){
				if(c[j]<c[k])k=j;
			}
			if(k!=i){
				Helper.swap(c, i, k);
			}
		}
	}

public static void insertionSort(int[] a){
		for(int i=1,len=a.length;i<len;i++){
			int j=i;
			while(j>0){
				if(a[j]<a[j-1]){
					Helper.swap(a,j,j-1);
				}
				j--;
			}
		}
	}

	public static void quickSort2(int[] c,int begin,int end){
//update 2012/7/1
		if(c==null||c.length<2){
				return;
			}
		 if(begin>end)return; 
		 int len = c.length;
		 if(begin<end&&(0<=begin&&begin<len)&&(0<=end&&end<len)){
			 int point=c[begin];  
		     int i=begin,j=end;  
		     int index=i;  
		     while(i<j){ 
		    	 while(c[j]>=point&&i<j)j--;  
		         if(i<j){  
		             c[index]=c[j];  
		             index=j;  
		         } 
		         while(c[i]<=point&&i<j)i++;  
		         if(i<j){  
		             c[index]=c[i];  
		             index=i;  
		         }  
		     }  
		     c[index]=point;  
		     quickSort2(c,begin,i-1);  
		     quickSort2(c,i+1,end); 
		 }
	}
	public static void quickSort(int[] c,int begin,int end){
		if(begin>end)return;
		int low=begin;
		int high=end;
		boolean flag=true;
		while(low!=high){
			if(c[low]>c[high]){
				Helper.swap(c, low, high);
				flag=!flag;
			}
			if(flag){
				high--;
			}else{
				low++;
			}
		}
		quickSort(c,begin,low-1);
		quickSort(c,high+1,end);
	}
	
        
    /**
     * 用最大堆实现“就地”升序排序
     * 思路:
     * 1.“自下而上”,将整个数组初始化建成一个最大堆
     *   从最右下方的子堆——也就是以最后一个非叶子结点为根结点(lastRootindex)的子堆——开始,
     *   调整各个子堆使之为最大堆,最后使得整个数组成为一个最大堆
     *   注意到从 0, 1, 2, ...lastRootIndex 的结点都是非叶子结点,都作为子堆需要调整
     * 2.将当前堆顶元素(最大元素)与堆的最后一个元素交换,这样,当前最大值就排到末尾了
     * 3.将堆的大小减1(排除最后一个元素),重新调整使得堆仍为最大堆,直到排序完毕
     *   注意这时候的调整是“自上而下”,选举出当前的最大值放至堆顶
     */
    public static void heapsort(int[] array) {
        int lastIndex = array.length - 1;
        int lastRootIndex = (lastIndex - 1) / 2;
        for (int root = lastRootIndex; root >= 0; root--) {
            reheap(array, root, lastIndex);
        }
        for (int last = lastIndex; last >= 0; last--) {
            swap(array, 0, last);
            reheap(array, 0, last - 1);     //堆大小减1
        }
        System.out.println(Arrays.toString(array));
    }

    /**
     * 调整使之仍为最大堆
     * @param heap heap是这样一个“半堆”:执行调整操作前是一个最大堆。将最大堆的堆顶元素移除,并替换为最大堆的最后一个元素,成为“半堆”
     * @param rootIndex “半堆”的根
     * @param lastIndex “半堆”的最后一个元素
     */
    public static void reheap2(int[] heap, int rootIndex, int lastIndex) {
        int orphan = heap[rootIndex];
        int leftIndex = rootIndex * 2 + 1;
        boolean done = false;
        while (!done && leftIndex <= lastIndex) {
            int largeIndex = leftIndex;
            int rightIndex = leftIndex + 1;
            if (rightIndex <= lastIndex && heap[rightIndex] > heap[leftIndex]) {
                largeIndex = rightIndex;
            }
            if (heap[largeIndex] > orphan) {
                heap[rootIndex] = heap[largeIndex];
                rootIndex = largeIndex;
                leftIndex = rootIndex * 2 + 1;
            } else {
                done = true;
            }
        }
        heap[rootIndex] = orphan;

    }


	public static void mergeSort(int[] c,int low,int high,int[] tmp){
		if(low>=high)return;
		int mid=(high&low)+((high^low)>>1);
		mergeSort(c,low,mid,tmp);
		mergeSort(c,mid+1,high,tmp);
		merge(c,low,mid,high,tmp);
	}
	public static void merge(int[] c,int low,int mid,int high,int[] tmp){
		int begin01=low;
		int end01=mid;
		int begin02=mid+1;
		int end02=high;
		int k=0;
		while(begin01<=end01&&begin02<=end02){
			if(c[begin01]<c[begin02]){
				tmp[k]=c[begin01];
				k++;
				begin01++;
			}else{
				tmp[k]=c[begin02];
				k++;
				begin02++;
			}
		}
		while(begin01<=end01){
			tmp[k++]=c[begin01++];
		}
		while(begin02<=end02){
			tmp[k++]=c[begin02++];
		}
		System.arraycopy(tmp, 0,  c,low, k);
	}

简单总结下各种排序算法

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
排序就是将一组杂乱无章的数据按一定的规律排列起来(递增或递减)。 第一类:插入排序 基本原理,每
概述 排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很
1. 基本思想:   每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺序放在已排好序的
概述 排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很
概述 排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很
排序大的分类可以分为两种:内排序和外排序。在排序过程中,全部记录存放在内存,则称为内排序,如
1. 基本思想:   每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺序放在已排好序的
排序的分类: 1 内部排序 内部排序:在整个排序过程中不需不访问外存便能完成,称这样的排序问题为
校招快要开始了,复习一下以前的排序知识,下面的代码都是以前写的,今天翻出来又重新看了一下,贴
排序算法是笔试和面试中最喜欢考到的内容,今晚花了好几个小时的时间把之前接触过的排序算法都重新
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号