Technorati 标记: java,排序算法,通配符
这几天无聊,又重新学起java的排序算法,为DualPivotQuickSort做准备。为了更好地适应各种情况,我们选择使用通用类型T和通配符的上下界来实现,同时这次谈的是对数组对象的排序。如果你对java 通配符的了解不深的,可以点击 这里 。
现在假设有如下排序方法:
public static void sort(T[] a, int n)
因为对象之间可以比较大小,数组对象必须是实现Comparable接口的。因此T所表示的类必须实现接口Comparable。为此需要为T添加一个上界,如下:
public static > void sort(T[] a, int n)
如此,便指定了传递给Sort的对象数组必须是可比较的.为了sort()方法可以更加贴近实际的需要,现在再做一点改进.
现在使用sort()方法对10个Integer对象排序如下:
sort(intArray,10);
代码”T extends Comparable“要求Integer必须实现Comparable,并且数组内的对象都必须是Integer对象。详细的使用细则,可参考 java 通配符解惑。 T的对象不仅可以与T的其他对象相互比较,也应该可以与T的超类对象相比较。因此,取代”T extends Comparable“的另一种写法是:
public static > void sort(T[] a, int n)
“?”代表任意类型,而“? super T”则意味着T的任意超类。写成Comparable super T>,就可以对任意类型使用Comparable。
一、选择排序:
选择排序是最基本的排序算法 ,一般不怎么用,可却是学排序最基本的算法,了解一下总无害。
迭代伪代码:
for i = 0:n-1,
k = i
for j = i+1:n-1, if a[j] < a[k], k = j
//a[k] 总是a[i..n]最小的那一个
swap a[i,k]
//排序的最后结果:a[1..i]
end
性能:
最坏的情况:О(n2)
最好的情况:О(n2)
平均状况:О(n2)
不稳定
额外需要的空间:O(n)
java 实现:
public static > void selectionSort(T[] a){
int smallestIndex;
for(int i = 0;i < a.length; i++){
smallestIndex = i;
for (int j = i+1; j < a.length; j++) {
if (a[j].compareTo(a[smallestIndex]) < 0) {
smallestIndex = j;
}
}
swap(a, i, smallestIndex);
}
}
private static void swap(Object[] a, int i, int j) {
Object temp = a[i];
a[i] = a[j];
a[j] = temp;
}
二、插入排序
插入排序在最坏情况下的效率是O(n2)。在大部分元素已排好序或者排序的元素数量少的情况下,一般选择使用插入排序(因为它是低开销)。
伪代码:
for i = 1:n,
for (k = i; k > 0 and a[k] < a[k-1]; k--)
swap a[k,k-1]
end
性能(效率):
最坏的情况:О(n2)比较,О(n2)交换
最好的情况:O(n) 比较, O(1) 交换
平均状况:О(n2)比较,О(n2)交换
稳定
额外需要的空间:O(n)
java 实现:
public static > void insertionSort(T[] a) {
int len = a.length;
for (int i = 1; i < len; i++) {
for (int k = i; (k > 0) && (a[k].compareTo(a[k - 1]) < 0); k--) {
swap(a, k, k - 1);
}
}
}
三、冒泡排序
冒泡排序与插入排序有很多相似的地方,只不过是冒泡排序的开销稍高。
伪代码:
for i = 0:n-1,
swapped = false
for j = n-1:i+1,
if a[j] < a[j-1],
swap a[j,j-1]
swapped = true
break if not swapped
end
性能:
最坏的情况:О(n2)
最好的情况:O(n)
平均状况:О(n2)
稳定
额外需要的空间:O(n)
java实现:
public static > void bubbleSort(T[] a) {
boolean swapped;
for (int i = 0; i < a.length; i++) {
swapped = false;
for (int j = a.length - 1; j > i; j--) {
if (a[j].compareTo(a[j - 1]) < 0) {
swap(a, j, j - 1);
swapped = true;
}
}
if (!swapped) { break; }
}
}
四、希尔排序
希尔排序属于插入类排序,是将整个无序列分割成若干小的子序列分别进行插入排序。将要排序的一组数按某个增量 gap 分成 gap 组,每组中记录的下标相差 gap.对每组中全部元素进行排序,然后再用一个较小的增量对它进行,在每组中再进行排序。当增量减到1时,整个要排序的数被分成一组,排序完成。
性能:
最坏的情况:取决于增量(在这里的基底是3)
最好的情况:取决于增量
平均状况:取决于增量
不稳定
额外需要的空间:O(n)
java实现:
public static >
void shellSort(T[] a) {
for(int inc = a.length/3; inc > 0; inc /= 3){
for(int index = 0;index < inc; index++){
shellInsertSort(a, index, inc);
}
}
shellInsertSort(a, 0, 1);
}
private static >
void shellInsertSort(T[] a, int start, int inc) {
//插入排序
for(int i = start + inc;i < a.length; i += inc){
for(int index = i;(index >= inc) && (a[index]).compareTo(a[index - inc]) < 0;index -= inc){
swap(a, index, index - inc);
}
}
}
五、归并排序
归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
伪代码:
//将序列分半
mid = n / 2
//递归排序
sort a[1..mid]
sort a[mid+1..n]
//合并已排好序的子序列
b = copy of a[1..m]
low = 1, high = mid+1,
for cur= l:r
if(high > r) || low < mid + 1 && b[low] < b[high])
a[cur] =b[low++]
else
a[cur] =b[high++]
性能:
最坏的情况:O(n log n)
最好的情况:O(n log n)
平均状况:O(n log n)
稳定
额外需要的空间:O(n)
java 实现:
public static > void mergeSort(T[] a) {
T[] tempArray = (T[]) new Comparable>[a.length];
mergeSortHelp(a, tempArray, 0, a.length - 1);
}
private static >
void mergeSortHelp(T[] a, T[] tempArray, int l, int r) {
int mid = (l + r) >>> 1;
if (l == r) {
return;
}
mergeSortHelp(a, tempArray, l, mid);
mergeSortHelp(a, tempArray, mid + 1, r);
System.arraycopy(a, l, tempArray, l, r - l + 1);
int low = l;
int high = mid + 1;
for (int cur = l; cur <= r; cur++) {
if ((high > r) || low < mid + 1 && (tempArray[low].compareTo(tempArray[high]) < 0)) {
a[cur] = tempArray[low++];
} else {
a[cur] = tempArray[high++];
}
}
}
六、堆排序
堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法,可以利用数组的特点快速定位指定索引的元素。堆排序(heapSort)主要分为两个步骤:第一步,根据初始数据,利用堆的调整算法 siftdown()形成初始堆;第二步,反复地移除堆中最大的数据(将其插入数组里),移除之后再继续对利用堆的调整算法对剩下的数据进行调整。
伪代码:
function heapSort(a, count)
heapify(a, count)//形成初始堆(大根堆)
end := count-1 //子女元素的索引为 2*i+1 and 2*i+2
while end > 0
swap(a[end], a[0]) //交换堆中最大的元素
end := end - 1 //减少堆中元素的个数,重新调整为大根堆
siftDown(a, 0, end)
function heapify(a, count)
start := (count - 2 ) / 2 //将start作为根节点
while start ≥ 0
siftDown(a, start, count-1)
start := start - 1
function siftDown(a, start, end) is
root := start
while root * 2 + 1 ≤ end do //有子节点
child := root * 2 + 1 //左子节点
swap := root //暂存子树根节点)
if a[swap] < a[child] //判断根节点与左子节点的大小
swap := child
//如果存在右子节点,则比较两子节点的大小
if child+1 ≤ end and a[swap] < a[child+1]
swap := child + 1
//判断子节点是否比根节点大
if swap != root
swap(a[root], a[swap])
root := swap //根节点下降到子节点
else
return
性能:
最坏的情况:O(n log n)
最好的情况:O(n )
平均状况:O(n log n)
不稳定
额外需要的空间:O(n)
java 实现:
public static > void heapSort(T[] a){
heapSortHelp(a,a.length);
}
private static >
void heapSortHelp(T[] a, int length) {
heapify(a,a.length); //调整为大根堆的形式
int end = a.length - 1;
while(end > 0){
swap(a, 0, end);
end--;
siftDown(a,0,end);
}
}
private static > void heapify(T[] a, int length) {
int currentSize = length; //存储根堆的元素个数
int start = (currentSize - 2) >>> 1;
while (start >= 0) {
siftDown(a,start,currentSize - 1);
start--;
}
}
private static >
void siftDown(T[] a, int start, int end) {
int root = start;
while (2*root + 1 <= end) {
int child = 2*root + 1;
int exchange = root;
if (a[exchange].compareTo(a[child]) < 0) {
exchange = child;
}
if ((child + 1 <= end) && (a[child].compareTo(a[child + 1]) < 0)) {
exchange = child + 1;
}
if (exchange != root) {
swap(a, exchange, root);
root = exchange;
}else{
return;
}
}
}
七、快速排序
快速排序(Quicksort)是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
伪代码:
function quicksort(array, left, right)
// 子序列有两个或多个元素
if left < right
选取基准元素,索引pivotIndex //left ≤ pivotIndex ≤ right
// 确定基准元素的最终存放位置
pivotNewIndex := partition(array, left, right, pivotIndex)
// 递归快速排序
quicksort(array, left, pivotNewIndex - 1)
quicksort(array, pivotNewIndex + 1, right)
function partition(array, left, right, pivotIndex)
pivotValue := array[pivotIndex]
swap array[pivotIndex] and array[right] // 将基准元素移到最后
storeIndex := left
for i from left to right - 1 // left ≤ i < right
if array[i] < pivotValue
swap array[i] and array[storeIndex]
storeIndex := storeIndex + 1
swap array[storeIndex] and array[right] //将基准元素存到其最终存放位置
return storeIndex
性能:
最坏的情况:O(n2)
最好的情况:O(n log n)
平均状况:O(n log n)
不稳定
额外需要的空间:O(n)
java 实现:
public static > void quickSort(T[] a) {
quickSortHelp(a, 0, a.length - 1);
}
//left 数组最左边的元素索引,right 数组最右边的元素索引(包含)
private static >
void quickSortHelp(T[] a, int left, int right) {
if (left < right) {
int privotIndex = (left + right) >>> 1;
int privotNewIndex = partition(a, left, right, privotIndex);
//递归快速排序(分而治之)
quickSortHelp(a, left, privotNewIndex - 1);
quickSortHelp(a, privotNewIndex + 1, right);
}
}
private static >
int partition(T[] a, int left, int right, int privotIndex) {
T privotValue = a[privotIndex];
swap(a, privotIndex, right);
int storeIndex = left;
for (int i = left; i < right; i++) {
if (a[i].compareTo(privotValue) < 0) {
swap(a, i, storeIndex);
storeIndex++;
}
}
swap(a, storeIndex, right);
return storeIndex;
}
阅读(1164) | 评论(0) | 转发(0) |