一个简单的js快速排序算法

深碍√TFBOYSˉ_ 2022-06-10 03:30 135阅读 0赞

## 简介： ##

快速排序是对冒泡排序的一种改进。它的基本思想是：  
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

## 整个排序过程只需要三步： ##

（1）在数据集之中，选择一个元素作为"基准"（pivot）。  
（2）所有小于"基准"的元素，都移到"基准"的左边；所有大于"基准"的元素，都移到"基准"的右边。  
（3）对"基准"左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。

## 快速排序的时间复杂度: ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2E0MTk0MTk_size_16_color_FFFFFF_t_70]

## 实现： ##

首先，定义一个quickSort函数，它的参数是一个数组。

var quickSort = function(arr) {
    };

然后，检查数组的元素个数，如果小于等于1，就返回。

var quickSort = function(arr) {
    　　if (arr.length <= 1) { return arr; }
    };

接着，选择"基准"（pivot），并将其与原数组分离，再定义两个空数组，用来存放一左一右的两个子集。

var quickSort = function(arr) {
    　　if (arr.length <= 1) { return arr; }
    　　var pivotIndex = Math.floor(arr.length / 2) ;
    　　var pivot = arr.splice(pivotIndex, 1)[0]; //数组已经失去了这个基准值，长度减1
    　　var left = [];
    　　var right = [];
    };

然后，开始遍历数组，小于"基准"的元素放入左边的子集，大于基准的元素放入右边的子集。

最后，使用递归不断重复这个过程，就可以得到排序后的数组。

使用：

var test = [21,2,11,4,5];
    console.log('快速排序'+quickSort(test));

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2E0MTk0MTk_size_16_color_FFFFFF_t_70]: /images/20220610/3ddbdc72b8b34ddbb29e864bd0a926a1.png