MoreWindows白话经典算法之七大排序(高清版)

这是本人在研一上课时所整理的文档，包括冒泡排序，直接插入排序，直接选择排序，希尔排序，归并排序，快速排序和堆排序这七种常用的排序方法，这些文章不仅使我在考试中取了不错的成绩，也为后来顺利面过迅雷，腾讯，微软打下了良好的基础，现在整理成电子书形式，希望能对大家有所帮助。 ### 白话经典算法之七大排序 #### 一、冒泡排序 冒泡排序是一种简单直观的排序算法，它的基本思想是从第一个元素开始，比较相邻元素的大小，如果前一个元素大于后一个元素则交换它们的位置，这样一轮比较下来，最大的元素会像气泡一样“浮”到最后的位置。接下来对剩余的元素重复此过程，直到所有元素排序完毕。 **冒泡排序的三种实现：** 1. **基本实现：** ```cpp void BubbleSort1(int a[], int n) { for (int i = 0; i < n; i++) { for (int j = 1; j < n - i; j++) { if (a[j - 1] > a[j]) { Swap(a[j - 1], a[j]); } } } } ``` 这是最基础的冒泡排序实现，它的时间复杂度为O(n^2)，其中n为数组的长度。 2. **带标志位的优化：** ```cpp void BubbleSort2(int a[], int n) { bool flag = true; while (flag) { flag = false; for (int j = 1; j < n; j++) { if (a[j - 1] > a[j]) { Swap(a[j - 1], a[j]); flag = true; } } n--; } } ``` 这里添加了一个布尔类型的变量`flag`来标记是否进行了交换。如果没有进行任何交换，说明数组已经是有序的，此时可以直接结束循环，提高了算法的效率。 3. **记录最后一次交换的位置：** ```cpp void BubbleSort3(int a[], int n) { int flag = n; while (flag > 0) { int k = flag; flag = 0; for (int j = 1; j < k; j++) { if (a[j - 1] > a[j]) { Swap(a[j - 1], a[j]); flag = j; } } } } ``` 这种实现方式记录了最后一次发生交换的位置，并利用这个位置作为下一轮排序的边界，从而避免不必要的比较，进一步提高了排序的效率。 #### 二、直接插入排序 直接插入排序是另一种简单的排序算法，它的基本思想是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。 **直接插入排序的三种实现：** 1. **基本实现：** ```cpp void InsertSort1(int a[], int n) { for (int i = 1; i < n; i++) { for (int j = i - 1; j >= 0; j--) { if (a[j] < a[i]) break; if (j != i - 1) { int temp = a[i]; for (int k = i - 1; k > j; k--) { a[k + 1] = a[k]; } a[j + 1] = temp; } } } } ``` 此实现遵循直接插入排序的基本逻辑，但代码较长且不够清晰。 2. **简化实现：** ```cpp void InsertSort2(int a[], int n) { for (int i = 1; i < n; i++) { int temp = a[i]; int j = i - 1; while (j >= 0 && a[j] > temp) { a[j + 1] = a[j]; j--; } a[j + 1] = temp; } } ``` 通过合并搜索和数据后移的步骤，使得代码更加简洁易懂。 #### 三、其他排序算法简介 除了冒泡排序和直接插入排序之外，文档还提到了直接选择排序、希尔排序、归并排序、快速排序和堆排序等排序算法。 - **直接选择排序**：每次从未排序的部分选择最小（或最大）的元素，存放到已排序序列的末尾。 - **希尔排序**：是基于插入排序的改进版本，通过引入“增量序列”技术，克服了插入排序中移动元素的问题。 - **归并排序**：采用分治策略，将数组分为两部分，分别排序后再合并。 - **快速排序**：同样采用分治策略，通过一趟排序将待排记录分割成独立的两部分，其中一部分的所有记录都比另一部分的所有记录小，然后再对这两部分继续排序。 - **堆排序**：是一种树形选择排序，通过建立堆结构，不断取出最大（或最小）值来实现排序。 以上介绍了几种常见的排序算法及其具体实现，每种算法都有其特点和适用场景。通过学习这些算法，不仅可以提高数据处理能力，还可以为后续更高级的算法学习打下坚实的基础。