C++排序算法总结(冒泡、插入、选择、希尔、归并、快速、堆)

排序算法是面试中经常遇到以及面试官常考的算法基本功，掌握排序算法对于找工作而言很重要的一个标准。
[转载注明出处] (http://blog.csdn.net/yuebai008/article/details/70853756)

排序算法总结：

• 冒泡排序
• 插入排序
• 选择排序
• 希尔排序
• 归并排序
• 快速排序
• 堆排序

---

目录

冒泡排序

• 时间复杂度 O(n^2)
• 空间复杂度 O(1)
• 稳定排序

冒泡排序的原理就是将相邻两项进行比较，如果第一个比第二个大就进行交换，一轮交换之后最大的一项就交换到最后一项，重复对剩余项进行排序。

@yue008_author
//冒泡排序 时间复杂度O(n^2) 空间复杂度O(1)
void bubble_sort(vector<int> &nums) {for (unsigned i = 0; i < nums.size() - 1; ++i)for (unsigned j = 0; j < nums.size() - i - 1; j++)if (nums[j] > nums[j + 1])swap(nums[j], nums[j + 1]);
}
void swap(int &a, int &b) {int temp;temp = a;a = b;b = temp;   
}

插入排序

• 时间复杂度 O(n^2)
• 空间复杂度 O(1)
• 稳定排序

直接插入排序的原理就是从第一项开始作为有序部分，然后循环将当前项与前面所有有序项进行比较，插入到有序序列中，直到最后所有数据都是有序序列。

@yue008_author
//插入排序 时间复杂度O(n^2) 空间复杂度O(n)
void insert_sort(vector<int> &nums) {for (int i = 0; i < nums.size(); ++i)for (int j = i; j > 0; j--)if (nums[j] < nums[j - 1])swap(nums[j], nums[j - 1]);
}

选择排序

• 时间复杂度 O(n^2)
• 空间复杂度 O(1)
• 不稳定排序

选择排序的原理就是先进行第一轮循环比较相邻两项，找到最小值得下标，将最小值与第一项交换，然后重复排序剩余部分。

@yue008_author
//选择排序 时间复杂度O(n^2) 空间复杂度O(n)
void select_sort(vector<int> &nums) {for (int i = 0; i < nums.size(); i++) {int min = i;for (int j = i + 1; j < nums.size(); j++)if (nums[j] < nums[min])min = j;swap(nums[i], nums[min]);}
}

希尔排序

• 时间复杂度 O(nlogn）~O(n^2)
• 空间复杂度 O(1)
• 不稳定排序

希尔排序的原理就是按照一定步长分成子序列进行排序，然后逐步递减步长来完成最终排序。时间复杂度根据选择的步长相关。

@yue008_author
//希尔排序 时间复杂度O(nlogn)~O(n^2) 空间复杂度O(1)
void shell_sort(vector<int> &nums) {for(int gap=nums.size()>>1;gap>0;gap>>=1)for (int i = gap; i < nums.size(); i++){int temp = nums[i];int j = i - gap;for (; j >= 0 && nums[j] > temp; j -= gap)nums[j +gap] = nums[j];nums[j+gap] = temp;}
}

归并排序

• 时间复杂度 O(nlogn)
• 空间复杂度 O(n)
• 稳定排序

归并排序的原理就是将序列递归分成单位为1的小序列，然后两两合并排序，最终得到有序的序列。

@yue008_author
//归并排序 时间复杂度O(nlogn) 空间复杂度O(n)
void merge_array(vector<int> &nums, int b, int m, int e, vector<int> &temp) {int lb = b, rb = m, tb = b;while (lb != m&&rb != e)if (nums[lb] < nums[rb])temp[tb++] = nums[lb++];elsetemp[tb++] = nums[rb++];while (lb < m)temp[tb++] = nums[lb++];while (rb < e)temp[tb++] = nums[rb++];for (int i = b; i < e; i++)nums[i] = temp[i];
}
void merge_sort(vector<int> &nums, int b, int e, vector<int> temp) {int m = (b + e) / 2;if (m != b) {merge_sort(nums, b, m, temp);merge_sort(nums, m, e, temp);merge_array(nums, b, m, e, temp);}
}

快速排序

• 时间复杂度 O(nlogn)
• 空间复杂度 O(logn)/O(1)
• 不稳定排序

快速排序的原理就是先选择一个哨兵，然后将序列的值与哨兵值比较，小于哨兵的放在左边，大于哨兵的放在右边从而将序列分成两部分，再重复对这两部分进行排序直到所有序列有序。

@yue008_author
//快速排序1 时间复杂度O(nlogn) 空间复杂度O(logn)
void quick1_sort(vector<int> &nums, int b, int e, vector<int> &temp) {int m = (b + e) / 2;if (m != b) {int lb = b, rb = e-1;for (int i = b; i < e; i++) {if (i == m)continue;if (nums[i] < nums[m])temp[lb++] = nums[i];elsetemp[rb--] = nums[i];}temp[lb] = nums[m];for (int i = b; i < e; i++)nums[i] = temp[i];quick1_sort(nums, b, lb, temp);quick1_sort(nums, lb + 1, e, temp);}
}
//快速排序2，不借助辅助空间的方法，空间复杂度O(1)
void quick2_sort(vector<int> &nums, int b, int e) {if (b < e - 1) {int lb = b, rb = e - 1;while (lb < rb) {while (nums[rb] >= nums[b] && lb < rb)rb--;while (nums[lb] < nums[b] && lb < rb)lb++;swap(nums[lb], nums[rb]);}swap(nums[b], nums[lb]);quick2_sort(nums, b, lb);quick2_sort(nums, lb + 1, e);}
}

堆排序

• 时间复杂度 O(nlogn)
• 空间复杂度 O(1)
• 不稳定排序

堆排序的原理就是先构造一个最大堆（完全二叉树），父结点大于左右子结点，然后取出根结点（最大值）与最后一个结点交换，重复调整剩余的结点成最大堆，得到有序的序列。

@yue008_author
//堆排序 时间复杂度O(nlogn) 空间复杂度O(1)
void max_heapify(vector<int> &nums, int beg, int end)
{int curr = beg;int child = curr * 2 + 1;while (child < end) {if (child + 1 < end &&nums[child] < nums[child + 1])child++;if (nums[curr] < nums[child]) {swap(nums[curr], nums[child]);curr = child;child = 2 * curr + 1;}elsebreak;}
}
void heap_sort(vector<int> &nums)
{int n = nums.size();for (int i = n / 2 + 1; i >=0; i--){max_heapify(nums, i, nums.size() - 1);}for (int i = n - 1; i > 0; i--){swap(nums[0], nums[i]);max_heapify(nums, 0, i);}
}

参考

• 大话数据结构
• 维基百科
• 七种常见经典排序算法总结（C++实现）

---