JS快速排序算法

为什么选择快速排序？
实现思路
代码实现
总结

为什么选择快速排序？

相比传统的排序算法（for循环嵌套），时间复杂度由**O(n²) => O(logn)**。当数据量大的时候就会体现出快排与传统的排序速度的差异，下面我来实现快排的一种方法。

各大排序算法比较

类别	排序方法	时间复杂度			空间复杂度	稳定性
类别	排序方法	平均情况	最好情况	最坏情况	辅助存储	稳定性
插入排序	直接插入	O(n²)	O(n)	O(n²)	O(1)	稳定
插入排序	Shell排序	O(n^1.3)	O(n)	O(n²)	O(1)	不稳定
选择排序	直接选择	O(n²)	O(n²)	O(n²)	O(1)	不稳定
选择排序	堆排序	O(nlogn)	O(nlogn)	O(nlogn)	O(1)	不稳定
狡猾排序	冒泡排序	O(n²)	O(n)	O(n²)	O(1)	稳定
狡猾排序	快速排序	O(nlogn)	O(nlogn)	O(n²)	O(n)	不稳定
归并排序		O(nlogn)	O(nlogn)	O(nlogn)	O(n)	稳定
基数排序		O(d(r+n))	O(d(n+rd))	O(d(r+n))	O(rd+n)	稳定

实现思路

1. 确定基准数

基准数就是选一个数作为标准,方便其他的数和它比较的一个数。
我们将数组的第一个数作为基准数，将大于基准数的放在基准数的右边，小于基准数的放在放在基准数的左边。

2. 确定数组的边界

定义两个变量指向序列的最左边(left)和最右边(right),让left自加直到找到大于基准数的时候停下，同理让right自减直到找到小于基准数的时候停下，将两个所对应的值进行交换。然后继续进行上步操作直到left>=right。然后将left对应的值与基准数换位置。

3. 示例

假设一个数组 arr = [6,1,2,7,9,3,4,5,10,8],对这个数组进行排序。
初始状态

6	1	2	7	9	3	4	5	10	8
left									right

第一次
left和right在如下时候停下即（arr[left] > 6 && arr[right] < 6）

6	1	2	7	9	3	4	5	10	8
			left				right

left和right所对应的数值交换位置

6	1	2	5	9	3	4	7	10	8
			left				right

第二次
与第一次同理可得

6	1	2	5	4	3	9	7	10	8
				left		right

第三次
left和right相遇了

6	1	2	5	4	3	9	7	10	8
					right--left

与基准数交换,第一次排序就完成了

3	1	2	5	4	6	9	7	10	8

## 代码实现

javascript

function quick_sort(arr,left, right){
        var i = left
        var j = right
        var z = arr[left]
        if(left >= right){ // 如果数组只有一个元素
            return;
         }
        while (i < j) {
            while(arr[j] > z && i < j){
                j--
            }
            while(arr[i] <= z && i < j) {
                i++
            }
            if (i < j) {
                var n = arr[i]
                arr[i] = arr[j]
                arr[j] = n
            }
        }
        arr[left] = arr[i]
        arr[i] = z
        
        quick_sort(arr,left,i-1) // 将基准数的左边进行排序
        quick_sort(arr,i+1,right)// 将基准数的右边进行排序
    }