【数据结构】排序：交换排序（冒泡排序、快速排序）详解与实现（C++）

古城微笑少年丶 2021-12-10 00:07 254阅读 0赞

\#笔记整理

***内部排序分类目录：***  
*- [插入排序][Link 1]  
**-[\->交换排序][-]**  
\- [选择排序][Link 2]  
\- [归并排序][Link 3]  
\- 计数排序*

# 交换排序 #

交换排序就是基于“交换”规则进行排序的方法，其中包括：**冒泡排序(Bubble Sort)、快速排序(Quick Sort)。**

### 冒泡排序(Bubble Sort) ###

冒泡排序又称**起泡排序**，其过程很简单，两两比较相邻的记录，如果反序则交换，直到没有反序的记录为止。

**算法实现：**

// 冒泡排序法，对容器或数组nums进行排序
        void bubbleSort(vector<int> &nums){
        
            int len = nums.size();
            bool isChange    = true; // 是否有记录交换的标志位，防止后面的记录已经是有序的还执行循环
            for(int i = 0; i < len - 1 && isChange; i++){
        
                isChange = false;
                for(int j = i + 1; j < len; j++){
           // 遍历 nums[i]之后的记录
                    if(nums[j] < nums[i]){
                  // 存在小于 numsp[i] 的记录时，交换两记录
                        swap(nums[i], nums[j]);
                        isChange = true;
                    }
                }
            }
        }

[github源码][github]

![在这里插入图片描述][20190714222624107.png]  
**冒泡排序的时间复杂度： O ( n 2 ) O(n^2) O(n2)。**  
**冒泡排序是一种稳定的排序方法。**

### 快速排序（Quick Sort） ###

快速排序是对冒泡排序的一种改进，最早由图灵奖获得者Tony Hoare提出，被列为20世纪十大算法之一。它的实现过程中，增大了记录的比较和移动的距离，将较大的记录从前面直接移动到后面，将较小的记录从后面直接移动到前面，从而减少了总的比较次数和移动交换次数。  
**基本思想：** 通过一趟排序将待排记录分割成独立的两部分，其中一部分的关键字均比另一部分的关键字小，再对这两部分继续排序，以达到整个序列有序的目的。

**算法思路：**  
任选数组中的一个记录作为枢轴（pivot），将枢轴记录放在临时单元中，设置 low 和 high 分别指向数组中的首记录和尾记录。随后将凡是比枢轴记录小的放在 low 的左边， low++（右移）；比枢轴大的放在 high 的右边，high–（左移）。最后，在 low 与 high 重合之处，将枢轴放入。  
贴上《大话数据结构》中的讲解，很容易懂：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 2]  
**算法实现：**

// --- 快速排序法的划分函数，对数组或集合 nums 进行划分，并返回枢轴所在位置。已优化不必要的交换（枢轴的交换）
        int partition(vector<int> &nums, int low, int high){
        
            int len = nums.size();
            int pivot;             // 存储枢轴的值
            pivot = nums[low];     // 确定枢轴的值，需优化（使用三数取中或其他方法）
    
            while(low < high){
        
                while(low < high && nums[high] >= pivot){
        
                    high--;
                }
                nums[low] = nums[high];   // 将右端小于枢轴的记录放入左端
    
                while(low < high && nums[low] <= pivot){
        
                    low++;
                }
                nums[high] = nums[low];   // 将左端大于枢轴的记录放入右端
            }
            nums[low] = pivot;            // 放入枢轴的值
            return low;                   // 返回枢轴所在位置
        }
    
        // -- 快速排序法，对数组或容器 nums 中 [low, high] 之间的记录进行快速排序
        void qSort(vector<int> &nums, int low, int high){
        
            int pivotkey;   // 枢轴的位置
            if(low < high){
        
                pivotkey = partition(nums, low, high);
                qSort(nums, low, pivotkey - 1);
                qSort(nums, pivotkey + 1, high);
            }
    
        }
    
         // - 快速排序法的容器函数，对容器或数组nums进行排序
        void quickSort(vector<int> &nums){
        
            int len = nums.size();
            qSort(nums, 0, len);
        }

[github源码][github]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 3]  
**优化思路：**

*  优化选取枢轴：3数取中、9数取中；
 *  当数组长度小于10（可以自己设置）时使用插入排序；
 *  优化递归操作

**快速排序是一种不稳定的排序方法。**

部分内容来源：

1.  《数据结构（C语言版）》----严蔚敏
2.  《数据结构》课堂教学ppt ---- 刘立芳
3.  《数据结构算法与解析（STL版）》 ---- 高一凡
4.  《大话数据结构》 ---- 程杰
5.  《挑战程序设计竞赛2：算法和数据结构》 ---- 渡部有隆

[Link 1]: https://steve.blog.csdn.net/article/details/95931848
[-]: https://steve.blog.csdn.net/article/details/95934166
[Link 2]: https://steve.blog.csdn.net/article/details/95935599
[Link 3]: https://steve.blog.csdn.net/article/details/96337444
[github]: https://github.com/yohstone/data-structure/blob/master/sort.cpp
[20190714222624107.png]: /images/20211209/8ca4ca42fae64f39a5ead9f0a4754172.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70]: /images/20211209/98ebe990bc664da78efb33f0cebe7546.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 1]: /images/20211209/27caa06a4f634f0e84e5c8c2307a31e6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 2]: /images/20211209/ee92b0f414f3433a95e4194a9f6f93f8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 3]: /images/20211209/6e3d9f8e7cfb47608cb2f9da793b7164.png