简单总结下各种排序算法

	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);
	}

评论

3 楼 bylijinnan 2012-06-29  

neyshule 写道

quicksort2是不是有问题，c[i]<=point?

嗯 我当时没考虑有相等的情况

2 楼 neyshule 2012-06-27  

quicksort2是不是有问题，c[i]<=point?

1 楼 pywepe 2012-02-05  

备忘,,希望没有错误