几种排序方法

public class Sorting {

	/**
	 * 冒泡
	 * 复杂度为O(n*n)
	 * @param nums
	 */
	public static void bubleSort(int[] nums) {
		int len = nums.length;
		for (int i = 0; i < len - 1; i++) {
			for(int j=i+1;j < len; j++) {
				if(nums[i] > nums[j]) {
					int t = nums[i];
					nums[i] = nums[j];
					nums[j] = t;
				}
			}
		}
	}
	
	/**
	 * 插入排序
	 * @param nums
	 */
	public static void insertSort(int[] nums) { // IllegalArgumentException
		for (int i = 1; i < nums.length; i++) {
			for (int j = i; j > 0 && nums[j - 1] > nums[j]; j--) {
				int t = nums[j];
				nums[j] = nums[j - 1];
				nums[j - 1] = t;
			}
		}
	}

	/**
	 * 插入排序改进
	 * @param nums
	 */
	public static void insertSort2(int[] nums) {
		int len = nums.length;
		for (int i = 1; i < len; i++) {
			int t = nums[i];
			int j = i;
			for (; j > 0 && nums[j - 1] > t; j--) {
				nums[j] = nums[j - 1];
			}
			nums[j] = t;
		}
	}
	
	/**
	 * 快速排序
	 * 对于随即数据序列的排序，快速排序已经是最好的排序算法了。
	 * 对于有序序列的排序，快速排序的效率是很低的，复杂度为O(n*n)，这时用冒泡和插入排序反而很快
	 * 时间复杂度：O(n log n)
	 * @param array
	 * @param low
	 * @param high
	 */
	public static void quickSort(int[] array, int low, int high) {
		if(low < high) {
			int n = quickPartition(array, low, high);
			quickSort(array,low,n);
			quickSort(array,n+1,high);
		}
	}

	private static int quickPartition(int[] array, int low, int high) {
		// 采用子序列的第一个元素为枢纽元素
		int pivot = array[low];
		while(low < high) {
			// 从后往前在后半部分寻找第一个小于枢纽元素的元素
			while(low < high && array[high] >= pivot) {
				--high;
			}
			int t = array[low];
			array[low] = array[high];
			array[high] = t;
			
			//
			while(low < high && array[low] <= pivot) {
				++low;
			}
			t = array[low];
			array[low] = array[high];
			array[high] = t;
		}
		
		return low;
	}
	
	public static void print(int[] array) {
		int index = 0;
		System.out.println("-----------------------");
		for (int n : array) {
			System.out.print(n + ",");
			index++;
			if(index%20 == 0)
				System.out.println();
		}
	}
	
	public static void testBubleSort(int[] array) {
		long time = System.currentTimeMillis();
		bubleSort(array);
		long time2 = System.currentTimeMillis();
		System.out.println("bubleSort:" + (time2 - time));
		
		print(array);
	}
	
	public static void testInsertSort(int[] array) {
		long time = System.currentTimeMillis();
		insertSort2(array);
		long time2 = System.currentTimeMillis();
		System.out.println("insertSort:" + (time2 - time));
		
		print(array);
	}
	
	public static void testArraysSort(int[] array) {
		long time = System.currentTimeMillis();
		Arrays.sort(array);
		long time2 = System.currentTimeMillis();
		System.out.println("Arrays.sort:" + (time2 - time));
		
		print(array);
	}
	
	public static void testQuickSort(int[] array) {
		long time = System.currentTimeMillis();
		quickSort(array, 0, array.length - 1);
		long time2 = System.currentTimeMillis();
		System.out.println("quickSort:" + (time2 - time));
		
		print(array);
	}
	
	public static void main(String[] args) {
		/*
		double a = Math.random() * 10;
		a = Math.ceil(a);
		int randomNum = new Double(a).intValue();
		System.out.println(randomNum);
		*/

		Random random = new Random();
		// System.out.println(random.nextInt());
		// System.out.println(random.nextInt(999999999));

		int len = 9000;
		int randomMax = 999999;
		int[] nums = new int[len];
		for(int i=0;i<len;i++) {
			nums[i] = random.nextInt(randomMax);
		}

		//testBubleSort(nums);
		//testInsertSort(nums);
		//testArraysSort(nums);
		testQuickSort(nums);
	}

    // 打印结果:
    // bubleSort:3203
    // insertSort:1078
    // Arrays.sort:31 
    // quickSort:16
    // 不同机器，结果也会不同，但是结果数据的差距大致差不多，可以看出快速排序方法是最快的，
    // 比库函数还要快上一倍，比起 冒泡和插入排序，根本不在一个数量级上！
    // 不过也有特殊情况，如果待排序数据存在有序数据，快速排序就不如冒泡和插入排序了！
        

评论

4 楼 Jameslyy 2010-08-17  

java 的库函数，Arrays.sort() 的实现是区分数组大小的，如果很小（小于7）采用的是插入排序，如果比较大，则采用快速排序，但是根据又根据数组的大小用不同的方法获取第一个比较元素。

3 楼 Jameslyy 2010-07-23  

冒泡排序、插入排序时间复杂度为 n*n
快速排序时间复杂度为 n * log n，最坏时间复杂度为 n*n（有序数组）
超大数据的排序适合使用堆排序，堆排序具有空间复杂度。

2 楼 Jameslyy 2010-07-23  

快速排序：选择数组的第一项A，倒序比较数组的其余项，找到第一个小于第一项A的项B，假如B的下标为high，置换它们的值，再倒序比较数组下标小于high的项，找到大于第一项A的项C，假如C的下标为low，置换它们的值，以low为分界把数组分为两个部分，分别对它们做上述操作，最终完成数组的排序。

1 楼 Jameslyy 2010-07-22  

冒泡排序：把数组中每一项和其后面的项进行比较，如果是大于（顺序的情况，如果是倒序，则条件为小于），则把它们的值置换。需要两层循环比较，复杂度为 n*n 。

插入排序：从第二项开始，把数组每一项插入到已经排序的数组部分，第二项将会和第一项比较，如果小于（顺序）第一项，则置换它们的值，第三项则将会和已经排序的第一项和第二项组成的数组的每一项进行比较，直到找到合适的位置，并进行置换，以此类推。

待续...