本文共 4655 字，大约阅读时间需要 15 分钟。

package main;public class Sort {		static void swap(int[] values, int firstIndex, int secondIndex) {		int tmp = values[firstIndex];		values[firstIndex] = values[secondIndex];		values[secondIndex] = tmp;	}	/**	 * 冒泡排序	 * @param values	 */	static void sort1(int[] values) {		for(int i = 0; i < values.length-1; i++) {			for(int j = 0;j < values.length - i - 1; j++) {				if (values[j]>values[j+1]) {					int tmp = values[j];					values[j] = values[j+1];					values[j+1] = tmp;				}			}		}	}		static void sort1_1(int[] values) {		for(int i = values.length-1;i>0;i--) {			for(int j = 0;j
   
    values[j+1]) {					int tmp = values[j];					values[j] = values[j+1];					values[j+1] = tmp;				}			}		}	}	/**	 * 直接插入排序	 * @param values	 */	static void sort2(int[] values) {		for(int i = 1; i < values.length; i++) {			for(int j = 0;j < i; j++) {				if (values[j]>values[i]) {					int tmp = values[i];					for (int k = i; k > j; k--) {						values[k] = values[k-1];					}					values[j] = tmp;					break;				}			}		}	}		static void sort2_1(int[] values) {		for(int i = 1; i < values.length; i++) {			int index = -1;			for(int j = 0;j < i; j++) {				if (values[j]>values[i]) {					index = j;					break;				}			}			if (index == -1) continue;			int tmp = values[i];			for (int j = i; j > index; j--) {				values[j] = values[j-1];			}			values[index] = tmp;		}	}	/**	 * 直接选择排序	 * @param values	 */	static void sort3(int[] values) {		for(int i = 0; i < values.length-1; i++) {			int index = i;			for(int j = i+1;j < values.length; j++) {				if (values[j]
    
     < i; j+=increment) {						if (values[j]>values[i]) {							index = j;							break;						}					}					if (index == -1) continue;					int tmp = values[i];					for (int j = i; j > index; j-=increment) {						values[j] = values[j-increment];					}					values[index] = tmp;				}			}		}	}	/**	 * 快速排序，是对冒泡排序的改进，	 * 设置一个枢轴记录，从待排序列的最后一个记录开始，将记录同枢轴记录比较，发现逆序后，将两者交换，	 * 然后从待排序列的第一个记录开始，同枢轴记录比较，发现逆序后，将两者交换，重复这两个步骤直到遍历完整个序列为止。	 * 然后对枢轴记录两边的两个序列做快速排序，如此重复，直到整个序列有序。	 */	static void sort5(int[] values) {		sort5_1(values, 0, values.length - 1);	}		static void sort5_1(int[] values, int start, int end) {		int centerIndex = start;		int centerValue = values[centerIndex];				int i = start;		int j = end;				while(i < j) {			while(i < j && values[j] >= centerValue) {				j--;			}			if (i < j) {				swap(values,centerIndex,j);				centerIndex = j;			}			while (i < j && values[i] <= centerValue) {				i++;			}			if (i < j) {				swap(values, centerIndex, i);				centerIndex = i;			}		}		//		对左侧序列进行快排序		if (start + 1 < centerIndex) {			sort5_1(values, start, centerIndex - 1);		}//		对右侧序列进行快排序		if (end - 1 > centerIndex) {			sort5_1(values, centerIndex + 1, end);		}	}	/**	 * 堆排序，堆是指在一个序列中，第 i 个记录不大/小于第 2*i 个和第 2*i+1 个记录，那么这个序列称为堆。	 * 堆排序，则是将待排序列看作一个完全二叉树，然后根据堆的定义，将待排序列构建为一个小根堆或大根堆，	 * 之后，取走堆顶记录作为输出，然后调整堆为一个新堆，再取走堆顶记录，如此反复，得到最终的有序序列。	 */	static void sort6(int[] values) {		for (int i = 0; i < values.length; i++) {			sort6_1(values, i);		}	}		static void sort6_1(int[] values, int start) {		int base = start;//		待排序列作为一个完全二叉树的层数		double value = Math.log(values.length - start)/Math.log(2);		int level = (int)(value);		//		调整为小根堆		for (int i = level; i > 0; i--) {			int levelStartIndex = (int) Math.pow(2, i) - 1;			int levelEndIndex = (int) Math.pow(2, i + 1) - 1;						for (int j = levelStartIndex; j < levelEndIndex && j + base < values.length; j = j + 2) {				int leftIndex = j + base;				int rightIndex = leftIndex + 1;				int parentIndex = j/2 + base;								int minIndex = parentIndex;				if (values[minIndex] > values[leftIndex]) {					minIndex = leftIndex;				}				if (rightIndex < values.length && values[minIndex] > values[rightIndex]) {					minIndex = rightIndex;				}				if (minIndex != parentIndex) {					swap(values, minIndex, parentIndex);				}			}		}	}		public static void main(String[] args) {		int[] values;		values = getValues();		Sort.sort1(values);		printValues(values);				values = getValues();		Sort.sort1_1(values);		printValues(values);				values = getValues();		Sort.sort2(values);		printValues(values);				values = getValues();		Sort.sort2_1(values);		printValues(values);		values = getValues();		Sort.sort3(values);		printValues(values);				values = getValues();		Sort.sort4(values);		printValues(values);				values = getValues();		Sort.sort5(values);		printValues(values);				values = getValues();		Sort.sort6(values);		printValues(values);	}		public static int[] getValues() {		int[] values = {1,20,10,30,5,5,9,0};		return values;	}		public static void printValues(int[] values) {		for (int i = 0; i < values.length; i++) {			System.out.print(values[i] + ",");					}		System.out.println();	}}
    
   

转载地址：http://rpdws.baihongyu.com/