首先,排序算法阐明了许多解决问题的创造性的方法,并且这些方法还可用于解决其他问题。其次,排序算法有助于使用选择语句、循环、方法和数组来练习基本的程序设计技术。最后,排序算法是演示算法性能的极好的例子。
为了简单起见,下面的知识假定:
1)要排序的数据是整数;
2)数据存储在数组中;
3)数据以升序排列。
冒泡排序算法需要遍历几次数组。在每次遍历中,比较连续相邻的元素。如果某一对元素是降序,则互换它们的值;否则,保持不变。由于较小的值像“气泡”一样逐渐浮向顶部,而较大的值沉向底部,所以称这种技术为冒泡排序或下沉排序。
例如,
for (int k = 1; k < list.length; k++) { //Perform the kth pass for (int i = 0; i < list.length - k; i++) { if (list[i] with list[i + 1]; swap list[i] with list[i + 1]; } }
注意,如果在某次遍历中没有发生交换,那么不必进行下一次遍历,因为所有的元素都已近排好序了。
例如,改进的冒泡排序算法
boolean needNextPass = true; for (int k = 1; k < list.length && needNextPass; k++) { // Array may be sorted and next pass not needed needNextPass = false; //Perform the kth pass for (int i = 0; i < list.length - k; i++) { if (list[i] with list[i + 1]; swap list[i] with list[i + 1]; needNextPass = true; // Next pass still needed } }
归并排序算法可以归递地描述为:算法将数组分为两半,对每部分递归地应用归并地应用并归排序。这两部分都排好序后,对它们进行归并。
例如,
public static void mergeSort(int[] list) { if (list.length > 1) { mergeSort(list[0 … list.length / 2]); mergeSort(list[list.length / 2 + 1 … list.length]); merge list[0 … list.length / 2] with list[list.length / 2 + 1 … list.length]; } }
快速排序是由C.A.R.Hoare开发的,该算法在数组中选择一个称为主元的元素,将数组分为两部分,使得第一部分中的所有元素都小于或等于主元,而第二部分中的所有元素都大于主元。
例如,
public static void quickSort(int[] list) { if (list.length > 1) { select a pivot; partition list into list1 and list2 such that all elements in list1 <= pivot and all elements in list2 > quickSort(list1); quickSort(list2); } }
堆排序使用的是二叉堆,它是一棵完全二叉树。二叉树是一种层次体系结构。它可能是空的,也可能包含一个称为根的元素以及称为左子树和右子数的两棵不同的二叉树。一条路径的长度是指这条路径上的边数。一个结点的深度是指从根结点到该结点的路径的长度。
堆是一棵具有以下属性的二叉树:
1)它是一棵完全二叉树
2)每个结点大于或等于它的任意一个孩子
桶排序算法的工作方式如下。假设键值额范围是从0到N-1。我们需要N个标记为0,1,…,N-1的桶。如果元素的键值是i,那么就将该元素放入桶i中。每个桶中都存在和键值具有相同值的元素。可以使用ArrayList来实现一个桶。
例如,桶排序算法对一个线性表中元素的排序:
void bucketSort(E[] list) { E[] buckets = (E[])new java.util.ArrayList[N]; //Distribute the elements from list to buckets for (int i = 0; i < list.length; i++) { int key = list[i].getKey(); if (buckets[key] == null) buckets[key] = new java.util.ArrayList(); buckets[key].add(list[i]); } // Now move the elements from the buckets back to list int k = 0; // k is an index for list for (int i = 0; i < buckets.length; i++) { if (buckets[i] != null) { for (int j = 0; j < buckets[i].size(); j++) list[k++] = buckets[i].get(j); } } }
很明显,它需要耗费O(n+N)时间来对线性表排序,使用的空间是O(n+N),其中n是指线性表的大小。
注意,如果N太大,那么桶排序不是很可取。此时,可以使用基数排序。基数排序是基于桶排序的,但是它只使用十个桶。