let arr = []
for(let i = 0; i < 10; i++) {
arr.push(Math.floor(Math.random() * 10))
}
console.log(arr)
// bubbleSort(arr)
// insetSort(arr)
// console.log(mergeSort(arr))
// changeSort(arr)
// shellSort(arr)
console.log(quickSort(arr))
//冒泡排序
function bubbleSort(arr) {
for(let i = 0; i < arr.length - 1; i++) {
for(let j = 0; j < arr.length - 1 - i; j++) {
if(arr[j] > arr[j + 1]) {
let temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
console.log(arr)
}
//插入排序
function insetSort(arr) {
for(let i = 1; i < arr.length; i++) {
let index = i;
let temp = arr[i];
while(index > 0 && arr[index - 1] > temp) {
index--;
}
arr.splice(i, 1);
arr.splice(index, 0, temp);
}
console.log(arr)
}
//归并排序
function mergeSort(arr) {
if(arr.length < 2) {
return arr
}
let mid = Math.floor(arr.length / 2);
let leftArr = arr.slice(0, mid);
let rightArr = arr.slice(mid);
return merge(mergeSort(leftArr), mergeSort(rightArr))
}
function merge(leftArr, rightArr) {
let res = [];
while(leftArr.length > 0 && rightArr.length > 0) {
if(leftArr[0] < rightArr[0]) {
res.push(leftArr.shift())
}else {
res.push(rightArr.shift())
}
}
if(leftArr.length != 0) {
res.push(...leftArr)
}
if(rightArr.length != 0) {
res.push(...rightArr)
}
return res
}
//选择排序
function changeSort(arr) {
for(let i = 0; i < arr.length - 1; i++) {
let index = i;
for(let j = i + 1; j < arr.length; j++) {
if(arr[j] < arr[index]) {
index = j;
}
}
let temp = arr[i];
arr[i] = arr[index];
arr[index] = temp;
}
console.log(arr)
}
//希尔排序
function shellSort(arr) {
for(let gap = Math.floor(arr.length / 2); gap > 0; gap = Math.floor(gap / 2)) {
for(let i = gap; i < arr.length; i ++) {
let index = i;
let temp = arr[i];
while(index > 0 && arr[index - gap] > temp) {
index -=gap;
}
arr.splice(i, 1);
arr.splice(index, 0, temp);
}
}
console.log(arr)
}
//快速排序
function quickSort(arr) {
if(arr.length < 2) {
return arr
}
let index = Math.floor(arr.length / 2);
let temp = arr.splice(index, 1)[0];
let leftArr = [];
let rightArr = [];
for(let i = 0; i < arr.length; i++) {
if(arr[i] < temp) {
leftArr.push(arr[i]);
}else {
rightArr.push(arr[i]);
}
}
return [...quickSort(leftArr), temp, ...quickSort(rightArr)]
}
console