复旦大学961-数据结构-第四章-排序（二）冒泡排序,快速排序；选择排序,堆排序

Myth丶恋晨 2022-12-12 15:28 138阅读 0赞

[961全部内容链接][961]

### 文章目录 ###

*  交换排序
 *   *  冒泡排序
     *  快速排序
 *  选择排序
 *   *  简单选择排序
     *  堆排序

# 交换排序 #

交换排序就是通过交换两个元素的位置，然后实现的排序。就是排序过程中，需要频繁交换两个元素的位置

## 冒泡排序 ##

这个是比较基本的排序算法，没学过也应该能自己想到。大致原理就像气泡往上冒。基本思想为：从最后一个元素开始，依次与前一个元素对比，若小于前一个元素，则两个元素交换位置，直到对比到第一个元素。然后进入下一轮，还从最后一个元素开始比较，这次比较到第二个元素，重复刚才的动作，依次类推。

public static void bubbleSort(Comparable[] array) { 
        if (array == null) return;
    
        // 第一轮从最后一位对比到第0位，第二轮从最后一位对比到第1位，依次类推，当n轮过去后，即排序完毕
        for (int i = 0; i < array.length - 1; i++) { 
            boolean flag = false; // 定义flag，标记是否发生了交换，若某轮没发生交换，说明已经有序，不需要再对比下去
            // 从最后一个开始，不断向前对比，直到对比到i位置。
            for (int j = array.length - 1; j > i; j--) { 
                if (array[j].compareTo(array[j - 1]) < 0) {  // 若后一位比前一位小，则交换两个位置，并标记发生了交换
                    Comparable temp = array[j - 1];
                    array[j - 1] = array[j];
                    array[j] = temp;
                    flag = true;
                }
            }
            if (!flag) return;  // 若该轮对比结束时没有发现有元素发生交换，说明已经有序，不需要再进行后续对比
        }
    }

易错点：

1.  别忘了加flag，若某轮没有发生交换，说明已经有序，不需要再进行后续对比
2.  第一层for循环，i<array.length-1，可以减1，也可以不减，个人建议减1。不会对整体时间有太大影响
3.  第二层for循环，j>i，虽然大于j>0也不会对最终结果造成影响，但是每轮都会做许多无用的对比，对效率影响较大。

复杂度分析：

*  时间复杂度：最好的时间复杂度为O(n)，平均时间复杂度和最坏的时间复杂度为O(n^2)
 *  空间复杂度：O(1)

稳定性：稳定的。在两个元素交换时，若相等，则不发生交换

适用性：顺序存储和链式存储均可。

## 快速排序 ##

快速排序也是利用交换，基本思想为：每次将一个元素放到它最终的位置，即数组排好序后它应该在的位置。具体做法为：首先选定一个元素作为“枢纽(pivot)”（比如选择第一个元素），之后通过第一轮比较交换，将数组分为三个部分，“小于枢纽”，“枢纽”，“大于枢纽”，这个过程称为**partition**。然后再递归的对小于枢纽的部分和大于枢纽的部分进行再次进行同样的操作。最终完成快速排序。

举例，对于无序数列8975339012进行快速排序：

<table> 
 <thead> 
  <tr> 
   <th></th> 
   <th>8</th> 
   <th>9</th> 
   <th>7</th> 
   <th>5</th> 
   <th>3</th> 
   <th>3</th> 
   <th>9</th> 
   <th>0</th> 
   <th>1</th> 
   <th>2</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>第一轮</td> 
   <td>7</td> 
   <td>5</td> 
   <td>3</td> 
   <td>3</td> 
   <td>0</td> 
   <td>1</td> 
   <td>2</td> 
   <td>8 (pivot)</td> 
   <td>9</td> 
   <td>9</td> 
  </tr> 
  <tr> 
   <td>第二轮</td> 
   <td>5</td> 
   <td>3</td> 
   <td>3</td> 
   <td>0</td> 
   <td>1</td> 
   <td>2</td> 
   <td>7(pivot)</td> 
   <td>8</td> 
   <td>9(pivot)</td> 
   <td>9</td> 
  </tr> 
  <tr> 
   <td>第三轮</td> 
   <td>3</td> 
   <td>3</td> 
   <td>0</td> 
   <td>1</td> 
   <td>2</td> 
   <td>5(pivot)</td> 
   <td>7</td> 
   <td>8</td> 
   <td>9</td> 
   <td>9</td> 
  </tr> 
  <tr> 
   <td>第四轮</td> 
   <td>0</td> 
   <td>1</td> 
   <td>2(pivot)</td> 
   <td>3</td> 
   <td>3</td> 
   <td>5</td> 
   <td>7</td> 
   <td>8</td> 
   <td>9</td> 
   <td>9</td> 
  </tr> 
 </tbody> 
