众所周知,JDK提供了java.util.Arrays工具类,能通过sort方法对基本类型的数据或者Java对象进行排序。
本文通过学习及使用三种简单排序算法(冒泡排序、选择排序、插入排序),实现对存储Java对象的数组进行排序。
以便使大家在学习简单排序算法的同时,又能对Arrays的排序实现有个更加感性的认知。
package com.zhangsx.sort;
import java.util.Comparator;
/**
* 简单排序算法的实现。
* 包括冒泡排序、选择排序和插入排序;可对对象数组按照指定的排序规则进行排序。
*
* 数组中的对象必须提供可比较的功能。
* 有以下两种方式为对象实现可比较功能:
* 1.对象实现java.lang.Comparable接口,提供比较规则。
* 2.提供一个实现了java.util.Comparator接口的比较器。
*
* @version 1.00 2010-4-11
* @since 1.5
* @author ZhangShixi
*/
public class SimpleSort {
private SimpleSort() {
}
/**
* 冒泡排序。
*
* 排序数组中的对象必须实现java.lang.Comparable接口,提供排序比较规则。
* 否则,调用时会抛出运行时异常java.lang.ClassCastException。
*
* 算法描述如下:
* 外层循环控制未排序的数据项,从数组最后一项开始,向低位递减。
* 内层循环控制数据项的比较和排序,从数组起始项开始,向高位递增。
* 每次内层循环结束,即外层循环移动一次时,数组的右侧将多一项排好序的数据。
*
* 1.从数组起始位置开始,比较数组前两项。
* 2.如果第一项大于第二项,则交换这两项。
* 3.数组下标下移一位,继续比较下两项数据的大小。
* 4.当遇到排好序的数据项时,返回到数组首项,重新开始下一趟排序。
*
* @param arrays 排序数组
*/
@SuppressWarnings("unchecked")
public static void bubbleSort(Object[] arrays) {
if (arrays == null || arrays.length == 0) {
return;
}
for (int out = arrays.length - 1; out > 0; out--) {
for (int in = 0; in < out; in++) {
if (((Comparable) arrays[in]).compareTo(arrays[in + 1]) > 0) {
swap(arrays, in, in + 1);
}
}
}
}
/**
* 冒泡排序。
* 按提供的比较器的比较规则进行排序。
* @param arrays 排序数组
* @param compara 排序比较器
*/
public static <T> void bubbleSort(T[] arrays, Comparator<? super T> compara) {
if (arrays == null || arrays.length == 0) {
return;
}
for (int out = arrays.length - 1; out > 0; out--) {
for (int in = 0; in < out; in++) {
if (compara.compare(arrays[in], arrays[in + 1]) > 0) {
swap(arrays, in, in + 1);
}
}
}
}
/**
* 选择排序。
*
* 排序数组中的对象必须实现java.lang.Comparable接口,提供排序比较规则。
* 否则,调用时会抛出运行时异常java.lang.ClassCastException。
*
* 算法描述如下:
* 外层循环控制未排序的数据项及交换最小数据项,从数组起始位置开始,向高位递增。
* 内层循环控制查找最小数据项,从外层循环所指向的位置开始,向高位递增。
* 每次内层循环结束,即外层循环移动一次时,数组的左侧将多一项排好序的数据。
*
* 1.外层循环从数组起始位置开始,并将最小数据项置为最小数据项。
* 2.内层循环从外层循环指向的下一个数据项开始,分别与最小数据项进行比较。
* 3.如果内层循环所指的当前数据项小于最小数据项,则将当前数据项下标置为最小数据项下标。
* 4.循环比较,直至内层循环结束,将找到为排序部分的最小数据项的下标。
* 5.交换外层循环当前数据项与内层循环找到的最小数据项。继续下一排序。
*
* @param arrays 排序数组
*/
@SuppressWarnings("unchecked")
public static <T> void selectSort(Object[] arrays) {
if (arrays == null || arrays.length == 0) {
return;
}
int minIndex;
for (int out = 0; out < arrays.length - 1; out++) {
minIndex = out;
for (int in = out + 1; in < arrays.length; in++) {
if (((Comparable) arrays[minIndex]).compareTo(arrays[in]) > 0) {
minIndex = in;
}
}
swap(arrays, out, minIndex);
}
}
/**
* 选择排序。
* 按提供的比较器的比较规则进行排序。
* @param arrays 排序数组
* @param compara 排序比较器
*/
public static <T> void selectSort(T[] arrays, Comparator<? super T> compara) {
if (arrays == null || arrays.length == 0) {
return;
}
int minIndex;
for (int out = 0; out < arrays.length - 1; out++) {
minIndex = out;
for (int in = out + 1; in < arrays.length; in++) {
if (compara.compare(arrays[minIndex], arrays[in]) > 0) {
minIndex = in;
}
}
swap(arrays, out, minIndex);
}
}
/**
* 插入排序。
*
* 排序数组中的对象必须实现java.lang.Comparable接口,提供排序比较规则。
* 否则,调用时会抛出运行时异常java.lang.ClassCastException。
*
* 算法描述如下:
* 外层循环控制未排序的数据项及循环交换最小数据项,从数组起始位置开始,向高位递增。
* 内层循环控制查找最小数据项,从外层循环所指向的位置开始,向高位递增。
* 每次内层循环结束,即外层循环移动一次时,数组的左侧将多一项排好序的数据。
*
* 1.外层循环从数组第二项开始,记录当前数据项及其下标。
* 2.当数据项指向的数组下标大于0时,且当前数据项比其前一个数据项大时,交换这两项数据。
* 3.数组下标指针减1,按条件2,循环比较前两项数据。
* 4.当条件不满足时,跳出内层循环,并将外层循环的当前数据项赋予内层指针下标所指的数据项。
* 5.外层循环递增,继续下一排序。
*
* @param arrays 排序数组
*/
@SuppressWarnings("unchecked")
public static void insertSort(Object[] arrays) {
if (arrays == null || arrays.length == 0) {
return;
}
int in;
for (int out = 1; out < arrays.length; out++) {
Object temp = arrays[out];
in = out;
while (in > 0 && ((Comparable) arrays[in - 1]).compareTo(temp) > 0) {
arrays[in] = arrays[in - 1];
in--;
}
arrays[in] = temp;
}
}
/**
* 插入排序。
* 按提供的比较器的比较规则进行排序。
* @param arrays 排序数组
* @param compara 排序比较器
*/
public static <T> void insertSort(T[] arrays, Comparator<? super T> compara) {
if (arrays == null || arrays.length == 0) {
return;
}
int in;
for (int out = 1; out < arrays.length; out++) {
T temp = arrays[out];
in = out;
while (in > 0 && compara.compare(arrays[in - 1], temp) > 0) {
arrays[in] = arrays[in - 1];
in--;
}
arrays[in] = temp;
}
}
/**
* 交换指定数组中的指定下标的两个数据项。
* @param first 第一个数据项的下标
* @param second 第二个数据项的下标
*/
private static void swap(Object[] arrays, int firstIndex, int secondIndex) {
Object temp = arrays[firstIndex];
arrays[firstIndex] = arrays[secondIndex];
arrays[secondIndex] = temp;
}
}
测试代码如下:
package com.zhangsx.sort;
import java.util.Comparator;
import java.util.Random;
import junit.framework.TestCase;
/**
* 测试简单排序算法的实现。
* @version 1.00 2010-4-11
* @since 1.5
* @author ZhangShixi
*/
public class SimpleSortTest extends TestCase {
Person[] persons;
Comparator<Person> comparator;
@Override
protected void setUp() throws Exception {
persons = new Person[10];
comparator = new PersonComparator();
Person person;
Random random = new Random();
for (int count = 0; count < 10; count++) {
int value = random.nextInt(100);
person = new Person("name-" + value, value);
persons[count] = person;
}
display();
}
@Override
protected void tearDown() throws Exception {
display();
}
/**
* 测试冒泡排序算法的实现。
*/
public void testBubbleSort() {
SimpleSort.bubbleSort(persons, comparator);
display();
SimpleSort.bubbleSort(persons);
}
/**
* 测试选择排序算法的实现。
*/
public void testSelectSort() {
SimpleSort.selectSort(persons);
display();
SimpleSort.selectSort(persons, comparator);
}
/**
* 测试插入排序算法的实现。
*/
public void testInsertSort() {
SimpleSort.insertSort(persons);
display();
SimpleSort.insertSort(persons, comparator);
}
/**
* 显示排序结果。
*/
private void display() {
for (Person person : persons) {
System.out.println(person.toString());
}
System.out.println("-------------------");
}
}
数组中的比较对象:实现Comparable接口,按年龄大小升序排序。
package com.zhangsx.sort;
/**
* 人,排序对象。
* @version 1.00 2010-4-11
* @since 1.5
* @author ZhangShixi
*/
public class Person implements Comparable<Person> {
private String name;
private int age;
public Person(String name, int age) {
this.name = name;
this.age = age;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
@Override
public String toString() {
return "Person: [" + this.age + "]";
}
public int compareTo(Person person) {
if (this.age > person.getAge()) {
return 1;
} else if (this.age < person.getAge()) {
return -1;
} else {
return 0;
}
}
}
自定义的对象比较器:按年龄大小降序排序。
package com.zhangsx.sort;
import java.util.Comparator;
/**
* 自定义比较器。
* @version 1.00 2010-4-11
* @since 1.5
* @author ZhangShixi
*/
public class PersonComparator implements Comparator<Person> {
public int compare(Person person1, Person person2) {
if (person1.getAge() > person2.getAge()) {
return -1;
} else if (person1.getAge() < person2.getAge()) {
return 1;
} else {
return 0;
}
}
}
分享到:
相关推荐
第四章 简单排序(C++)_PDF(2020.06.10).rar
介绍了一些简单的排序算法,比如冒泡法,插入法,选择法,交换法,以及快速排序,还有一些有意思的,比如双向冒泡排序,希尔排序等等。
自己写的三个排序算法的比较。快速排序、归并排序、简单排序 对三个排序算法所消耗时间进行统计,比较时间效率 程序是在Linux下用C写的,vc下并未做测试。
VB 排序 简单排序 文本框取数字排序 字符串取数字排序
c++实验之一:简单插入排序 实现简单排序方法
1.10编程基础之简单排序(10题)--题目 有链接.pdf
题目一 简单排序方法 【问题描述】 简单排序算法主要包括冒泡排序、简单选择排序和直接插入排序,它们都是时间复杂度为的排序方法,需要熟练掌握。 【基本要求】 用随机函数产生10000(或更多)个整数(或浮点数...
。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
四种简单的排序算法,简单排序,快速选择排序,希尔排序
一些简单排序的简单Java实现,除了计数排序和基数排序 那两个不太懂,有的来自网上加上了一些自己的注释和解释,方便快速理解排序思想 用于我自己的笔记
链表的简单排序 struct teacher *head;head = creat(); head = play(head);out(head);
Excel简单排序的例子.rar,按“科目名称”笔划顺序升序排序的简单示例。
C#简单排序——Sort(2005),array.sort(),listviewitem.sort(),和Icompare的接口使用.
基于C语言的简单排序,输入10个数字,逆序输出这10个数字,很简单的。
5.简单排序方法.ppt
NULL 博文链接:https://yuan.iteye.com/blog/304808
C++中简单排序算法的实现.docx