数据结构--排序

转自：http://student.zjzk.cn/course_ware/data_structure/web/paixu/paixu8.6.2.htm

顺便贴出两个排序：快速排序，插入排序代码



快速排序：

package org.hwq.util;
public class QuickSort{
	public static int part(int[] arr,int low,int heigh){
		int temp = arr[low];
		while(low<heigh){
			while(low<heigh&&arr[heigh]>temp)
				heigh--;
			if(low<heigh)
				arr[low++] = arr[heigh];
			
			while(low<heigh&&arr[low]<temp)
				low++;
			if(low<heigh)
				arr[heigh--] = arr[low];
		}
		arr[low] = temp;
		return low;
	}
	public static void quicksort(int[]arr,int low,int heigh){
		int p ;
		if(low<heigh){
			p = part(arr,low,heigh);
			quicksort(arr,low,p-1);
			quicksort(arr,p+1,heigh);
		}
	}
	public static void quicksort(int[] arr){
		quicksort(arr,0,arr.length-1);
	}
	public static void main(String[] args) {
		int[] arr = new int[]{3,2,1,55,6,6,6,6};
		quicksort(arr);
		for(int i=0;i<arr.length;i++){
			System.out.print(arr[i]+",");
		}
	}
}

插入排序：

package org.hwq.util;

public class InsertSort {
	public static void insertsort(int[] a){
		int t,j;
		for(int i=1;i<a.length;i++){
			t = a[i];
			for(j=i-1;j>=0;j--){
				if(t<a[j]){
					a[j+1] = a[j];
				}else{
					break;
				}
			}
			a[j+1] = t;
		}
	}
/**
	 * 插入排序的递归调用
	 * @param a
	 * @param i
	 */
	public static void recursionInsertion(int[] a,int i){
		if(i == 0){
			return;
		}
		recursionInsertion(a,i-1);
		insert(a,i);
	}
	
	public static void insert(int[] a,int i){
		int key = a[i];
		int j = i-1;
		for(;j>=0;j--){
			if(key<a[j]){
				a[j+1] = a[j];
			}else{
				break;
			}
		}
		a[j+1] = key;
	}

	public static void main(String[] args) {
		int[] arr = new int[]{2,1,5,6,3,8,8,8,4};
		insertsort(arr);
		for(int i=0;i<arr.length;i++){
			System.out.print(arr[i]+";");
		}
	}
}

堆排序：

public class Heap {
	public static void heapAdjust(int[] a,int start,int length){
		int temp = a[start];
		int child;
		int i;
		for(i = start; i * 2 + 1 < length; i = child){
			child = i * 2 + 1;
			if(child!=length-1&&a[child+1]>a[child])
				++child;
			if(temp<a[child]){
				a[i] = a[child];
			}else{
				break;
			}
		}
		a[i] = temp;
	}
	public static void heapSort(int[] a){
		for(int i=a.length/2-1;i>=0;i--){
			heapAdjust(a,i,a.length);
		}
		for(int i = a.length-1;i>0;i--){
			swap(a,0,i);
			heapAdjust(a,0,i);
		}
	}
	public static void swap(int[] a,int i,int j){
		a[i]^=a[j];
		a[j]^=a[i];
		a[i]^=a[j];
	}
	public static void main(String[] args) {
		int[] a = {42,13,24,91,23,16,05,88,88,8,91,88,88};
		System.out.println(Arrays.toString(a));
		heapSort(a);
		System.out.println(Arrays.toString(a));
	}
}

希尔排序：

public class ShellRe {
	/**
	 * 希尔排序,每次改变一个增量，直到增量increment=1，变为直接插入排序
	 * @param a
	 */
	public static void shellSort(int[] a){
		for(int k=a.length/2;k>0;k/=2){
			insertion(a,k);
		}
	}
	/**
	 * 直接插入排序
	 * @param a
	 */
	public static void insertion(int[] a){
		for(int i=1;i<a.length;i++){
			int temp = a[i];
			int j;
			for(j=i-1;j>=0;j--){
				if(temp<a[j]){
					a[j+1] = a[j];
				}else{
					break;
				}
			}
			a[j+1] = temp;
		}
	}
	/**
	 * 加入增量的插入排序
	 * 如果increment=1，则演变为直接插入排序
	 * @param a
	 * @param increment
	 */
	public static void insertion(int[] a,int increment){
		for(int i=increment;i<a.length;i+=increment){
			int temp = a[i];
			int j;
			for(j=i-increment;j>=0;j-=increment){
				if(temp<a[j]){
					a[j+increment] = a[j];
				}else{
					break;
				}
			}
			a[j+increment] = temp;
		}
	}
	public static void main(String[] args) {
		int[] a = {42,13,24,91,23,16,05,88,88,8,91,88,88};
		System.out.println(Arrays.toString(a));
//		insertion(a,1);
		shellSort(a);
		System.out.println(Arrays.toString(a));
	}
}