</table>

在该例子中：

1.  第一轮选择8作为枢纽，然后将8放到了它的最终位置，左边的都比8小，右边的都比8大。
2.  第二轮，即将8左边的和右边的元素进行递归执行1操作。所以第二轮左边枢纽为7，右边枢纽为9。
3.  之后的依次类推

Java代码：

public static void quickSort(Comparable[] array) { 
        if (array == null) return;
        quickSort(array, 0, array.length - 1); // 对整个数组进行快速排序
    }
    
    private static void quickSort(Comparable[] array, int left, int right) { 
        if (left >= right) return; // 当左节点与右节点重合时，说明该快速排序只有一个元素，直接返回。 这个不能漏，否则递归会永远递归下去。
        // 对 [left,right]这个范围内的数据进行partition操作，将数组分为 小于等于枢纽，枢纽和大于枢纽，然后返回这个枢纽的下标
        int position = partition(array, left, right);
        quickSort(array, left, position - 1);  // partition后，对其左边再次进行快速排序
        quickSort(array, position + 1, right); // 对其右边再次进行快速排序
    }
    
    private static int partition(Comparable[] array, int left, int right) { 
        int pivotPosition = left;  // 存储left的位置，要不然后面left被修改了，最开始位置就丢失了
        Comparable pivot = array[left];  // 定义枢纽
        left++;  // left原先的位置变成枢纽了，所以+1
        while (left <= right) {   // 当left超过right时跳出循环，注意，left和right重合时不能跳出循环，因为重合时那个节点还没有与枢纽进行比较。
            if (array[left].compareTo(pivot) > 0) {   // 如果left元素大于枢纽，则与right交换位置，同时right往左移动一位，即-1
                Comparable temp = array[left];
                array[left] = array[right];
                array[right] = temp;
                right--;
            } else {   // 如果left元素小于或等于枢纽，那么不发生交换，left直接右移即可。
                left++;
            }
        }
    
        // 当循环结束时，right及其左边的都是小于等于枢纽的，right右边的都是大于枢纽的。
        // 所以让枢纽再跟right换一下位置。那么就变成了枢纽左边的都是小于等于枢纽的，枢纽右边的都是大于等于枢纽的。
        // 这里的right = left - 1，所以right也可以换成left-1
        Comparable temp = array[pivotPosition];
        array[pivotPosition] = array[right];
        array[right] = temp;
        return right; // 返回枢纽的位置
    }

易错点：

1.  在递归的quickSort中，if (left >= right) return; 这句代码容易忽略，导致递归无限循环下去
2.  partition的while循环，left<=right，容易遗漏等号，认为left和right重合就跳出循环，导致最后一个元素没有被partition。
3.  partition的过程多种多样，即left和right指针的移动方式，初始位置等可以有多种写法。只要结果正确就可以。

复杂度分析：

*  空间复杂度：最好的情况，即每次partition操作后，枢纽都在中间位置，这样递归工作栈的最大深度为 log n，所以最好的空间复杂度为 O(log n)，平均情况也是如此。但如果元素一开始就是有序的，那么每次partition操作后，枢纽都在最左边，就会导致递归调用栈的深度为n-1，所以最坏的空间复杂度为O(n)
 *  时间复杂度：最好与最坏的情况与空间效率类似，最好和平均的时间复杂度为O(n\*log n)，最坏的时间复杂度为O(n^2)

稳定性：不稳定。在partition的过程中，会导致两个相同的元素相对位置发生改变。

适用性：仅适用于顺序存储。

# 选择排序 #

选择排序的思路就是每次从数组中选出一个最小的元素放在数组的前面。

## 简单选择排序 ##

直接利用选择排序的思想，没有什么其他心机。基本思想：从数组的第0位开始，从数组的中未排序的数组中选出一个最小的元素，与该位置进行交换。后面以此类推

Java代码：

