1.简介
交换类排序：顾名思意，即在排序过程中，依次交换两个元素之间的值
2.冒泡排序
2.1 思想
将两两进行比较，将大的关键字"沉底"，即将数值大的元素放到后面
例如：待排序序列为{4, 2, 6, 9, 5, 1, 10, 3, 8, 7}
第一趟：2, 4, 6, 5, 1, 9, 3, 8, 7, 10
第二趟：2, 4, 5, 1, 6, 3, 8, 7, 9, 10
第三趟：2, 4, 1, 5, 3, 6, 7, 8, 9, 10
第四趟：2, 1, 4, 3, 5, 6, 7, 8, 9, 10
第五趟：1, 2, 3, 4, 5, 6, 7, 8, 9, 10
第六趟：hasChange = false， 结束
2.2 实现
void bubble_insert_sort(vector<int>& nums)
{
bool hasChange = false;
int size = nums.size();
for (int i = 1; i < size; ++i) {
hasChange = false;
for (int j = 0; j < (size - i); ++j) {
if (nums[j] > nums[j + 1]) { //将大的关键字"沉底"
int t = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = t;
hasChange = true;
}
}
if (hasChange == false) break; //已经没有可交换的元素，即序列已经是有序的
}
}
2.3 时间和空间复杂度分析
当待排序序列是有序序列时，只需进行n次比较，时间复杂度为O(n)；当待排序序列为逆有序序列时，要进行(n*n-1)/2次比较，即时间复杂度为O(n^2)；故平均时间复杂度为O(n^2).
排序过程，除了需要一个临时变量之外，无需其他的空间，故空间复杂度为O(1).
3. 快速排序
3.1 思想
每次选择一个目标桩，将小于或等于目标桩的放到目标桩的左边，大于目标桩的放到目标桩的右边，根据目标桩分为左边序列或右边序列，在将左边序列和右边序列分别重复上面过程.
例如：待排序序列为{4, 2, 6, 9, 5, 1, 10, 3, 8, 7}
第一趟：目标桩为4
3, 2, 6, 9, 5, 1, 10, 4, 8, 7
3, 2, 4, 9, 5, 1, 10, 6, 8, 7
3, 2, 1, 9, 5, 4, 10, 6, 8, 7
3, 2, 1, 4, 5, 9, 10, 6, 8, 7
得到左序列为：3, 2, 1 得到右序列为：5, 9, 10, 6, 8, 7
分别对左序列和右序列重复上述过程
3.2 实现
void merge(vector<int>& nums, int left, int right)
{
int pos = left; //交换的目标位置
while (left < right) {
while (nums[right] > nums[pos] && left < right) right--; //从右往左扫描
if (left < right) {
swap(nums[right], nums[pos]); //放到temp的前面
pos = right; //记录目标桩位置
}
while (nums[left] <= nums[pos] && left <= right) left++; //从左往右扫描
if (left < right) {
swap(nums[left], nums[pos]); //放到temp的后面
pos = left++;
}
}
}
void quick_insert_sort(vector<int>& nums, int left, int right)
{
if (left < right) {
merge(nums, left, right);
int mid = (left + right) / 2;
quick_insert_sort(nums, left, mid - 1); //目标桩的左边序列
quick_insert_sort(nums, mid + 1, right); //目标桩的右边序列
}
}
3.3 时间和空间复杂度分析
当待排序序列是有序序列时，时间复杂度为O(n^2)；当为逆序序列时，需要时间复杂度为O(n*log2(n))；故平均时间复杂度为O(n*log2(n)).
排序过程当中利用递归实现，故空间复杂度为O(log2(n)).
[1]数据结构清华大学版
[2]数据结构高分笔记
