文档章节

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

天地一MADAO_
 天地一MADAO_
发布于 2014/03/02 00:07
字数 2551
阅读 103
收藏 8

  这几天无聊,又重新学起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)

             “?”代表任意类型,而“? 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 <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)

      

java 实现:

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)

    最好的情况O(n)

    平均状况:О(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 排序算法就一定要向上面那要来实现(不过如果使用通配符来实现,会是方法的健壮性更强。


本文转载自:http://peiquan.blog.51cto.com/7518552/1309060

共有 人打赏支持
天地一MADAO_
粉丝 29
博文 37
码字总数 37041
作品 0
东城
其他
私信 提问
【目录导航】JAVA零基础进阶之路

【JAVA零基础入门系列】(已完结)导航目录 Day1 开发环境搭建 Day2 Java集成开发环境IDEA Day3 Java基本数据类型 Day4 变量与常量 Day5 Java中的运算符 Day6 Java字符串 Day7 Java输入与输出...

MFrank
2018/06/21
0
0
提给程序员和开发者的 10 道 Java 泛型面试题

关于泛型的面试题在 Java面试中变得越来越常见,因为 Java 5问世已经有相当长的时间了,越来越多的应用已经迁移到Java 5上来了,并且几乎所有新的Java开发工作也都是在Tiger(Java 5的项目代号...

lwei
2013/10/18
13.2K
30
Kotlin 泛型 VS Java 泛型

建议先阅读我的上一篇文章 -- Java 泛型 和 Java 泛型一样,Kotlin 泛型也是 Kotlin 语言中较难理解的一个部分。Kotlin 泛型的本质也是参数化类型,并且提供了编译时强类型检查,实际上也是伪...

JohnnyShieh
2018/06/11
0
0
【Java学习路线】新手该如何一步步的学习 Java

新手该如何一步步的学习 Java? 如果真的想学Java,最好要循序渐进,有章有法的学习它! 今天小慕就不说一些学习方法和技巧了,直接来谈每个阶段要学习的内容。 首先,给大家分享一张以 企业...

Eddie_yang
2018/11/15
131
0
10 道关于 Java 泛型的面试题

1.Java中的泛型是什么 ? 使用泛型的好处是什么? 这是在各种Java泛型面试中,一开场你就会被问到的问题中的一个,主要集中在初级和中级面试中。那些拥有Java1.4或更早版本的开发背景的人都知道...

蚂蚁-Declan
2018/10/24
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Android 保活

1.Android不间断上报位置信息-应用进程防杀指南 2.Android锁屏无法继续定位问题 3.微信 Android 客户端后台保活经验分享

IT追寻者
19分钟前
1
0
基于Kubernetes的Spark集群部署实践

Spark是新一代分布式内存计算框架,Apache开源的顶级项目。相比于Hadoop Map-Reduce计算框架,Spark将中间计算结果保留在内存中,速度提升10~100倍;同时它还提供更丰富的算子,采用弹性分布...

hblt-j
20分钟前
4
0
NTP服务搭建

NTP服务搭建 如果是单独安装这个服务,请直接开始即可。如果是为了解决hadoop集群的时针偏差问题,配置ntp服务时,务必先关闭chd的相关服务。 一、准备环境 1、操作系统 CentOS7操作系统,准...

星汉
21分钟前
3
0
SPring AOP(面向切面编程)

AOP(面向切面编程) AOP是OOP(面向对象编程)的延续,但是它和面向对象的纵向编程不同,它是一个横向的切面式的编程。可以理解为oop就是一根柱子,如果需要就继续往上加长,而aop则是在需要...

MrBoyce
21分钟前
3
0
高性能Mysql:复制

1 复制概述 Mysql内建的复制功能是构建大型,高性能应用程序的基础。将Mysql的数据分布到多个系统上去,这种分布的机制,是通过将Mysql的某一台主机的数据复制到其它主机(slaves)上,并重新...

watermelon11
24分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部