`

四种基本排序算法(java表示)

阅读更多

工具类:

/**
 * 获取数据
 * 
 * @timestamp Mar 11, 2016 12:27:20 PM
 * @author smallbug
 */
public class DataUtil {

	public static final String ASC = "asc";
	public static final String DESC = "desc";

	/**
	 * 获取数据
	 * 
	 * @timestamp Mar 11, 2016 1:17:10 PM
	 * @param sum
	 * @return
	 */
	public static int[] getData(int sum) {
		int[] ii = new int[sum];
		Random r = new Random();
		for (int i = 0; i < sum; i++) {
			ii[i] = r.nextInt(sum);
		}
		return ii;
	}

	/**
	 * 交换数据
	 * 
	 * @timestamp Mar 11, 2016 1:17:17 PM
	 * @param data
	 * @param i
	 * @param j
	 */
	public static void swap(int[] data, int i, int j) {
		int temp = data[i];
		data[i] = data[j];
		data[j] = temp;
	}

	/**
	 * 验证排序是否成功
	 * 
	 * @timestamp Mar 11, 2016 1:38:09 PM
	 * @param data
	 * @param orderBy
	 * @return
	 */
	public static boolean verify(int[] data, String orderBy) {
		boolean flag = true;

		if (ASC.equalsIgnoreCase(orderBy)) {
			for (int i = 0; i < data.length - 1; i++) {
				if (data[i] > data[i + 1])
					flag = false;
			}
		} else if (DESC.equalsIgnoreCase(orderBy)) {
			for (int i = 0; i < data.length - 1; i++) {
				if (data[i] < data[i + 1])
					flag = false;
			}
		} else {
			throw new RuntimeException("order error!");
		}
		return flag;
	}

}

 冒泡:

/**
 * 冒泡排序
 * <ul>
 * <li>平均情况:O(N^2)</li>
 * <li>最好情况:O(N)</li>
 * <li>最坏情况:O(N^2)</li>
 * <li>辅助存储:O(1)</li>
 * <li>稳定</li>
 * <ul>
 * 
 * @timestamp Mar 11, 2016 1:08:08 PM
 * @author smallbug
 */
public class BubbleSort {

	public static void main(String[] args) {

		int[] data = DataUtil.getData(1000);
		System.out.println(Arrays.toString(data));
		long time = System.currentTimeMillis();
		sort(data);
		System.out.println(Arrays.toString(data));
		System.out.println("speed " + (System.currentTimeMillis() - time) + " ms");
		System.out.println("排序是否成功:" + (DataUtil.verify(data, DataUtil.DESC) ? "是" : "否"));
	}

	/**
	 * 每一次的外层循环都是将一个最小的数字推到了次小或相等数字的下面<br />
	 * 内层循环是为了将小数字往上推
	 * 
	 * @timestamp Mar 11, 2016 1:05:21 PM
	 * @param data
	 */
	private static void bubbling(int[] data) {
		boolean flag;
		for (int i = 0; i < data.length; i++) {// 倒数第几个结束
			flag = true;// 本来这一趟是可以退出的
			for (int j = 1; j < data.length - i; j++) {// 比较第一个到第length-i个
				if (data[j] > data[j - 1]) {
					flag = false;// 但是由于交换了,就没有退出
					DataUtil.swap(data, j, j - 1);
				}
			}
			if (flag)
				return;// 成功退出
		}
	}
}

 选择:

package cn.smallbug.structure.sort;

import java.util.Arrays;

/**
 * 选择排序
 * <ul>
 * <li>平均情况:O(N^2)</li>
 * <li>最好情况:O(N^2)</li>
 * <li>最坏情况:O(N^2)</li>
 * <li>辅助存储:O(1)</li>
 * <li>不稳定</li>
 * <ul>
 * 
 * @timestamp Mar 11, 2016 12:52:57 PM
 * @author smallbug
 */
public class SelectSort {

	public static void main(String[] args) {
		int[] data = DataUtil.getData(1000);
		System.out.println(Arrays.toString(data));
		long time = System.currentTimeMillis();
		selectSort(data);
		System.out.println(Arrays.toString(data));
		System.out.println("speed " + (System.currentTimeMillis() - time) + " ms");
		System.out.println("排序是否成功:" + (DataUtil.verify(data, DataUtil.ASC) ? "是" : "否"));
	}

	public static void selectSort(int[] data) {
		int p = -1;// 定义指向最大值的指针
		for (int i = 0; i < data.length - 1; i++) {// 从第一个数开始比较到length-1个数
			p = i;// 初始化最大值指针
			for (int j = i + 1; j < data.length; j++) {// 比较i之后的数
				if (data[p] < data[j])
					p = j;// 指向最大数
			}
			if (i != p)// 让i位的数字与最大值交换
				DataUtil.swap(data, p, i);
		}
	}

}

 插入:

/**
 * 插入排序
 * <ul>
 * <li>平均情况:O(N^2)</li>
 * <li>最好情况:O(N)</li>
 * <li>最坏情况:O(N^2)</li>
 * <li>辅助存储:O(1)</li>
 * <li>稳定</li>
 * <ul>
 * 
 * @timestamp Mar 11, 2016 1:25:05 PM
 * @author smallbug
 */
public class InsertSort {

	public static void main(String[] args) {
		int[] data = DataUtil.getData(1000);
		System.out.println(Arrays.toString(data));
		long time = System.currentTimeMillis();
		insertSort(data);
		System.out.println(Arrays.toString(data));
		System.out.println("speed " + (System.currentTimeMillis() - time) + " ms");
		System.out.println("排序是否成功:" + (DataUtil.verify(data, DataUtil.ASC) ? "是" : "否"));
	}

	private static void insertSort(int[] data) {
		int temp;
		for (int i = 1; i < data.length; i++) {
			temp = data[i];// 保存待插入的数值
			int j = i;
			for (; j > 0 && temp < data[j - 1]; j--) {
				data[j] = data[j - 1];// 如果待插入的数值前面的元素比该值大,就向后移动一位
			}
			data[j] = temp;// 插入
		}
	}
}

 Shell:

/**
 * Shell排序<br />
 * <ul>
 * <li>平均情况:O(N^1.5)</li>
 * <li>最好情况:O(N)</li>
 * <li>最坏情况:O(N^2)</li>
 * <li>辅助存储:O(1)</li>
 * <li>不稳定</li>
 * <ul>
 * 
 * @timestamp Mar 11, 2016 2:01:32 PM
 * @author smallbug
 */
public class ShellSort {

	public static void main(String[] args) {
		int[] data = DataUtil.getData(1000);
		System.out.println(Arrays.toString(data));
		long time = System.currentTimeMillis();
		shellSort(data);
		System.out.println(Arrays.toString(data));
		System.out.println("speed " + (System.currentTimeMillis() - time) + " ms");
		System.out.println("排序是否成功:" + (DataUtil.verify(data, DataUtil.ASC) ? "是" : "否"));
	}

	private static void shellSort(int[] data) {
		int k = 1;// 增量
		for (;;) {
			k = k << 1;
			if (k > data.length) {
				k >>= 1;
				break;
			}
		} // 这里取的增量是2^n-1,即长度为1000算出的k是512,它是最大的小于1000且为2的倍数的数
		for (; k > 1; k >>>= 1) {
			int temp;
			for (int i = k - 1; i < data.length; i++) {
				temp = data[i];// 保存待插入的数值
				int j = i;
				for (; j > k - 2 && temp < data[j - k + 1]; j = j - k + 1) {// j-k+1=j-(k-1)=k-增量
					data[j] = data[j - k + 1];// 如果待插入的数值前面的元素比该值大,就向后移动k-1位
				}
				data[j] = temp;// 插入
			}
		}

	}
}

 

1
4
分享到:
评论

相关推荐

    常用排序算法java演示

    本文将深入探讨标题"常用排序算法java演示"中涉及的知识点,包括排序算法的原理、Java实现方式以及其在实际应用中的图形演示。 首先,让我们逐一了解几种常见的排序算法: 1. **冒泡排序(Bubble Sort)**:这是一...

    各种排序算法比较(java实现)

    本文将详细探讨标题所提及的几种排序算法:合并排序、插入排序、希尔排序、快速排序、冒泡排序以及桶排序,并结合Java语言的实现进行解析。 1. **合并排序(Merge Sort)**: 合并排序是一种基于分治策略的排序算法...

    各种排序算法java实现

    在提供的文件中,我们可以看到有四种经典的排序算法的Java实现:插入排序、冒泡排序、选择排序以及希尔排序。 **插入排序**: 插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据...

    java实现的八种基本排序算法(有注释)

    以下是标题"java实现的八种基本排序算法(有注释)"所涵盖的八种排序算法的详细说明: 1. **冒泡排序(Bubble Sort)**: 冒泡排序是一种简单的交换排序,通过不断比较相邻元素并交换位置,使最大或最小的元素逐渐...

    堆排序算法 java

    堆排序算法 java

    各种排序算法java源代码

    下面将详细介绍这四种排序算法的原理、特点以及Java实现的关键点。 1. **冒泡排序**: 冒泡排序是一种简单直观的排序算法,通过不断交换相邻的逆序元素来逐步将较大的元素推向序列末尾。它的时间复杂度为O(n^2)。...

    java的两种冒泡排序算法

    ### Java中的两种冒泡排序算法 #### 知识点一:基本冒泡排序算法 冒泡排序是一种简单的排序算法,其基本思想是通过不断地比较相邻元素的大小,并根据需要进行交换,来达到排序的目的。 **代码实现:** ```java ...

    三种线性排序算法Java实现

    本资源提供的Java实现包括了三种线性排序算法:桶排序(Bucket Sort)、基数排序(Radix Sort)和计数排序(Counting Sort)。这三种算法在特定条件下可以达到线性的平均或最好时间复杂度,效率相对较高。 1. **桶...

    JAVA四种基本排序的总结

    本文将深入探讨四种基本的排序算法:冒泡排序、插入排序、选择排序和快速排序。这些算法各有特点,适用于不同的场景,理解它们的工作原理有助于提升编程能力。 首先,我们来了解冒泡排序(Bubble Sort)。冒泡排序...

    三种排序算法java实现

    这里我们主要关注三种排序算法的Java实现:快速排序、桶排序以及插入排序。这三种算法各有特点,适用于不同的场景。 首先,快速排序(QuickSort)是由C.A.R. Hoare在1960年提出的,它是一种分治策略的典型应用。...

    常见的七大排序算法Java实现.zip

    本压缩包"常见的七大排序算法Java实现.zip"包含了七种经典的排序算法在Java语言中的实现。尽管文件列表中并未明确列出每种排序算法的名称,但根据常规,这七大排序算法可能包括冒泡排序、插入排序、选择排序、快速...

    快速排序算法java代码

    "快速排序算法java代码" 快速排序算法是由Tony Hoare在1960年提出的一种排序算法,它的平均时间复杂度为O(n log n),是目前最快的排序算法之一。下面我们将详细地讲解快速排序算法的java代码实现。 快速排序算法的...

    七种排序算法Java版

    七种排序算法Java版 以下是对七种排序算法Java版的详细解释: 1. 冒泡排序 冒泡排序是一种简单的排序算法,时间复杂度为O(n2),算法具有稳定性。冒泡排序的基本思想是:通过对数组的多次遍历,逐渐将最大(或最小...

    基于java语言十大经典排序算法

    **基于Java语言十大经典排序算法** 排序算法是计算机科学中不可或缺的一部分,特别是在数据处理和算法设计领域。在Java编程中,理解并掌握各种排序算法能够帮助开发者提高代码效率,优化性能。以下是Java语言中十大...

    常用的排序算法(java实现),附带一个PPT动画演示、详解了其中三种

    插入排序是一种简单的排序算法,其基本思想是将未排序的元素逐个插入到已排序的序列中,直到所有元素都有序。在Java中,插入排序可以使用两层循环实现:外层循环控制未排序部分的元素,内层循环则负责找到合适的位置...

    Java常用8大排序算法

    除了以上介绍的四种排序算法外,Java中还有以下几种常用的排序算法: 1. **冒泡排序**:每次比较两个相邻的元素,如果它们的顺序错误就把它们交换过来。遍历所有元素之后,最大的元素就会被放到最后的位置上。然后...

    java常见八种排序算法

    本篇文章将详细探讨Java中常见的八种排序算法,每一种都有其独特的特性和适用场景。 1. **冒泡排序(Bubble Sort)** 冒泡排序是最基础的排序算法之一,通过不断交换相邻的逆序元素来逐步完成排序。它的时间复杂度为...

    8种排序算法的可视化 采用java gui的形式展示

    8种排序算法的可视化 采用java gui的形式展示8种排序算法的可视化 采用java gui的形式展示8种排序算法的可视化 采用java gui的形式展示8种排序算法的可视化 采用java gui的形式展示8种排序算法的可视化 采用java gui...

Global site tag (gtag.js) - Google Analytics