quickSort

快速排序

by Chris_Walter

JavaScript

class ArrayList{
  constructor(){
	  this.array = [];
	}
	insert(item){
	  this.array.push(item);
	}
	toString(){
	  return this.array.join();
	}
	swap(array, A, B){
	  [array[A], array[B]] = [array[B], array[A]];
	}
	partition(array, left, right){
	  const pivot = array[Math.floor((left + right) / 2)];
		let i = left;
		let j = right;
		while(i <= j){
		  while(array[i] < pivot){
			 i++;
			}
			while(array[j] > pivot){
			 j--;
			}
			if(i <= j){
			  this.swap(array, i, j);
				i++;
				j--;
			}
		}
		console.log(i);
		return i;
	}
	quick(array, left, right){
	  let index;
		if(array.length > 1){
		  index = this.partition(array, left, right);
			if(left < index-1){
			  this.quick(array, left, index-1);
			}
			if(index < right){
			  this.quick(array, index, right);
			}
		}
		return array;
	}
	quickSort(){
	  this.array = this.quick(this.array, 0, this.array.length-1);
	}
}


const nonSortedArray = (arraySize)=> {
  const array = new ArrayList();
  for(let i=0; i<arraySize; i++){
	  array.insert(Math.random()*100);
	}
	console.log(array);
	console.time();
	array.quickSort();
	console.timeEnd();
	console.log(array);
}

nonSortedArray(5);