排序算法--快速排序

快速排序

什么是快速排序 ？

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

排序流程

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

非原地快速排序

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

代码如下

function quick_sort(arr){
    if(arr.length < 2){
        return arr
    }else{
        let pivot = arr[0]    
        let left = [], right = []   
        for(let i=1;i<arr.length;i++){
            if(arr[i] <= pivot){
                left.push(arr[i])
            }else{
                right.push(arr[i])
            }
        }
        return [...quick_sort(left),pivot,...quick_sort(right)]
    }
}

原地快速排序

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

function quick_sort_in_place(arr){
    var quick_sort = (arr,start,end)=>{
        if(end - start <=1) return 
        let pivotIndex = handlePivot(arr,start,end)
        quick_sort(arr,start,pivotIndex)
        quick_sort(arr,pivotIndex+1,end)
    }
    quick_sort(arr,0,arr.length)
}

// 原地将小的放左边 大的放右边  找到基准值的下标
function handlePivot(arr,start,end){
    if(end - start <= 1) return end - start - 1
    let k = start + 1
    while(end - k > 0){    
        if(arr[k] > arr[start]){
            swap(arr,k,end-1)   // 当最后一次arr[k] > arr[start]时 会自己跟自己交换
            end --
        }else{
            k++
        }        
    }
    swap(arr,start,k-1)
    return k - 1
}

随机化快排

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

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

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

    let k = start + 1
    while(end - k > 0){    
        if(arr[k] > arr[start]){
            swap(arr,k,end-1)   // 当最后一次arr[k] > arr[start]时 会自己跟自己交换
            end --
        }else{
            k++
        }        
    }
    swap(arr,start,k-1)
    return k - 1
}