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]); } } }
相关推荐
虽然选择排序的交换操作次数较少,但比较次数仍然为O(N),因此在处理大量数据时,效率不如其他更高级的排序算法如快速排序、归并排序等。然而,选择排序的一个优点是它对原始数据的顺序不敏感,即无论输入数据是否...
- **性能评估**:对不同的数据结构和算法进行时间和空间复杂度的分析,评估其效率。 - **团队合作**:在项目开发过程中,培养团队协作能力,共同完成一个大型项目的设计与实现。 通过本教程的学习,不仅能够掌握...
标题中提到的“Java数据结构和算法”是计算机科学领域中的基础内容,对于学习Java语言的开发者来说尤为重要。数据结构是组织和存储数据的方式,使得数据操作更加高效;算法则是解决问题的一系列步骤。在Java编程中,...
#### 二、Python在算法与数据结构中的应用 1. **Python的基础特性**: - **语法简洁性**:Python的语法简单明了,易于理解和编写,这使得它成为初学者学习数据结构和算法的理想选择。 - **动态类型**:Python是一...
本文档主要聚焦于初级水平的数据结构与算法的学习,适用于初学者掌握基础概念和技术要点。主要内容包括栈、队列、链表等基本数据结构以及递归的概念,并详细介绍了几种排序算法的实现方式。 #### 一、基本概念 **...
- **排序算法**:详细讨论了几种常见的排序算法,包括插入排序(Insertion Sort)、选择排序(Selection Sort)、冒泡排序(Bubble Sort)和归并排序(Merge Sort)。每种算法都有其特定的优势和适用场景。 ##### ...
在编程领域,掌握数据结构和算法是提升编程能力的关键步骤,尤其是在Java这样的高级语言中。本文将深入探讨四种简单的排序算法:插入排序、冒泡排序、选择排序。这些算法虽然在复杂度上不如高级排序算法如快速排序或...
通过这样的实现,我们可以看到C语言如何有效地表达和执行SelectionSort算法。 总结来说,"排序算法-基于C语言实现的排序算法之SelectionSort实现.zip"文件包含了一个C语言实现的SelectionSort排序算法。通过学习和...
通过对“Java数据结构和算法(第二版)”这本书的核心内容进行总结,我们不仅了解了各种基础和高级的数据结构,还深入探讨了几种经典的算法。这些知识对于软件开发人员来说至关重要,它们不仅能帮助我们更好地理解和...
### 数据结构排序算法详解 #### 冒泡排序(Bubble Sort) 冒泡排序是一种简单的排序算法。它重复地遍历要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复进行的,直到没有...
通过以上对数据结构、算法以及C++实现方面的详细阐述,可以看出《数据结构与算法C版本》这本书不仅覆盖了理论基础,还深入到了具体的实现细节和技术要点,对于学习和掌握数据结构与算法具有很高的参考价值。...
Java作为一种广泛应用的编程语言,提供了丰富的工具和库来实现各种数据结构和算法。本项目基于Java语言,深入探讨并实现了多种常用的数据结构与算法,旨在帮助开发者巩固理论知识,提高实际编程能力。 首先,我们要...