网站做留言板怎么清空源码,休闲度假村网站建设方案,国家住房建设部网站,临沂网站建设技术托管归并排序思维导图#xff1a; 知识点#xff1a;如果原序列中两个数的值是相同的#xff0c;它们在排完序后#xff0c;它们的位置不发生变化#xff0c;那么这个排序是稳定的。快速排序是不稳定的#xff0c;归并排序是稳定的。
快排变成稳定的使快排排序数组中的每…归并排序思维导图 知识点如果原序列中两个数的值是相同的它们在排完序后它们的位置不发生变化那么这个排序是稳定的。快速排序是不稳定的归并排序是稳定的。
快排变成稳定的使快排排序数组中的每个数都不同将ai变成ai, i这个二元组将ai的下标也放进来使用双关键字排序。
快速排序平均时间复杂度是最坏是但是基本上不会达到的。归并排序时间复杂度。
#include iostreamusing namespace std;const int N 1e5 10;int n;
int q[N], tmp[N];void merge_sort(int q[], int l, int r)
{if (l r) return;int mid l r 1;merge_sort(q, l, mid), merge_sort(q, mid 1, r);int k 0, i l, j mid 1;while (i mid j r)if (q[i] q[j]) tmp[k] q[i];else tmp[k] q[j];while (i mid) tmp[k] q[i];while (j r) tmp[k] q[j];for (i l, j 0; i r; i, j) q[i] tmp[j];
}int main()
{scanf(%d, n);for (int i 0; i n; i) scanf(%d, q[i]);merge_sort(q, 0, n - 1);for (int i 0; i n; i) printf(%d , q[i]);return 0;
}
