java 通配符的应用— java 排序算法

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，就可以对任意类型使用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;
    }