1年前 207 0 0

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

举个例子

如无序数组[6 2 4 1 5 9]

a),先把第一项[6]取出来,

用[6]依次与其余项进行比较,

如果比[6]小就放[6]前边,2 4 1 5都比[6]小,所以全部放到[6]前边

如果比[6]大就放[6]后边,9比[6]大,放到[6]后边,//6出列后大喝一声,比我小的站前边,比我大的站后边,行动吧!霸气十足~

一趟排完后变成下边这样:

排序前 6 2 4 1 5 9

排序后 2 4 1 5 6 9

b),对前半拉[2 4 1 5]继续进行快速排序

重复步骤a)后变成下边这样:

排序前 2 4 1 5

排序后 1 2 4 5

前半拉排序完成,总的排序也完成:

排序前:[6 2 4 1 5 9]

排序后:[1 2 4 5 6 9]

排序结束

以下代码实现仅供参考

function quickSort(a) {
    // If the array is 1 or less in size it is already sorted.
    if (a.length < = 1) {
        return a;
    }
    
    // Pick a pivot from the middle of the array.
    var pivotIndex = Math.floor(a.length/2);
    var pivot = a[pivotIndex];
    var less = [], greater = [];
    
    // Iterate over all items in the array and put them in less or greater.
    for (var i=0; i< a.length; i++) {
        if (i === pivotIndex) {
            // Skip the pivot.
            continue;
        }
        
        if (a[i] < = pivot) {
            less.push(a[i]);
        }
        else {
            greater.push(a[i]);
        }
    }
    
    // Recurse and sort the arrays less and greater using quickSort.
    var sortedLess = quickSort(less);
    var sortedGreater = quickSort(greater);
    
    // Return the sorted array by concatenating less, pivot and greater.
    return sortedLess.concat([pivot], sortedGreater);
}
function partition(a, left, right, pivotIndex) {
    // left is the index of the leftmost element of the subarray
    // right is the index of the rightmost element of the subarray (inclusive)
    //   number of elements in subarray = right-left+1
    var storeIndex = left;
    var pivotValue = a[pivotIndex];
    // Move pivot to end.
    swap(a, pivotIndex, right);

    // left ≤ i <  right
    for (var i=left; i< right; i++) {
        if (a[i] < = pivotValue) {
            swap(a, i, storeIndex);
            storeIndex++;
        }
    }
    
    // Move pivot to its final place.
    swap(a, storeIndex, right);
    return storeIndex;
}

function quicksort(a, left, right) {
    // If the array has 2 or more items.
    if (left <  right) {
        // Choose the middle value as a pivot.
        var pivotIndex = Math.floor((left+right)/2);
        
        // Get lists of bigger and smaller items and final position of pivot.
        var pivotNewIndex = partition(a, left, right, pivotIndex);
        
        // Recursively sort elements smaller than the pivot.
        quicksort(a, left, pivotNewIndex - 1);
        
        // Recursively sort elements at least as big as the pivot.
        quicksort(a, pivotNewIndex + 1, right);
    }
}
function swap(a, i, j) {
    var t = a[i];
    a[i] = a[j];
    a[j] = t;
}

0 条评论

还没有人评论。
您需要登录后才可以回复。登录 | 立即注册