JavaScript 快速排序法

2021/6/10 22:21:06

本文主要是介绍JavaScript 快速排序法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

核心思想:

1.先从数组中取出一个数作为基准数

2.定义两个空数组

3.将数组其余的每一项与基准数作比较

4.将小于等于(或大于等于)基准数的项放入准备好的一个空数组中

5.将其余的项放入另一个空数组中

6.然后通过函数递归,实现快速排序

函数封装如下:

(1)从小到大排序

        function quickSort(array) {
            if (!Array.isArray(array)) {
                return;
            }
            if (array.length <= 1) {
                return array;
            }
            var center = parseInt(array.length / 2);
            var centerNum = array.splice(center, 1);
            var left = [];
            var right = [];
            for (var i = 0; i < array.length; i++) {
                if (array[i] <= centerNum) {
                    left.push(array[i]);
                }
                else {
                    right.push(array[i]);
                }
            }
            return quickSort(left).concat(centerNum).concat(quickSort(right));
        }

(2)从大到小排序

        function quickSort(array) {
            if (!Array.isArray(array)) {
                return;
            }
            if (array.length <= 1) {
                return array;
            }
            var center = parseInt(array.length / 2);
            var centerNum = array.splice(center, 1);
            var left = [];
            var right = [];
            for (var i = 0; i < array.length; i++) {
                if (array[i] >= centerNum) {
                    left.push(array[i]);
                }
                else {
                    right.push(array[i]);
                }
            }
            return quickSort(left).concat(centerNum).concat(quickSort(right));
        }

示例:

(1)将一个数组从大到小排序

        var arr = [1, 5, 3, 6, 4, 2, 7, 4, 7, 8, 3, 6, 3, 6];
        function quickSort(array) {
            if (!Array.isArray(array)) {
                return;
            }
            if (array.length <= 1) {
                return array;
            }
            var center = parseInt(array.length / 2);
            var centerNum = array.splice(center, 1);
            var left = [];
            var right = [];
            for (var i = 0; i < array.length; i++) {
                if (array[i] >= centerNum) {
                    left.push(array[i]);
                }
                else {
                    right.push(array[i]);
                }
            }
            return quickSort(left).concat(centerNum).concat(quickSort(right));
        }
        console.log(quickSort(arr));

控制台输出:

(2)将一个数组从小到大排序

        var arr = [1, 5, 3, 6, 4, 2, 7, 4, 7, 8, 3, 6, 3, 6];
        function quickSort(array) {
            if (!Array.isArray(array)) {
                return;
            }
            if (array.length <= 1) {
                return array;
            }
            var center = parseInt(array.length / 2);
            var centerNum = array.splice(center, 1);
            var left = [];
            var right = [];
            for (var i = 0; i < array.length; i++) {
                if (array[i] <= centerNum) {
                    left.push(array[i]);
                }
                else {
                    right.push(array[i]);
                }
            }
            return quickSort(left).concat(centerNum).concat(quickSort(right));
        }
        console.log(quickSort(arr));

控制台输出:



这篇关于JavaScript 快速排序法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程