首页 > 其他 > 详细

[Algorithms] Quicksort algorithm using TypeScript

时间:2018-12-18 22:19:15      阅读:188      评论:0      收藏:0      [点我收藏+]

Quicksort (also called partition sort and pivot sort) is arguably the most used sorting algorithm. It is the one commonly implemented internally in language runtimes. In this lesson we cover the quick sort algorithm, why is it called quick and how to implement it using TypeScript / JavaScript.

 

export function quickSort(array) {
  array = [...array];
  partition(array, 0, array.length);
  return array;
}

function partition(array, start, end) {
  const length = end - start;
  if (length <= 1) return;

  // select the pivot
  const pivotIndex = start + Math.floor(Math.random() * length);
  // move the pivot to the beginning of the array
  [array[start], array[pivotIndex]] = [array[pivotIndex], array[start]];
  // get the pivot value
  const pivot = array[start];
  // get the pivot index
  let pivotRank = start;
  // loop thought the array, swap every number each is smaller
  // than the pivor
  for (let index = start + 1; index < end; index++) {
    if (array[index] < pivot) {
      // increase the rank poisition first
      pivotRank++;
      // swap the current number and rand poisition
      [array[index], array[pivotRank]] = [array[pivotRank], array[index]];
    }
  }
  // move the pivot to the pivotRank position
  if (pivotRank !== start) {
    [array[start], array[pivotRank]] = [array[pivotRank], array[start]];
  }

  partition(array, start, pivotRank);
  partition(array, pivotRank + 1, end);
}

const test = [5, 1, 8, 7, 4, 3, 6, 9];
const res = quickSort(test);

document.write(res);

 

 Simpfily way:

function quickSort (array) {

    if (array.length <= 1) {
        return array;
    }

    let pivotIndex = 0;
    let pivot = array[pivotIndex];

    let less = []
    let greater = []

    for (let i in array) {
        if (i != pivotIndex) {
            array[i] > pivot ? greater.push(array[i]): less.push(array[i]);
        }
    }

    return [
        ...quickSort(less),
        pivot,
        ...quickSort(greater)
    ]
}

console.log(quickSort([6, 5, 4, 3, 2, 1, 7,9, 8]))

 

 

[Algorithms] Quicksort algorithm using TypeScript

原文:https://www.cnblogs.com/Answer1215/p/6799983.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!