算法：排序
一些约定
- java命令行程序
算法的学习和语言无关，下面使用一个
java命令行程序来作为实例程序。 - 一个算法一个类 排序算法使用一个方法就可以表示，不需要是一个对象。但为了让各种排序算法的表示相互独立，接下来分别为它们定义不同的类型，并提供一些工具类来产生随机数序列，打印数字序列，对数列进行校验等。
- 以整数序列升序为例
对应java程序，任何可比较的类型——实现接口
Comparable<T>的类型，都是可排序的。所以一个排序方法的签名大致可以是这样的public <T extends Comparable<? super T>> void sort(T[] items)，不过为了演示的简单，下面使用int[] numbers作为需要排序的数列，并且排序算法对它进行升序排序。
排序方法抽象接口
使用下面的接口SortMethod来抽象表达排序算法：
interface SortMethod {
/**
* sort numbers.
*/
void sort(int[] numbers);
}工具类
定义下面的SortingTools类来提供需要的辅助功能。
public final class SortingTools {
private static Random random = new Random();
public static void testSort(SortMethod method, int numberSize) {
int[] numbers = new int[numberSize];
for (int i = 0; i < numbers.length; i++) {
numbers[i] = random.nextInt(1000);
}
SortingTools.printNumbers(numbers);
Log.println("before sort. isAscending = " + SortingTools.isAscending(numbers));
method.sort(numbers);
SortingTools.printNumbers(numbers);
Log.println("after sort. isAscending = " + SortingTools.isAscending(numbers));
}
public static void printNumbers(int[] numbers) {
for (int i = 0; i < numbers.length; i++) {
Log.print(numbers[i] + ", ");
}
Log.print("\n");
}
public static boolean isAscending(int[] numbers) {
int prev = numbers[0];
for (int i = 1; i < numbers.length; i++) {
if (numbers[i] < prev) {
return false;
}
prev = numbers[i];
}
return true;
}
}- printNumbers(int[] numbers)
用来打印输出numbers，方面查看。
Log.print()方法简单封装了下显示打印的逻辑。 - isAscending(int[] numbers) 用来校验指定序列numbers是否为升序。
- testSort() 测试method所表示的某种排序算法，对于将要学习的各种不同排序算法，测试的过程是一样的。 先随机生成numberSize大小的int[]数组，然后排序前后分别打印输出数组各项，并且对数组是否为升序进行验证。
冒泡排序
先从一个简单的“冒泡排序”开始，实际上即使冒泡排序也有许多高级的变种，这里仅实现基础的算法。
算法思路
假设是N个数字，要完成升序排列，每次从第一个元素开始，依次将较大数字放置到第N、N-1、N-2...位置处。
编码
下面算法的时间效率属于O(N²)：
public class BubbleSort implements SortMethod {
@Override
public void sort(int[] numbers) {
bubbleSort(numbers);
}
public static void bubbleSort(int[] numbers) {
int swap;
for (int end = numbers.length - 1; end > 0; end--) {
for (int i = 0; i < end; i++) {
if (numbers[i] > numbers[i + 1]) {
swap = numbers[i + 1];
numbers[i + 1] = numbers[i];
numbers[i] = swap;
}
}
}
}
}实际的排序方法可以是静态的，然后重写的sort()方法简单地调用它来完成排序。
测试
在main()方法中:
public static void main(String[] args) {
SortingTools.testSort(new BubbleSort(), 20);
}一次输出如下：
246, 558, 286, 652, 470, 905, 11, 102, 705, 498, 695, 769, 86, 189, 986, 317, 957, 471, 406, 625,
before sort. isAscending = false
11, 86, 102, 189, 246, 286, 317, 406, 470, 471, 498, 558, 625, 652, 695, 705, 769, 905, 957, 986,
after sort. isAscending = true本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2017-01-03 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
