Just for fun——迅速写完快速排序

weakish 发布于2019-06-28 14:17 / 3148人阅读

摘要：快速排序快速排序的话，应用了分治的思想，选取一个中间值，把小于它的值放左边，大于它的值放右边，然后再对这两个分组应用同样的方法，递归下去。挖坑挖坑是自己快速回忆实现这个算法的形象叫法。

快速排序

快速排序的话，应用了分治的思想，选取一个中间值，把小于它的值放左边，大于它的值放右边，然后再对这两个分组应用同样的方法，递归下去。

挖坑

挖坑是自己快速回忆实现这个算法的形象叫法。
如果现在有数组

[-1, 2, 4, 7, 8, -7, 6, 20]

挖出第一个位置的值，存起来，现在有一个空的坑位了，需要填上

刚开始的时候，i指向初始的位置，j指向末尾的位置，现在i指向的地方有坑位，j开始往前走，遇到的数如果比中间值（这里是-1）小的话，把当前j指向位置的数挖掉，给i上的位置填补上，现在j的位置是空的

那现在i（+1之后）开始活动了，向前跑，如果碰到i指向位置的值比中间值（这里是-1）大，则把当前i指向位置的数挖掉，给j的位置补上，然后重复j运动的过程

以上过程最终i和j会相遇（跳出循环点），那里正好有个空的坑位给中间值

然后应用分治策略，对剩下的两个分组使用同样的手段 实现 Java实现

/**
  * 快速排序
  * @param arr int[] 排序数组
  * @param start int 开始位置
  * @param end int 结尾位置
  */
private static void quickSort(int[] arr, int start, int end) {
    if(end - start == 1) {
        if(arr[start] > arr[end]) {
            int temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;
        }
    } else if (end - start > 1) {
        int middle = arr[start];
        int i = start;
        int j = end;
        while (i != j && i <= end && j >= start) {
            while (arr[j] >= middle && j > i) {
                j--;
            }
            if(j > i) {
                arr[i] = arr[j];
                i++;
            }
            while (arr[i] <= middle && i < j) {
                i++;
            }
            if(i < j) {
                arr[j] = arr[i];
                j--;
            }
        }
        arr[i] = middle;
        quickSort(arr, start, i - 1);
        quickSort(arr, i + 1, end);
    }
}

Javascript的实现

let arr = [2, -1, -2, 100, 5];

function quickSort(arr, start, end) {
    if(end - start === 1) {
        if(arr[start] > arr[end]) {
            let temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;
        }
    } else if (end - start > 1) {
        let middle = arr[start];
        let i = start;
        let j = end;
        while (i !== j && i <= end && j >= start) {
            while (arr[j] >= middle && j > i) {
                j--;
            }
            if(j > i) {
                arr[i] = arr[j];
                i++;
            }
            while (arr[i] <= middle && i < j) {
                i++;
            }
            if(i < j) {
                arr[j] = arr[i];
                j--;
            }
        }
        arr[i] = middle;
        quickSort(arr, start, i - 1);
        quickSort(arr, i + 1, end);
    }
}

quickSort(arr, 0, arr.length - 1);
console.log(arr);

PHP的实现

 $arr[$end]) {
            $temp = $arr[$start];
            $arr[$start] = $arr[$end];
            $arr[$end] = $temp;
        }
    } elseif ($end - $start > 1) {
        $middle = $arr[$start];
        $i = $start;
        $j = $end;
        while ($i !== $j && $i <= $end && $j >= $start) {
            while ($arr[$j] >= $middle && $j > $i) {
                $j--;
            }
            if($j > $i) {
                $arr[$i] = $arr[$j];
                $i++;
            }
            while ($arr[$i] <= $middle && $i < $j) {
                $i++;
            }
            if($i < $j) {
                $arr[$j] = $arr[$i];
                $j--;
            }
        }
        $arr[$i] = $middle;
        quickSort($arr, $start, $i - 1);
        quickSort($arr, $i + 1, $end);
    }
}

quickSort($arr, 0, count($arr) - 1);
print_r($arr);

云服务器 GPU云服务器快速排序快速排序函数快速排序算法 php快速排序

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/26090.html

Just for fun——迅速写完快速排序

摘要：快速排序快速排序的话，应用了分治的思想，选取一个中间值，把小于它的值放左边，大于它的值放右边，然后再对这两个分组应用同样的方法，递归下去。挖坑挖坑是自己快速回忆实现这个算法的形象叫法。快速排序快速排序的话，应用了分治的思想，选取一个中间值，把小于它的值放左边，大于它的值放右边，然后再对这两个分组应用同样的方法，递归下去。挖坑挖坑是自己快速回忆实现这个算法的形象叫法。如果现在有数...

JowayYoung 2019-08-21 17:39 评论0 收藏0
Just for fun——迅速写完快速排序

摘要：快速排序快速排序的话，应用了分治的思想，选取一个中间值，把小于它的值放左边，大于它的值放右边，然后再对这两个分组应用同样的方法，递归下去。挖坑挖坑是自己快速回忆实现这个算法的形象叫法。快速排序快速排序的话，应用了分治的思想，选取一个中间值，把小于它的值放左边，大于它的值放右边，然后再对这两个分组应用同样的方法，递归下去。挖坑挖坑是自己快速回忆实现这个算法的形象叫法。如果现在有数...

alaege 2019-08-15 12:30 评论0 收藏0
Just for fun——基于Swoole做个小框架

摘要：使开发人员可以编写高性能的异步并发，服务。使用作为网络通信框架，可以使企业研发团队的效率大大提升，更加专注于开发创新产品。总之，这个库让可以常驻内存，并提供了，等功能。 swoole 使 PHP 开发人员可以编写高性能的异步并发 TCP、UDP、Unix Socket、HTTP，WebSocket 服务。Swoole 可以广泛应用于互联网、移动通信、企业软件、云计算、网络游戏、物联网（...

CoreDump 2019-07-25 14:09 评论0 收藏0
Just for fun——Slim借力Swoole

摘要：的话，是一个遵循规范微型的框架，作者这样说大致意思的核心工作分发了请求，然后调用回调函数，返回一个对象。执行的方法时，我们从中取出的依赖，这时候，注册的回调函数被调用，返回实例。 Slim Slim的话，是一个遵循PSR (PSR-7)规范微型的框架，作者这样说： Slim is a PHP micro framework that helps you quickly write si...

leejan97 2019-06-28 18:22 评论0 收藏0
Just for fun——基于Swoole做个小框架

摘要：使开发人员可以编写高性能的异步并发，服务。使用作为网络通信框架，可以使企业研发团队的效率大大提升，更加专注于开发创新产品。总之，这个库让可以常驻内存，并提供了，等功能。 swoole 使 PHP 开发人员可以编写高性能的异步并发 TCP、UDP、Unix Socket、HTTP，WebSocket 服务。Swoole 可以广泛应用于互联网、移动通信、企业软件、云计算、网络游戏、物联网（...

fevin 2019-06-28 18:19 评论0 收藏0