快速排序

快速排序
把左边都是较小的数,右边都是较大的数,再递归排序左右两边的数
时间复杂度O(nlog(n))
空间复杂度O(n)

第一种方法:指针移动过程中,第一个数参与交换

第一步:从右边开始移动后指针和第一个数比较大小,如果比第一个数小那么做交换,后指针停止;
第二步:从左边开始移动前指针和第一个数比较大小(已经交换,所以现在已经不是第一个数了),如果比第一个数大那么做交换,前指针停止;
第三步:重复第一步,第二步,知道前后指针相遇,这时前后指针和第一个数的指针位置重合在一起,此时出现前面的数都比第一个数小,后面的数都比第一个数大(比它小的都交换到前面去了,比它大的都交换到后面去了);
第四步:在指针相遇的地方分开两部分,分别重复前面的动作(递归)

$arr = [6, 2, 3, 4, 5, 1, 7, 8, 0, 9];
print_r($arr);
function sorted(&$arr, $first_pointer, $last_pointer) {
    if ($first_pointer >= $last_pointer) return true;
    $base_pointer = $first_pointer;
    $i = $first_pointer;
    $j = $last_pointer;
    $last_stoped = false;
    $first_stoped = true;
    while ($j > $i) {
        if ($arr[$j] < $arr[$base_pointer]) {
            $tmp = $arr[$j];
            $arr[$j] = $arr[$base_pointer];
            $arr[$base_pointer] = $tmp;
            $base_pointer = $j;
            $last_stoped = true;
            $first_stoped = false;
        } else if ($first_stoped) {
            $j--;
        }
        if ($arr[$i] > $arr[$base_pointer]) {
            $tmp = $arr[$i];
            $arr[$i] = $arr[$base_pointer];
            $arr[$base_pointer] = $tmp;
            $base_pointer = $i;
            $first_stoped = true;
            $last_stoped = false;
        } else if ($last_stoped) {
            $i++;
        }
    }
    if ($base_pointer > $first_pointer) {
        sorted($arr, $first_pointer, $base_pointer - 1);
    }
    if ($base_pointer < $last_pointer) {
        sorted($arr, $base_pointer + 1, $last_pointer);
    }
}
sorted($arr, 0, count($arr) - 1);
print_r($arr);

更简洁的写法

$arr = [6, 2, 3, 4, 5, 1, 7, 8, 0, 9];
print_r($arr);
function sorted(&$arr, $first_pointer, $last_pointer) {
    if ($first_pointer >= $last_pointer) return true;
    $base_pointer = $first_pointer;
    $i = $first_pointer;
    $j = $last_pointer;
    while ($j > $i) {
        while ($arr[$j] > $arr[$base_pointer] && $j > $i) {
            $j--;
        }
        $tmp = $arr[$j];
        $arr[$j] = $arr[$base_pointer];
        $arr[$base_pointer] = $tmp;
        $base_pointer = $j;
        while ($arr[$i] < $arr[$base_pointer] && $j > $i) {
            $i++;
        }
        $tmp = $arr[$i];
        $arr[$i] = $arr[$base_pointer];
        $arr[$base_pointer] = $tmp;
        $base_pointer = $i;
    }
    if ($base_pointer > $first_pointer) {
        sorted($arr, $first_pointer, $base_pointer - 1);
    }
    if ($base_pointer < $last_pointer) {
        sorted($arr, $base_pointer + 1, $last_pointer);
    }
}
sorted($arr, 0, count($arr) - 1);
print_r($arr);

第二种方法:指针移动过程中,第一个数不参与交换

第一步:右指针从最后一个数开始,和第一个数比较,比它小,停下来;
第二步:左指针从第二个数开始,和第一个数比较,比它大,停下来,和右指针的数做交换;
第三步:左右指针继续先后移动,相当于重复前两步操作,最后发现,左指针直到和右指针重合也找不到比第一个数大的了,这时的指针指向的数是右指针找到的小于第一个数的元素,把它和第一个数交换,不再继续移动指针;
第四步:在指针相遇的地方分开两部分,分别重复前面的动作(递归)

$arr = [6, 2, 3, 4, 5, 1, 7, 8, 0, 9];
print_r($arr);
function sorted(&$arr, $first_pointer, $last_pointer) {
    if ($first_pointer >= $last_pointer) return true;
    $first_node = $arr[$first_pointer];
    $i = $first_pointer + 1;
    $j = $last_pointer;
    $last_stoped = false;
    $first_stoped = true;
    while ($j > $i) {
        if ($arr[$j] < $first_node) {
            $last_stoped = true;
            $first_stoped = false;
        } else if (!$last_stoped) {
            $j--;
        }
        if ($arr[$i] > $first_node) {
            $first_stoped = true;
        } else if (!$first_stoped) {
            $i++;
        }
        if ($last_stoped && $first_stoped) {
            $tmp = $arr[$i];
            $arr[$i] = $arr[$j];
            $arr[$j] = $tmp;
            $last_stoped = false;
        }
    }
    $base_pointer = $first_pointer;
    if ($arr[$j] < $first_node) {
        $arr[$first_pointer] = $arr[$j];
        $arr[$j] = $first_node;
        $base_pointer = $j;
    }
    if ($base_pointer > $first_pointer) {
        sorted($arr, $first_pointer, $base_pointer - 1);
    }
    if ($base_pointer < $last_pointer) {
        sorted($arr, $base_pointer + 1, $last_pointer);
    }
}
sorted($arr, 0, count($arr) - 1);
print_r($arr);

更简洁的写法

$arr = [6, 2, 3, 4, 5, 1, 7, 8, 0, 9];
print_r($arr);
function sorted(&$arr, $first_pointer, $last_pointer) {
    if ($first_pointer >= $last_pointer) return true;
    $base_pointer = $first_pointer;
    $i = $first_pointer + 1;
    $j = $last_pointer;
    while ($j > $i) {
        while ($arr[$j] > $arr[$base_pointer] && $j > $i) {
            $j--;
        }
        while ($arr[$i] < $arr[$base_pointer] && $j > $i) {
            $i++;
        }
        $tmp = $arr[$i];
        $arr[$i] = $arr[$j];
        $arr[$j] = $tmp;
    }
    if ($arr[$j] < $arr[$first_pointer]) {
        $tmp = $arr[$first_pointer];
        $arr[$first_pointer] = $arr[$j];
        $arr[$j] = $arr[$first_pointer];
        $base_pointer = $j;
    }
    if ($base_pointer > $first_pointer) {
        sorted($arr, $first_pointer, $base_pointer - 1);
    }
    if ($base_pointer < $last_pointer) {
        sorted($arr, $base_pointer + 1, $last_pointer);
    }
}
sorted($arr, 0, count($arr) - 1);
print_r($arr);

从上面可以看出:
1、第二种方法交换次数更少,所以性能也更优;
2、快速排序是不稳定排序,因为相同的值顺序在排序前后是不一致的;
3、快速排序的时间复杂度是O(N*logN),空间复杂度是O(N);

发表评论