排序算法：冒泡排序与选择排序详解

### 排序算法：冒泡排序与选择排序详解 #### 1. 冒泡排序 冒泡排序是一种简单的排序算法，其核心思想是通过多次比较和交换相邻元素，将最大的元素逐步“冒泡”到数组的末尾。 ##### 1.1 算法步骤 - 从数组的第一个元素开始，依次比较相邻的两个元素。如果前一个元素大于后一个元素，则交换它们的位置。 - 重复上述步骤，直到到达数组的最后一个元素。此时，最大的元素已经位于数组的末尾。 - 再次从数组的第一个元素开始，重复上述步骤，但这次只需要比较到倒数第二个元素，因为最后一个元素已经是最大的了。 - 不断重复上述步骤，每次比较的范围逐渐缩小，直到整个数组有序。 以下是冒泡排序的流程图： ```mermaid graph TD; A[开始] --> B[从第一个元素开始比较相邻元素]; B --> C{前一个元素是否大于后一个元素}; C -- 是 --> D[交换两个元素的位置]; C -- 否 --> E[继续比较下一对相邻元素]; D --> E; E --> F{是否到达数组末尾}; F -- 否 --> B; F -- 是 --> G[缩小比较范围，排除已排序的元素]; G --> H{是否所有元素都已排序}; H -- 否 --> B; H -- 是 --> I[结束]; ``` ##### 1.2 冒泡排序工作坊小程序 为了更好地理解冒泡排序的过程，可以使用冒泡排序工作坊小程序。该小程序提供了一个可视化的界面，展示了冒泡排序的具体过程。 - **运行按钮**：点击运行按钮，小程序将自动执行冒泡排序算法，在大约10秒内完成排序。 - **新建按钮**：点击新建按钮，将创建一组新的随机排列的条形图。多次点击新建按钮，可以在随机排列和逆序排列之间切换。 - **单步按钮**：点击单步按钮，可以逐一步骤地执行排序算法，观察每一次比较和交换的过程。 - **大小按钮**：点击大小按钮，可以在10个条形图和100个条形图之间切换。对于100个条形图，建议使用运行按钮进行排序。 - **绘制按钮**：如果在排序过程中出现显示问题，可以点击绘制按钮重新绘制所有条形图。 ##### 1.3 Java代码实现 以下是冒泡排序的Java代码实现： ```java // bubbleSort.java // demonstrates bubble sort // to run this program: C>java BubbleSortApp //////////////////////////////////////////////////////////////// class ArrayBub { private long[] a; // ref to array a private int nElems; // number of data items //-------------------------------------------------------------- public ArrayBub(int max) // constructor { a = new long[max]; // create the array nElems = 0; // no items yet } //-------------------------------------------------------------- public void insert(long value) // put element into array { a[nElems] = value; // insert it nElems++; // increment size } //-------------------------------------------------------------- public void display() // displays array contents { for(int j=0; j<nElems; j++) // for each element, System.out.print(a[j] + " "); // display it System.out.println(""); } //-------------------------------------------------------------- public void bubbleSort() { int out, in; for(out=nElems-1; out>1; out--) // outer loop (backward) for(in=0; in<out; in++) // inner loop (forward) if( a[in] > a[in+1] ) // out of order? swap(in, in+1); // swap them } // end bubbleSort() //-------------------------------------------------------------- private void swap(int one, int two) { long temp = a[one]; a[one] = a[two]; a[two] = temp; } //-------------------------------------------------------------- } // end class ArrayBub //////////////////////////////////////////////////////////////// class BubbleSortApp { public static void main(String[] args) { int maxSize = 100; // array size ArrayBub arr; // ```