j**l
发帖数: 2911 | 1 这道题就是那道被讨论得热火朝天的MS老题，如何把负数扫到左边，正数扫到右边。对
所有的正数和所有的负数，都不能改变原有的相对次序
/*
{1, 5, -5, -8, 2, -1, 15}
要把负的扫到左边，正的扫到右边。
不能改变顺序
得到{-5 -8 -1 1 5 2 15}
*/
void swap_numbers(int input[], int n)
{
int temp;
for (int i = 0; i < n; )
{
if (input[i] > 0 && i < n - 1 && input[i + 1] < 0)
{
temp = input[i];
input[i] = input[i+1];
input[i+1] = temp;
if (i > 0 && input[i-1] > 0)
i--;
else
i++;
| g*******y
发帖数: 1930 | | j**l
发帖数: 2911 | 3 如何给出证明?
【在 g*******y 的大作中提到】
: 平方级的
| j**l
发帖数: 2911 | 4 这个程序算简洁么? 面试官事后会因为O(n^2)而提交negative的feedback么？
【在 g*******y 的大作中提到】
: 平方级的
| o**********t
发帖数: 406 | 5 直接看程序，有时很难一眼看出复杂度。
关键是在纸上的分析，如果一个算法在纸上分析不出 O(N)，程序在怎么写，能写出 O
(N) 来？
【在 j**l 的大作中提到】
: 这道题就是那道被讨论得热火朝天的MS老题，如何把负数扫到左边，正数扫到右边。对
: 所有的正数和所有的负数，都不能改变原有的相对次序
: /*
: {1, 5, -5, -8, 2, -1, 15}
: 要把负的扫到左边，正的扫到右边。
: 不能改变顺序
: 得到{-5 -8 -1 1 5 2 15}
: */
: void swap_numbers(int input[], int n)
: {
| j**l
发帖数: 2911 | 6 有谁能总结一下，这道题目前公认最好最优的算法是什么？空间复杂度必须是O(1)
O
【在 o**********t 的大作中提到】
: 直接看程序，有时很难一眼看出复杂度。
: 关键是在纸上的分析，如果一个算法在纸上分析不出 O(N)，程序在怎么写，能写出 O
: (N) 来？
| s*********g
发帖数: 153 | 7 这个循环，长度虽然是n，但是时间复杂度不是 O（n），因为不停的有 i--，所以swap
的次数不是O（n），虽然没写出来，但我感觉，里面就像有嵌套了一个循环的效果，唉
，我也不太会证明....
【在 j**l 的大作中提到】
: 这道题就是那道被讨论得热火朝天的MS老题，如何把负数扫到左边，正数扫到右边。对
: 所有的正数和所有的负数，都不能改变原有的相对次序
: /*
: {1, 5, -5, -8, 2, -1, 15}
: 要把负的扫到左边，正的扫到右边。
: 不能改变顺序
: 得到{-5 -8 -1 1 5 2 15}
: */
: void swap_numbers(int input[], int n)
: {
| g*******y
发帖数: 1930 | 8 假设一共有n+1个数, 假设对于前n个数，已经做完了，得到 | y**i
发帖数: 1112 | 9 这个程序跟我在另一个帖子里给出的程序执行方法几乎一摸一样，思路就是把每个负数
冒泡法一样的交换到它前面的所有正数的前面，与其用冒泡法还不如用插入法呢，我修
改了一下就是：
void SplitPN(int A[], int p, int r)
{
int i = p-1, j, k, temp;
for (j = p; j <= r; ++j)
{
if (A[j] < 0)
{
++i;
temp = A[j];
for (k = j; k > i; --k)
{
A[k] = A[k-1];
}
A[i] = temp;
}
}
}
【在 j**l 的大作中提到】
: 这道题就是那道被讨论得热火朝天的MS老题，如何把负数扫到左边，正数扫到右边。对
: 所有的正数和所有的负数，都不能改变原有的相对次序
: /*
: {1, 5, -5, -8, 2, -1, 15}
: 要把负的扫到左边，正的扫到右边。
: 不能改变顺序
: 得到{-5 -8 -1 1 5 2 15}
: */
: void swap_numbers(int input[], int n)
: {
| y**i
发帖数: 1112 | 10 时间复杂度最坏情况是O(n^2/2)=O(n^2)
【在 y**i 的大作中提到】
: 这个程序跟我在另一个帖子里给出的程序执行方法几乎一摸一样，思路就是把每个负数
: 冒泡法一样的交换到它前面的所有正数的前面，与其用冒泡法还不如用插入法呢，我修
: 改了一下就是：
: void SplitPN(int A[], int p, int r)
: {
: int i = p-1, j, k, temp;
: for (j = p; j <= r; ++j)
: {
: if (A[j] < 0)
: {
| a*******h
发帖数: 123 | 11 你这个是 O(n^2) 比较显然吧，每次把一个负数往前顺至多需要 O(n) 步。
再考虑左边一半全是正数右边一半全是负数的输入，你的程序需要运行 n^2 步，所以复
杂度也是 \Omega(n^2)。
所以一共就是 \Theta(n^2)。
【在 j**l 的大作中提到】
: 这道题就是那道被讨论得热火朝天的MS老题，如何把负数扫到左边，正数扫到右边。对
: 所有的正数和所有的负数，都不能改变原有的相对次序
: /*
: {1, 5, -5, -8, 2, -1, 15}
: 要把负的扫到左边，正的扫到右边。
: 不能改变顺序
: 得到{-5 -8 -1 1 5 2 15}
: */
: void swap_numbers(int input[], int n)
: {
| l******g
发帖数: 59 | 12 quick_sort, partition
【在 j**l 的大作中提到】
: 这道题就是那道被讨论得热火朝天的MS老题，如何把负数扫到左边，正数扫到右边。对
: 所有的正数和所有的负数，都不能改变原有的相对次序
: /*
: {1, 5, -5, -8, 2, -1, 15}
: 要把负的扫到左边，正的扫到右边。
: 不能改变顺序
: 得到{-5 -8 -1 1 5 2 15}
: */
: void swap_numbers(int input[], int n)
: {
| y**i
发帖数: 1112 | 13 这个不能保证稳定性
【在 l******g 的大作中提到】
: quick_sort, partition
| r****o
发帖数: 1950 | 14 你说的稳定性是数据的相对order吗？
我想了一下，quick sort的每次partition后，似乎能保证所有比pivot小的元素们的位
置的相对顺序都不变，但大于等于pivot的元素们的位置的相对顺序有可能变化。
我说的对不对?
【在 y**i 的大作中提到】
: 这个不能保证稳定性
|
|
