import java.util.Random;
/**
* 排序测试类
* 排序算法的分类如下：
* 1.插入排序（直接插入排序、折半插入排序、希尔排序）；
* 2.交换排序（冒泡泡排序、快速排序）；
* 3.选择排序（直接选择排序、堆排序）；
* 4.归并排序；
* 5.基数排序。
*
* 关于排序方法的选择：
* (1)若n较小(如n≤50)，可采用直接插入或直接选择排序。
* 当记录规模较小时，直接插入排序较好；否则因为直接选择移动的记录数少于直接插人，应选直接选择排序为宜。
* (2)若文件初始状态基本有序(指正序)，则应选用直接插人、冒泡或随机的快速排序为宜；
* (3)若n较大，则应采用时间复杂度为O(nlgn)的排序方法：快速排序、堆排序或归并排序。
*
*/
public class SortTest {
/**
* 初始化测试数组的方法
* @return 一个初始化好的数组
*/
public int[] createArray() {
Random random = new Random();
int[] array = new int[10];
for (int i = 0; i < 10; i++) {
array[i] = random.nextInt(100) - random.nextInt(100);//生成两个随机数相减，保证生成的数中有负数
}
System.out.println("==========原始序列==========");
printArray(array);
return array;
}
/**
* 打印数组中的元素到控制台
* @param source
*/
public void printArray(int[] data) {
for (int i : data) {
System.out.print(i + " ");
}
System.out.println();
}
/**
* 交换数组中指定的两元素的位置
* @param data
* @param x
* @param y
*/
private void swap(int[] data, int x, int y) {
int temp = data[x];
data[x] = data[y];
data[y] = temp;
}
/**
* 冒泡排序----交换排序的一种
* 方法：相邻两元素进行比较，如有需要则进行交换，每完成一次循环就将最大元素排在最后（如从小到大排序），下一次循环是将其他的数进行类似操作。
* 性能：比较次数O(n^2),n^2/2；交换次数O(n^2),n^2/4
*
* @param data 要排序的数组
* @param sortType 排序类型
* @return
*/
public void bubbleSort(int[] data, String sortType) {
if (sortType.equals("asc")) { //正排序，从小排到大
//比较的轮数
for (int i = 1; i < data.length; i++) {
//将相邻两个数进行比较，较大的数往后冒泡
for (int j = 0; j < data.length - i; j++) {
if (data[j] > data[j + 1]) {
//交换相邻两个数
swap(data, j, j + 1);
}
}
}
} else if (sortType.equals("desc")) { //倒排序，从大排到小
//比较的轮数
for (int i = 1; i < data.length; i++) {
//将相邻两个数进行比较，较大的数往后冒泡
for (int j = 0; j < data.length - i; j++) {
if (data[j] < data[j + 1]) {
//交换相邻两个数
swap(data, j, j + 1);
}
}
}
} else {
System.out.println("您输入的排序类型错误！");
}
printArray(data);//输出冒泡排序后的数组值
}
/**
* 直接选择排序法----选择排序的一种
* 方法：每一趟从待排序的数据元素中选出最小（或最大）的一个元素， 顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。
* 性能：比较次数O(n^2),n^2/2
* 交换次数O(n),n
* 交换次数比冒泡排序少多了，由于交换所需CPU时间比比较所需的CUP时间多，所以选择排序比冒泡排序快。
* 但是N比较大时，比较所需的CPU时间占主要地位，所以这时的性能和冒泡排序差不太多，但毫无疑问肯定要快些。
*
* @param data 要排序的数组
* @param sortType 排序类型
* @return
*/
public void selectSort(int[] data, String sortType) {
if (sortType.equals("asc")) { //正排序，从小排到大
int index;
for (int i = 1; i < data.length; i++) {
index = 0;
for (int j = 1; j <= data.length - i; j++) {
if (data[j] > data[index]) {
index = j;
}
}
//交换在位置data.length-i和index(最大值)两个数
swap(data, data.length - i, index);
}
} else if (sortType.equals("desc")) { //倒排序，从大排到小
int index;
for (int i = 1; i < data.length; i++) {
index = 0;
for (int j = 1; j <= data.length - i; j++) {
if (data[j] < data[index]) {
index = j;
}
}
//交换在位置data.length-i和index(最大值)两个数
swap(data, data.length - i, index);
}
} else {
System.out.println("您输入的排序类型错误！");
}
printArray(data);//输出直接选择排序后的数组值
}
/**
* 插入排序
* 方法：将一个记录插入到已排好序的有序表（有可能是空表）中,从而得到一个新的记录数增1的有序表。
* 性能：比较次数O(n^2),n^2/4
* 复制次数O(n),n^2/4
* 比较次数是前两者的一般，而复制所需的CPU时间较交换少，所以性能上比冒泡排序提高一倍多，而比选择排序也要快。
*
* @param data 要排序的数组
* @param sortType 排序类型
*/
public void insertSort(int[] data, String sortType) {
if (sortType.equals("asc")) { //正排序，从小排到大
//比较的轮数
for (int i = 1; i < data.length; i++) {
//保证前i+1个数排好序
for (int j = 0; j < i; j++) {
if (data[j] > data[i]) {
//交换在位置j和i两个数
swap(data, i, j);
}
}
}
} else if (sortType.equals("desc")) { //倒排序，从大排到小
//比较的轮数
for (int i = 1; i < data.length; i++) {
//保证前i+1个数排好序
for (int j = 0; j < i; j++) {
if (data[j] < data[i]) {
//交换在位置j和i两个数
swap(data, i, j);
}
}
}
} else {
System.out.println("您输入的排序类型错误！");
}
printArray(data);//输出插入排序后的数组值
}
/**
* 反转数组的方法
* @param data 源数组
*/
public void reverse(int[] data) {
int length = data.length;
int temp = 0;//临时变量
for (int i = 0; i < length / 2; i++) {
temp = data[i];
data[i] = data[length - 1 - i];
data[length - 1 - i] = temp;
}
printArray(data);//输出到转后数组的值
}
/**
* 快速排序
* 快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。
* 步骤为：
* 1. 从数列中挑出一个元素，称为 "基准"（pivot），
* 2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分割之后，该基准是它的最后位置。这个称为分割（partition）操作。
* 3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
* 递回的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递回下去，但是这个算法总会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
* @param data 待排序的数组
* @param low
* @param high
* @see SortTest#qsort(int[], int, int)
* @see SortTest#qsort_desc(int[], int, int)
*/
public void quickSort(int[] data, String sortType) {
if (sortType.equals("asc")) { //正排序，从小排到大
qsort_asc(data, 0, data.length - 1);
} else if (sortType.equals("desc")) { //倒排序，从大排到小
qsort_desc(data, 0, data.length - 1);
} else {
System.out.println("您输入的排序类型错误！");
}
}
public static void main(String[] args) {
SortTest sortTest = new SortTest();
int[] array = sortTest.createArray();
System.out.println("==========冒泡排序后(正序)==========");
sortTest.bubbleSort(array, "asc");
System.out.println("==========冒泡排序后(倒序)==========");
sortTest.bubbleSort(array, "desc");
array = sortTest.createArray();
System.out.println("==========倒转数组后==========");
sortTest.reverse(array);
array = sortTest.createArray();
System.out.println("==========选择排序后(正序)==========");
sortTest.selectSort(array, "asc");
System.out.println("==========选择排序后(倒序)==========");
sortTest.selectSort(array, "desc");
array = sortTest.createArray();
System.out.println("==========插入排序后(正序)==========");
sortTest.insertSort(array, "asc");
System.out.println("==========插入排序后(倒序)==========");
sortTest.insertSort(array, "desc");
}
}
本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/rommal7090/archive/2009/04/30/4138914.aspx
分享到：
发表评论
-
hermes 监听hornetq JMS配置
2013-02-22 15:46 2009hermes 监听配置步奏 ... -
Proxool连接池之参数设置详解
2012-11-28 15:07 1142今天把我做的WEB工程用压力测试工具测试测试了一下，WEB ... -
Myeclipse注册码生成代码
2012-08-28 12:04 896package com.able.test; import ... -
portal启动参数配置
2011-12-29 11:39 1020-Xms768m -Xmn256m -Xmx1024m -Xs ... -
Java软件的安装与更新
2010-08-04 16:30 1003使用Java web start 和 JNLP技术部署应用 -
PowerDesign高级应用
2009-12-22 17:29 1412PowerDesign高级应用 1、去掉Oracle ... -
web应用中的Session机制
2009-11-30 21:31 1205目录： 一、术语session ... -
Apache Commons工具集
2009-11-19 16:42 797Apache Commons包含了很多开源的工具，用于解决平时 ... -
JTA事物管理
2009-11-17 09:20 1830Spring+iBatis+Atomikos实现JTA事务 ... -
Apache + Tomcat*2集群 负载平衡
2009-11-13 11:15 905说明：一台apache主机，两台tomcat主机 安装JDK ... -
powerdesigner12.5 入门教程
2009-10-26 13:11 11053powerdesigner12.5 入门教程 下载po ... -
php开源网址介绍
2009-09-17 12:37 4361[综合门户]PHPChina 开源社区门户 PHPChina ... -
入库算法
2009-09-16 19:47 1098String[] aa = {"1",&q ... -
什么是Drools?
2009-03-31 11:04 1817(译者增加：什么是Drools, 摘自drools.org) ... -
如何在SSH框架中防止重复提交？
2008-10-26 20:23 1553如何在已有的SSH框架中，构建一个非侵入式防重复提交方案？ 开 ...
相关推荐
总的来说，这段代码提供了四种排序算法的实现，分别是冒泡排序、选择排序、插入排序以及Java内置的数组排序。每种排序算法都有其适用场景，理解这些算法可以帮助我们更好地解决实际问题，并根据需求选择合适的排序...
以下是关于"冒泡排序，选择排序，插入排序，希尔排序，堆排序，归并排序，快速排序"这七种常见排序算法的源码实现及相关知识点的详细解释： 1. **冒泡排序**：冒泡排序是一种简单的排序算法，它重复地遍历待排序的...
本文将深入探讨四种在C++中实现的常见排序算法：插入排序、冒泡排序、堆排序和快速排序。这些算法各有特点，适用于不同的场景，理解并掌握它们对于提升编程能力至关重要。 1. **插入排序**： 插入排序是一种简单的...
冒泡排序、选择排序和插入排序是三种基本的排序算法，它们都是在计算机科学中用于组织数据的关键技术。这些算法的实现通常用作教学示例，帮助初学者理解排序过程和时间复杂性。 **冒泡排序（Bubble Sort）**： 冒泡...
本资源提供了七大经典排序算法的实现程序，包括快速排序、冒泡排序、选择排序、归并排序、插入排序、希尔排序和堆排序。下面将逐一详细介绍这些排序算法及其原理。 1. 快速排序：由C.A.R. Hoare提出，是一种采用...
直接插入排序、冒泡排序、快速排序、直接选择排序、堆排序和二路归并排序是计算机科学中经典的排序算法，它们在数据处理和算法学习中占有重要地位。这些排序算法各有特点，适用场景不同，下面将逐一详细介绍，并结合...
本文将详细讲解六种经典的排序算法——合并排序、插入排序、希尔排序、快速排序、冒泡排序以及桶排序，并结合提供的文件名（sort.c、set.c、main.c、set.h、sort.h）推测出每个文件可能包含的代码实现。 1. **合并...
本话题主要探讨六种内部排序算法：直接插入排序、希尔排序、冒泡排序、快速排序、选择排序以及堆排序。这六种排序算法各有优劣，适用于不同的场景，接下来我们将逐一进行详细阐述。 1. **直接插入排序**： 直接...
本资源包含了几种常见的排序算法，包括堆排序、选择排序、冒泡排序、归并排序和插入排序。这些排序算法各有特点，适用于不同的场景，并且在理解它们的工作原理后，能够帮助初学者更好地掌握编程基础。 1. **堆排序*...
本文将深入探讨C#中常见的四种排序算法：冒泡排序、选择排序、插入排序和希尔排序，以及它们的实现细节和应用场合。 首先，我们来看**冒泡排序**。冒泡排序是一种简单的交换排序方法，它通过不断比较相邻元素并交换...
本文将深入探讨Java编程语言中实现的七种主要排序算法：直接插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序以及归并排序。每种算法都有其独特性，适用于不同的场景和数据特性。 1. **直接插入排序**：...
- C++中，快速排序通常采用递归实现，选取一个基准值，将数组分为两部分，然后对这两部分分别进行快速排序。 6. **归并排序(Merge Sort)** - 归并排序是建立在归并操作上的一种有效的排序算法，它采用了分治的...
以下将详细讲解标题和描述中提到的几种排序算法：冒泡排序、快速排序、选择排序、二分法、插入排序以及快速选择排序。 1. **冒泡排序**：冒泡排序是一种简单的比较排序算法。它通过重复遍历待排序的数列，一次比较...
根据提供的文件信息，我们可以深入探讨几种经典的排序算法：冒泡排序、直接插入排序、快速排序以及希尔排序。这些算法在数据结构与算法课程中是非常重要的基础内容，它们各自有着独特的特性和应用场景。 ### 1. ...
快速排序的基本思想是选择一个pivot元素，然后将数组分为两个部分：小于pivot的元素和大于pivot的元素。然后，递归地对这两个部分进行排序，直到整个数组都已经排序。 在本文中，我们使用C++语言编写了冒泡排序和...
在本文中，我们将深入探讨四种经典的排序算法：插入排序、选择排序、基数排序和冒泡排序，以及它们在C++语言中的实现。 **插入排序（Insertion Sort）** 插入排序是一种简单直观的排序算法，它的工作原理类似于我们...
实验结果表明，直接插入排序算法和冒泡排序算法都可以正确地排序数组，但快速排序算法的性能远远超过它们。这是因为快速排序算法的时间复杂度只有 O(n log n)，而直接插入排序算法和冒泡排序算法的时间复杂度都是 O...
根据给定的文件信息，我们将深入探讨几种经典的排序算法，包括选择排序、冒泡排序、交换排序、希尔排序、插入排序以及基数排序。这些算法在计算机科学领域内有着广泛的应用，各自具有独特的特点和适用场景。 ### 1....
排序算法汇总（选择排序、直接插入排序、冒泡排序、希尔排序、快速排序、堆排序） 本资源介绍了六种常用的排序算法：选择排序、直接插入排序、冒泡排序、希尔排序、快速排序和堆排序。下面对每种算法进行详细介绍：...
这里我们汇总了七种常见的排序算法：Shell排序、归并排序、选择排序、快速排序、堆排序、冒泡排序和插入排序。每种算法都有其独特的特点和适用场景，下面将逐一详细介绍。 1. **Shell排序**：由Donald Shell提出，...