排序算法的C++实现

排序算法的C++实现

排序算法比较

1、冒泡排序2、选择排序3、插入排序4、希尔排序5、归并排序6、快速排序代码实现7、堆排序 排序算法比较 排序方法时间复杂度(最好)时间复杂度(最坏)时间复杂度(平均)空间复杂度稳定性是否原地排序冒泡排序O(n)O(n2)O(n2)O(1)稳定是选择排序O(n)O(n2)O(n2)O(1)不稳定是插入排序O(n)O(n2)O(n1.3)O(1)稳定是希尔排序O(n)O(n2)O(n2)O(1)不稳定是归并排序O(nlogn)O(nlogn)O(nlogn)O(n)稳定不是快速排序O(nlogn)O(n2)O(nlogn)O(1)不稳定是

稳定性：如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变，则具备稳定性。

1、冒泡排序 2、选择排序

原理：在已给的序列中选择最大（最小）的数放到末尾，再从剩余元素中选择最大的，放到未排序的序列末尾，重复这个过程。直到全部排序完成。

选择排序每次都要找剩余未排序元素中的最小值，并和前面的元素交换位置，这样破坏了稳定性。比如 5，8，5，2，9 这样一组数据，使用选择排序算法来排序的话，第一次找到最小元素 2，与第一个 5 交换位置，那第一个 5 和中间的 5 顺序就变了，所以就不稳定了。正是因此，相对于冒泡排序和插入排序，选择排序就稍微逊色了。

3、插入排序

原理：对于未排序序列，默认首元素是有序的，从后往前扫描已排序数据，将未排序元素依次插入到已经有序序列的对应位置。

4、希尔排序

原理：希尔排序是将待排序的序列分成若干待排序的子序列，分别进行插入排序。关键在于间隔序列的设定。希尔排序是第一个突破O(n2)的排序算法。

5、归并排序

原理：如果要排序一个数组，先将数组从中间分成前后两部分，对前后两部分分别排序，再将排好序的两部分合并在一起。

归并排序时间复杂度分析：
对n个数组进行归并的时间复杂度是T(n)，分解成两个子数组进行排序的时间复杂的是T(n/2),合并有序数组的操作时间复杂度是O(n)。所以归并排序的时间复杂度就是：

T(n) = 2T(n/2) + n
= 2(2T(n/4) + n/2) + n = 4T(n/4) + 2n
= 4(2T(n/8) + n/4) + 2n = 8T(n/8) + 3n
…
= 2^k * T(n/2^k) + k * n
…
n/2^k 表示分解后的数据规模， k表示把数据规模分解到1时的分解次数，当算法完成，数据规模分解到1，此时n/2^k=1,k=log2n。将k带回原公式，可以计算得到T(n)=Cn+nlog2n，时间复杂度就是O(nlogn)。

6、快速排序

原理：在数列中挑选一个数，称为基准(pivot)，将比这个数小的元素放在左半边，其余元素放在右半边。递归地选择基准，并对两边的元素进行排序。

代码实现

#includeusing namespace std;#include#include//冒泡排序基础void bubbleSort1(vector &q){for (int i = q.size() - 1; i > 0; i--){ for (int j = 0; j < i; j++){if (q[j] > q[j + 1]){swap(q[j], q[j + 1]);}}}}//冒泡排序改进void bubbleSort2(vector& q){for (int i = q.size() - 1; i > 0; i--){bool flag = false;for (int j = 0; j < i; j++){if (q[j] > q[j + 1]){swap(q[j], q[j + 1]);flag = true;}}//若内层循环没有进行一次交换说明已经有序，直接breakif (!flag) break;}}//选择排序void selectSort(vector& q){for (int i = 0; i < q.size(); i++){//int max = q[i];for (int j = i + 1; j < q.size(); j++){if (q[i] > q[j]){swap(q[i], q[j]);}}}}//插入排序void insertSort(vector& q){for (int i = 1; i < q.size(); i++){int t = q[i], j;for (j = i - 1; j >= 0; j--){if (q[j] > t){q[j + 1] = q[j];}elsebreak;}q[j + 1] = t;}}//归并排序//l,r分别代表区间的左右void merges_sort(vector& q, int l, int r){if (l >= r) return; //只有一个元素int mid = (l + r) / 2;merges_sort(q, l, mid); //左边做归并merges_sort(q, mid + 1, r); //右边做归并//归并操作static vector w; //辅助数组w.clear();int i = l, j = mid + 1;//两个指针指向两个序列的起点while (i <= mid && j <= r){//判断当前两个指针指向的数哪个小if (q[i] < q[j]){w.push_back(q[i++]);}else{w.push_back(q[j++]);}}while (i <= mid) w.push_back(q[i++]);while (j <= r) w.push_back(q[j++]);for (int i = l, j = 0; j < w.size(); i++, j++){q[i] = w[j];}}//快速排序void quick_sort(vector& q, int l, int r){if (l >= r) return;int i = l - 1, j = r + 1, x = q[l + r >> 1];// x：基准，可以写成随机while (i < j){do j--; while (q[j] > x); //大于x在右边do i++; while (q[i] < x); //小于x在左边if (i < j) swap(q[i], q[j]);elsequick_sort(q, l, j), quick_sort(q, j + 1, r);}}int main(){int n;vectorq;cin >> n;for (int i = 0, t; i < n; i++){cin >> t;q.push_back(t);}//bubbleSort2(q);//selectSort(q);//insertSort(q);//merges_sort(q, 0, q.size() - 1);quick_sort(q, 0, q.size() - 1);for (auto x : q) cout << x <<' ';cout << endl;return 0;}

7、堆排序

堆是一棵完全二叉树，树中每个结点的值都不小于（或不大于）其左右孩子的值。 如果父亲结点是大于等于左右孩子就是大顶堆，小于等于左右孩子就是小顶堆。