`
sunwinner
  • 浏览: 202197 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

基础数据结构和算法二:Selection sort

阅读更多

 

One of the simplest sorting algorithms works as follows: First, find the smallest item in the array and exchange it with the first entry (itself if the first entry is already the smallest). Then, find the next smallest item and exchange it with the sec- ond entry. Continue in this way until the entire array is sorted. This method is called selection sort because it works by repeatedly selecting the smallest remaining item.

 

Time complexity: Selection sort uses ~N^2 / 2 compares and N exchanges to sort an array of length N.

public class Selection {

    // selection sort
    public static void sort(Comparable[] a) {
        int N = a.length;
        for (int i = 0; i < N; i++) {
            int min = i;
            for (int j = i+1; j < N; j++) {
                if (less(a[j], a[min])) min = j;
            }
            exch(a, i, min);
            assert isSorted(a, 0, i);
        }
        assert isSorted(a);
    }

    // use a custom order and Comparator interface - see Section 3.5
    public static void sort(Object[] a, Comparator c) {
        int N = a.length;
        for (int i = 0; i < N; i++) {
            int min = i;
            for (int j = i+1; j < N; j++) {
                if (less(c, a[j], a[min])) min = j;
            }
            exch(a, i, min);
            assert isSorted(a, c, 0, i);
        }
        assert isSorted(a, c);
    }


   /***********************************************************************
    *  Helper sorting functions
    ***********************************************************************/
    
    // is v < w ?
    private static boolean less(Comparable v, Comparable w) {
        return (v.compareTo(w) < 0);
    }

    // is v < w ?
    private static boolean less(Comparator c, Object v, Object w) {
        return (c.compare(v, w) < 0);
    }
        
        
    // exchange a[i] and a[j]
    private static void exch(Object[] a, int i, int j) {
        Object swap = a[i];
        a[i] = a[j];
        a[j] = swap;
    }


   /***********************************************************************
    *  Check if array is sorted - useful for debugging
    ***********************************************************************/

    // is the array a[] sorted?
    private static boolean isSorted(Comparable[] a) {
        return isSorted(a, 0, a.length - 1);
    }
        
    // is the array sorted from a[lo] to a[hi]
    private static boolean isSorted(Comparable[] a, int lo, int hi) {
        for (int i = lo + 1; i <= hi; i++)
            if (less(a[i], a[i-1])) return false;
        return true;
    }

    // is the array a[] sorted?
    private static boolean isSorted(Object[] a, Comparator c) {
        return isSorted(a, c, 0, a.length - 1);
    }

    // is the array sorted from a[lo] to a[hi]
    private static boolean isSorted(Object[] a, Comparator c, int lo, int hi) {
        for (int i = lo + 1; i <= hi; i++)
            if (less(c, a[i], a[i-1])) return false;
        return true;
    }



    // print array to standard output
    private static void show(Comparable[] a) {
        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i]);
        }
    }
}

 

分享到:
评论
1 楼 20131007 2013-11-19  
用java描述算法?

相关推荐

    Java数据结构及算法实例:选择排序 Selection Sort

    虽然选择排序的交换操作次数较少,但比较次数仍然为O(N),因此在处理大量数据时,效率不如其他更高级的排序算法如快速排序、归并排序等。然而,选择排序的一个优点是它对原始数据的顺序不敏感,即无论输入数据是否...

    数据结构与算法教程(C++版)实验和课程设计

    - **性能评估**:对不同的数据结构和算法进行时间和空间复杂度的分析,评估其效率。 - **团队合作**:在项目开发过程中,培养团队协作能力,共同完成一个大型项目的设计与实现。 通过本教程的学习,不仅能够掌握...

    Java数据结构和算法

    标题中提到的“Java数据结构和算法”是计算机科学领域中的基础内容,对于学习Java语言的开发者来说尤为重要。数据结构是组织和存储数据的方式,使得数据操作更加高效;算法则是解决问题的一系列步骤。在Java编程中,...

    Java数据结构与算法概述-初级篇.docx

    本文档主要聚焦于初级水平的数据结构与算法的学习,适用于初学者掌握基础概念和技术要点。主要内容包括栈、队列、链表等基本数据结构以及递归的概念,并详细介绍了几种排序算法的实现方式。 #### 一、基本概念 **...

    数据结构与算法-作者Aho

    - **排序算法**:详细讨论了几种常见的排序算法,包括插入排序(Insertion Sort)、选择排序(Selection Sort)、冒泡排序(Bubble Sort)和归并排序(Merge Sort)。每种算法都有其特定的优势和适用场景。 ##### ...

    《Java数据结构和算法》学习笔记(2)——4种简单排序算法

    在编程领域,掌握数据结构和算法是提升编程能力的关键步骤,尤其是在Java这样的高级语言中。本文将深入探讨四种简单的排序算法:插入排序、冒泡排序、选择排序。这些算法虽然在复杂度上不如高级排序算法如快速排序或...

    排序算法-基于C语言实现的排序算法之SelectionSort实现.zip

    通过这样的实现,我们可以看到C语言如何有效地表达和执行SelectionSort算法。 总结来说,"排序算法-基于C语言实现的排序算法之SelectionSort实现.zip"文件包含了一个C语言实现的SelectionSort排序算法。通过学习和...

    Java数据结构和算法(第二版)

    通过对“Java数据结构和算法(第二版)”这本书的核心内容进行总结,我们不仅了解了各种基础和高级的数据结构,还深入探讨了几种经典的算法。这些知识对于软件开发人员来说至关重要,它们不仅能帮助我们更好地理解和...

    数据结构排序算法

    ### 数据结构排序算法详解 #### 冒泡排序(Bubble Sort) 冒泡排序是一种简单的排序算法。它重复地遍历要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复进行的,直到没有...

    数据结构与算法C版本

    通过以上对数据结构、算法以及C++实现方面的详细阐述,可以看出《数据结构与算法C版本》这本书不仅覆盖了理论基础,还深入到了具体的实现细节和技术要点,对于学习和掌握数据结构与算法具有很高的参考价值。...

    基于java的数据结构与算法的实现(持续更新)

    Java作为一种广泛应用的编程语言,提供了丰富的工具和库来实现各种数据结构和算法。本项目基于Java语言,深入探讨并实现了多种常用的数据结构与算法,旨在帮助开发者巩固理论知识,提高实际编程能力。 首先,我们要...

    基于Java的数据结构与算法实现.zip

    通过这些实现,用户可以深入理解各种算法的原理和应用场景,同时也可以作为学习和实践数据结构与算法的参考。 项目的主要特性和功能 1. 排序算法 冒泡排序(Bubble Sort) 选择排序(Selection Sort) 插入...

    Java数据结构和算法中文3(第二版)

    根据提供的信息,我们可以推断《Java数据结构和算法中文3(第二版)》是一本专注于Java编程语言中的数据结构与算法应用的专业书籍。虽然提供的部分内容并没有包含实际的章节或者具体的讲解内容,但根据书名、描述及...

Global site tag (gtag.js) - Google Analytics