var arr = generateRandomArr(50);
maopao(arr);
select(arr);
insert_sort(arr);
arr = quick_sort(arr);
console.log(arr);
// 产生随机数
function generateRandomArr(n){
let arr = [];
let temp;
for(let i = 0; i < n; i++){
temp = Math.round(Math.random()*1000);
arr.push(temp);
}
console.log(arr)
return arr;
}
冒泡排序
function maopao(arr){
for(let j = arr.length-1; j > 0; j--){
let temp;
for(let i = 0; i < j; i++){
if(arr[i] > arr[i+1]){
temp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = temp;
}
}
}
}
选择排序
- 在未排序序列中找到最小元素,存放到排序序列的起始位置,
- 再从剩余未排序元素中继续寻找最小元素,然后放到已排序序列的末尾
- 重复步骤2
function select(arr){
for(let i = 0; i < arr.length; i++){
let index = i;
for(let j = i+1; j < arr.length; j++){
if(arr[index] > arr[j]){ // 找出最小值,从小到大排序
index = j;
}
}
if(index !== i){
var temp = arr[i];
arr[i] = arr[index];
arr[index] = temp;
}
}
}
插入排序
- 从第一个元素开始,该元素可以认为已经被排序
- 取出下一个元素,在已经排序的元素序列中从后向前扫描
- 如果该元素(已排序)大于新元素,将该元素移到下一位置
- 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
- 将新元素插入到该位置后
- 重复步骤2~5
function insert_sort(arr){
for(let i = 1; i < arr.length; i ++){
let temp = arr[i];
for(let j = i - 1; j >= 0; j--){
if(temp < arr[j]){
arr[j+1] = arr[j];
}else{
arr[j+1] = temp;
}
}
}
}
快速排序
- 从数列中挑出一个元素,称为"基准"(pivot),
- 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区结束之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
- 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。
function quick_sort(arr){
if(arr.length <= 1) return arr;
let pivotIndex = Math.floor(arr.length / 2) ;
let pivot = arr.splice(pivotIndex, 1)[0];
let left = [];
let right = [];
for (let i = 0; i < arr.length; i++){
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return quick_sort(left).concat(pivot, quick_sort(right));
}
网友评论