（二十三）数据结构-交换排序

交换排序：根据序列两个元素关键字的比较结果来对换这两个记录在序列中的位置
交换排序：冒泡排序、快速排序

一、冒泡排序（稳定的）

（第一趟排序能使关键字最小的一个元素“冒”到最前面）

算法思想：从后往前（从前往后）两两比较相邻元素的值，若为逆序，即交换他们，知道序列比较完

1.1时间复杂度

移动次数与交换次数不同

1.2重要知识点

二、快速排序（应用最广泛）

算法思想：在待排序表中任取一个元素作为枢轴pivot（或者基准，通常取首元素），通过一趟排序表划分为独立的两个部分，使得左半部分所有元素小于pivot，右半部分大于pivot。分别递归对两个子表重复上述过程，直到每个部分只有一个元素或空为止，即所有元素放在了最终位置上