这几天无聊,又重新学起java的排序算法,为DualPivotQuickSort做准备。为了更好地适应各种情况,我们选择使用通用类型T和通配符的上下界来实现,同时这次谈的是对数组对象的排序。如果你对java 通配符的了解不深的,可以点击 这里 。
现在假设有如下排序方法:
public static <T> void sort(T[] a, int n)
因为对象之间可以比较大小,数组对象必须是实现Comparable接口的。因此T所表示的类必须实现接口Comparable。为此需要为T添加一个上界,如下:
public static <T extends Comparable<T>> void sort(T[] a, int n)
如此,便指定了传递给Sort的对象数组必须是可比较的.为了sort()方法可以更加贴近实际的需要,现在再做一点改进.
现在使用sort()方法对10个Integer对象排序如下:
sort(intArray,10);
代码”T extends Comparable<T>“要求Integer必须实现Comparable<Integer>,并且数组内的对象都必须是Integer对象。详细的使用细则,可参考 java 通配符解惑。 T的对象不仅可以与T的其他对象相互比较,也应该可以与T的超类对象相比较。因此,取代”T extends Comparable<T>“的另一种写法是:
public static <T extends Comparable<? super T>> void sort(T[] a, int n)
一、选择排序:
选择排序是最基本的排序算法 ,一般不怎么用,可却是学排序最基本的算法,了解一下总无害。
迭代伪代码:
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 <T extends Comparable<? super T>> 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)
public static <T extends Comparable<? super T>> 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)
最好的情况:
平均状况:О(n2)
稳定
额外需要的空间:O(n)
java实现:
public static <T extends Comparable<? super T>> 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 <T extends Comparable<? super T>> 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 <T extends Object & Comparable<? super T>> 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 <T extends Comparable<? super T>> void mergeSort(T[] a) { T[] tempArray = (T[]) new Comparable<?>[a.length]; mergeSortHelp(a, tempArray, 0, a.length - 1); } private static <T extends Comparable<? super T>> 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 <T extends Comparable<? super T>> void heapSort(T[] a){ heapSortHelp(a,a.length); } private static <T extends Comparable<? super T>> 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 <T extends Comparable<? super T>> 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 <T extends Comparable<? super T>> 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 <T extends Comparable<? super T>> void quickSort(T[] a) { quickSortHelp(a, 0, a.length - 1); } //left 数组最左边的元素索引,right 数组最右边的元素索引(包含) private static <T extends Comparable<? super T>> 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 <T extends Comparable<? super T>> 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; }
八、其他
这里只是给出了java 通配符的应用实例,并不说明java 排序算法就一定要向上面那要来实现(不过如果使用通配符来实现,会是方法的健壮性更强。