交换排序-冒泡排序（详情讲解）

1.0 概述

• 交换排序的基本思想是两两比较待排序记录的关键字，若两个记录的次序相反则交换这两个记录，直到没有反序的记录为止。

• 交换排序主要方法（这一次主要讲解冒泡排序）：

  • 冒泡排序

  • 快速排序

2.0冒泡排序

1.  概述     

• 冒泡排序：Bubble Sort

• 将待排序的数组看成从上到下的存放，把关键字较小的记录看成==较轻的==，关键字较大的记录看成==较重的==，

• 较小关键字值的记录，好像水中的气泡一样，向上浮；

• 较大关键字值的记录，好像水中的石块一样，向下沉；

• 当所有的气泡都浮到了相应的位置，并且所有的石块都沉到了水中，排序就结束了。

      2.1 示意图（方便更加容易理解）      

        2.2 算法分析

• 从第一个记录开始，依次对无序区中相邻记录进行关键字比较，如果大在上，小在下，则交换，第一趟扫描下来表中最大的沉在最下面

• 然后再对前n-1个记录进行冒泡排序，直到排序成功为止。

• 一般，第i趟扫描时，r[0]到r[n-i]和r[i+1]到r[n-1]分别为当前的无序区和有序区。

•   例如拿 {52,39,67,95,70,8,25,52} 做例子

2.3算法：标准版

public void bubbleSort() {    RecordNode temp;    for(int i = 1 ; i < this.curlen; i ++) { //每一趟需要处理好一个数据 for(int j = 0; j  0) {//交换相邻的2个元素  temp = r[j];  r[j] = r[j+1];  r[j + 1] = temp;     }  }    }}

2.4算法：优化版【重点】

//【算法优化】 冒泡排序算法public void bubbleSort() {//    System.out.println("冒泡排序");    RecordNode temp; // 辅助结点    boolean flag = true;    // 是否交换的标记    for (int i = 1; i < this.curlen && flag; i++) {   // 有交换时再进行下一趟，最多n-1趟 flag = false;// 假定元素未交换 for (int j = 0; j  0) { // 逆序时，交换  temp = r[j];  r[j] = r[j + 1];  r[j + 1] = temp;  flag = true;//如果发生交换，记录     } } System.out.print("第" + i + "趟: "); display();    }}

3.0        测试

  public static void main(String[] args) throws Exception { int[] arr = {52,39,67,95,70,8,25,52}; SeqList seqList = new SeqList(arr.length); for (int i = 0; i < arr.length; i++) {     seqList.insert(i, new RecordNode(arr[i])); } // 希尔排序算法 seqList.bubbleSort();    }//冒泡排序//第1趟:  39 52 67 70  8 25 52 95//第2趟:  39 52 67  8 25 52 70 95//第3趟:  39 52  8 25 52 67 70 95//第4趟:  39  8 25 52 52 67 70 95//第5趟:   8 25 39 52 52 67 70 95//第6趟:   8 25 39 52 52 67 70 95