【1.数据结构-8.2 排序】冒泡排序-快速排序

一、冒泡排序

1.1 原理

• 基于“交换”的排序:根据序列中两个元素关键字的比较结果来对换这两个记录在序列中的位置
• 冒泡排序：从后往前(或从前往后)两两比较相邻元素的值，若为逆序(即A[i-1]>A[i))，则交换它们，直到序列比较完。称这样过程为“一趟”冒泡排序

1.2 排序过程

• 初始状态

• 第一趟
  
  
• 第二趟
  
  
  …
  …
  …
• 第五趟
  

1.3 算法实现

1.4 性能分析

1.5 冒泡用于链表

1.6 总结

二、快速排序

2.1. 算法原理

• 算法思想:在待排序表L[1…n]中任取一个元素pivot作为枢轴(或基准，通常取首元素)，通过一趟排序将待排序表划分为独立的两部分L[1…k-1]和L[k+1…n]，使得L[1…k-1]中的所有元素小于pivot,L[k+1…n]中的所有元素大于等于pivot，则pivot放在了其最终位置L(k)上，这个过程称为一次“划分”。然后分别递归地对两个子表重复上述过程，直至每部分内只有一个元素或空为止，即所有元素放在了其最终位置上。

2.2. 排序过程

• 第一趟：选定最左边的第一个元素49作为枢轴pivot，比49小的元素放到左边，比49大的元素放到右边

high指针向左移动，找到27比49小，则将27移动到枢轴pivot左边

low指针向右移动，找到65比49大，则将65移动到枢轴pivot右边

…
…
…

• 第一趟结束：用第一个元素把待排序序列“划分”为两个部分。左边更小，右边更大。该元素的最终位置已确定

• 第二趟排序：
  （1）以49为中心，对左右两边的序列重新进行递归快速排序；
  （2）左边选取27作为枢轴pivot，进行快速排序；
  （3）右边选取76作为枢轴pivot，进行快速排序。
  
  
  …
  …
  …
• 最终排序结果：

2.3. 算法效率分析

• 每一层的QuickSort只需要处理剩余的待排序元素，时间复杂度不超过O(n)
• 时间复杂度=O(n*递归层数)

• 空间复杂度=O(递归层数)

• 把n个元素组织成二叉树，二叉树的层数就是递归调用的层数

• 最坏的情况：每一次选中的“枢轴”将待排序序列划分为很不均匀的两个部分，则会导致递归深度增加，算法效率变低

• 比较好的情况：每一次选中的“枢轴”将待排序序列划分为均匀的两个部分，则递归深度最小，算法效率最高

2.4. 总结