快速排序#

什么是快速排序？#

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

排序流程#

(1)首先设定一个分界值pivot，通过该分界值将数组分成左右两部分。
(2)大于pivot的放到右边,小于pivot的放到左边
(3)对于左侧和右侧的数据又可以用递归的方式进行排序

非原地快速排序#

非原地排序即不需要在原数组上修改顺序所以我们可以自己定义一个结果数组以arr[0]作为分界值

代码如下

1
function quick_sort(arr){
2
    if(arr.length < 2){
3
        return arr
4
    }else{
5
        let pivot = arr[0]
6
        let left = [], right = []
7
        for(let i=1;i<arr.length;i++){
8
            if(arr[i] <= pivot){
9
                left.push(arr[i])
10
            }else{
11
                right.push(arr[i])
12
            }
13
        }
14
        return [...quick_sort(left),pivot,...quick_sort(right)]
15
    }
16
}

原地快速排序#

不能创建新数组必须就地排序

1
function quick_sort_in_place(arr){
2
    var quick_sort = (arr,start,end)=>{
3
        if(end - start <=1) return
4
        let pivotIndex = handlePivot(arr,start,end)
5
        quick_sort(arr,start,pivotIndex)
6
        quick_sort(arr,pivotIndex+1,end)
7
    }
8
    quick_sort(arr,0,arr.length)
9
}
10

11
// 原地将小的放左边 大的放右边  找到基准值的下标
12
function handlePivot(arr,start,end){
13
    if(end - start <= 1) return end - start - 1
14
    let k = start + 1
15
    while(end - k > 0){
16
        if(arr[k] > arr[start]){
17
            swap(arr,k,end-1)   // 当最后一次arr[k] > arr[start]时 会自己跟自己交换
18
            end --
19
        }else{
20
            k++
21
        }
22
    }
23
    swap(arr,start,k-1)
24
    return k - 1
25
}

随机化快排#

每一次都以第一个数作为分界值如果数据不太巧的话会让交换的次数更多所以可以随机选择排序数列的任意一个作为分界值找到后与第一个数交换位置

1
function handlePivot(arr,start,end){
2
    if(end - start <= 1) return end - start - 1
3

4
    // 在[start,end)之间随机生成一个位置  然后与第一个数交换位置
5
    let random = Math.floor(Math.random()*(end - start)+start)
6
    swap(arr[random],arr[0])
7

8
    let k = start + 1
9
    while(end - k > 0){
10
        if(arr[k] > arr[start]){
11
            swap(arr,k,end-1)   // 当最后一次arr[k] > arr[start]时 会自己跟自己交换
12
            end --
13
        }else{
14
            k++
15
        }
16
    }
17
    swap(arr,start,k-1)
18
    return k - 1
19
}