`
Jameslyy
  • 浏览: 403385 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

几种排序方法

阅读更多
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 。

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

待续...

相关推荐

    javascript 的几种排序方法

    以上就是JavaScript中常用的几种排序方法。理解并熟练运用它们,能够帮助你在处理数据时更加游刃有余。在实际项目中,可以根据具体需求选择合适的方法,或者利用现有的库和工具提高代码的可读性和可维护性。

    用几种排序方法对随机产生的数据排序

    以下是关于这几种排序方法的详细介绍: 1. **堆排序(Heap Sort)** 堆排序是一种基于比较的原地排序算法,它利用了完全二叉树的特性。首先构建大顶堆或小顶堆,然后将堆顶元素与末尾元素交换,再调整堆,重复此...

    几种排序方法的具体代码

    以下是标题“几种排序方法的具体代码”中涉及的几种排序算法的详细解释: 1. **插入排序**(Insertion Sort): 插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序...

    java堆排序和几种排序方法实现代码.pdf

    此外,代码中还展示了其他几种排序方法的实现,包括冒泡排序、双路冒泡排序、插入排序、快速排序和选择排序。这些排序算法各有特点: - 冒泡排序:通过不断交换相邻的逆序元素,逐步将最大(或最小)元素移到数组...

    常见几种排序方式(选择排序,冒泡排序,快速排序,希尔排序,堆排序,插入排序)

    常见的几种排序方式,包括选择排序,冒泡排序,快速排序,希尔排序,堆排序,插入排序。vs2008实现,对话框方式,主要实现字符串的由小到大...点击“几种排序方法.vcproj“运行。字符集使用多字节集,不能用UNICODE。

    几种排序方法及栈的应用

    主要是源代码 包括几种排序方法 选择 基数 快速排序 及栈的运用。

    php实现的几种排序方法

    php实现的几种排序方法,包括插入排序,选择排序,冒泡排序、快速排序

    Java几种排序方法

    根据给定的信息,本文将详细介绍Java中的四种基本排序算法:冒泡排序、插入排序、快速排序和选择排序。...以上四种排序算法各有优缺点,适用场景也不同。在实际应用中,根据具体需求选择合适的排序算法是非常重要的。

    数组的几种排序方法

    本篇文章将深入探讨数组的几种常见排序方法,包括冒泡排序、选择排序和插入排序,这些都是基础且实用的排序算法,对于理解更复杂的排序算法有着重要的铺垫作用。 ### 冒泡排序 冒泡排序是一种简单直观的排序算法。...

    几种排序方法的比较

    随即生成一组数据 可以实现三种排序方法的速度比较

    java几种排序方法代码

    使用java实现的选择、冒泡、插入、快速、希尔排序以及折半查找

    java堆排序和几种排序方法实现代码文.pdf

    - 在`OrderTest`类中,还提到了其他几种排序算法的实现,如冒泡排序、双路冒泡排序、插入排序、快速排序和选择排序。这些排序算法各有特点,适用于不同的场景。 - 冒泡排序是一种简单的排序,通过不断交换相邻的...

    数据结构常见排序的几种方法

    本程序涵盖了数据结构中常见的几种排序方法,下面将对这些排序算法进行详细介绍。 1. 冒泡排序(Bubble Sort) 冒泡排序是最简单的排序算法之一。它通过不断比较相邻元素并交换位置来实现排序,重复这一过程,直到...

    基于C语言的几种排序方法比较.pdf

    选择排序是不稳定的排序方法,因为在选择最小(或最大)元素时,可能会改变相同元素的原始顺序。其优点是实现简单,不会像冒泡排序那样移动大量元素;缺点是时间复杂度为O(n^2),效率同样很低。 插入排序...

    mysql排序方法

    几种mysql利用sql语句进行距离排序的方法,亲测可用,大家可放心研究

    C语言经典排序方法及动图演示

    这些排序方法是计算机科学中的基础,对于理解和优化算法性能至关重要。 1. **冒泡排序**:冒泡排序是最简单的排序算法之一,通过重复遍历待排序的数列,比较相邻元素并根据需要交换它们的位置。这个过程会使得较大...

    Java实现几种常见排序方法

    ### Java 实现几种常见排序方法 #### 泡泡排序(Bubble Sort) 泡泡排序是一种简单的排序算法,它重复地遍历待排序的数列,依次比较相邻的两个元素,如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复...

Global site tag (gtag.js) - Google Analytics