public static void selectSort(Comparable[] array) { 
        for (int i=0; i <array.length - 1; i ++) { 
            int min = i;
            for (int j=i+1; j<array.length; j++) { 
                if (array[min].compareTo(array[j]) > 0) min = j;
            }
    
            if (i != min) { 
                Comparable temp = array[i];
                array[i] = array[min];
                array[min] = temp;
            }
        }
    }

易错点：

1.  第一次层for循环, i<array.length-1，这个减1也可以不减
2.  循环结束时的if(i != min)判断可以不加，如果它们相等，换一下也没什么

复杂度分析：  
空间复杂度：O(1)  
时间复杂度：最好，最坏，平均时间复杂度都是O(n^2)

稳定性：不稳定。假设数组为\{2,**2**,1\}，简单排序之后会变成\{1,**2**,2\}。2的相对位置发生了变化

适用性：适用于顺序存储和链式存储。

## 堆排序 ##

堆排序是堆这种数据结构的其中一个应用。堆排序基本思想是：将数组构建成一个大根堆（也叫大顶堆，最大堆）。然后将大根堆的堆顶元素出队，然后再次将堆变成大根堆，然后再出队。

具体堆操作去复习前面章节的“优先队列与堆”

Java代码如下：

public static void heapSort(Comparable[] array) { 
        int size = array.length; // 堆的大小
    
        // 叶子节点公式: i<=size/2-1为叶子节点，否则为分支节点（i>size/2-1）
        // 首先构建大根堆：从最后一个分支节点开始，一直到堆顶，每个元素都进行下滤操作。
        for (int i = size / 2 - 1; i >= 0; i--) { 
            percolateDown(array, i, size);
        }
    
        while (size > 0) { 
            // 将堆顶元素与最后一个元素交换，即将最大的元素放入堆的最后，然后将堆的大小-1
            Comparable temp = array[size - 1];
            array[size - 1] = array[0];
            array[0] = temp;
            size--;
    
            percolateDown(array, 0, size); // 对堆顶元素进行下滤操作，调整大根堆
        } // 当堆为空时，排序完成
    }
    
    private static void percolateDown(Comparable[] array, int i, int size) { 
        Comparable x = array[i];  // 暂存要调整的元素
    
        while (i <= size / 2 - 1) { 
            int child = i * 2 + 1; // 访问节点的左孩子
            if (child + 1 < size && array[child].compareTo(array[child + 1]) < 0) { 
                child++; // 如果节点有右孩子，且右孩子大于左孩子，则将child执行节点的右孩子
            }
            if (x.compareTo(array[child]) < 0) {  // 如果x比它更大的那个孩子要小，则交换位置
                array[i] = array[child]; // 将节点的值修改为其更大的那个孩子的值
                i = child; // i移动到其孩子的位置，这步别忘了
            } else { 
                // 如果x比它更大的那个孩子要大，则下滤完成，跳出循环
                break;
            }
        } // 若节点还是分支节点，就继续下滤，若为叶节点，则跳出循环
        array[i] = x; // 下滤完成后，修改最终位置的值
    }

易错点：

1.  由于该堆是从0开始算的，所以孩子节点的计算公式为：i×2+1(左孩子)，i×2+2(右孩子)
2.  叶子节点公式: i<=size/2-1为叶子节点，否则为分支节点（i>size/2-1）
3.  在构建堆时的for循环，i>=0，不能忽略等号，因为堆顶元素也要下滤。
4.  每次从堆顶拿出元素后，别忘了让堆的size减1
5.  当在下滤代码中，当判断完左右孩子的大小时，替换父节点前，别忘了判断父节点与其孩子节点的大小。我这就每次都容易忘。若父节点比他的孩子节点大，就不用再下滤了。
6.  当判断完左右孩子大小后，别忘了让i值指向其孩子节点。

复杂度分析：  
空间复杂度：没有使用额外空间。空间复杂度O(1)  
时间复杂度：建堆所需时间O(n)，之后向下调整了n-1次，每次调成的时间复杂度为O(h)，h为树高。所以最好、最坏和平均情况下，堆排序的时间复杂度为O(n\*log n)

稳定性：不稳定。因为要把第一个节点和堆底元素做交换。所以可能会发生相对位置变化。如\{1,**2**,2\}，构建大根堆之后为 \{ **2**,2,1\}，最后弄下来变成了 \{1,2,**2**\}。

[961]: https://blog.csdn.net/zhaohongfei_358/article/details/111414370