数据结构常用排序

冒泡排序
function bubbleSort(arr)
{
//原理：每一遍都把最大的数放在后面，所以每一遍过后next < arr.length - 1 - i
for (let i = 0; i < arr.length; i++) {
for (let next = 0; next < arr.length - 1 - i ; next++) {
if (arr[next] > arr[next+1])
{
//只要前面的值比后面大的就交换数组里面的值
let temp = arr[next+1];
arr[next+1] = arr[next];
arr[next] = temp;
}
}
}
return arr;
}
var arr = [1,3,4,2,45,92,0];
console.log(bubbleSort(arr));

//选择排序
function selectionSort(arr)
{
//每一趟都找出数最小的下标，保存在minIndex，每一趟结束时最小数的下标与i交换
let len = arr.length;
let temp,minIndex;
for (let i = 0; i < len - 1; i++) {
minIndex = i;
for (let j = i + 1; j < len; j++) {
//找出最小数的下标
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
//判断当前循环的i是否和取出来最小数的下标是否相等，相等就不用交换数值
if (i != minIndex)
{
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
return arr;
}
var arr = [1,3,4,2,45,92,0];
console.log(selectionSort(arr));

//插入排序
function insertSort(arr){
let preIndex,currentValue;
for (let index = 1; index < arr.length; index++) {
//循环n-1躺
preIndex = index - 1;
currentValue = arr[index];
//每一趟都排序出前i+1个数
while (preIndex >=0 && arr[preIndex] > currentValue) {
arr[preIndex+1] = arr[preIndex];
preIndex--;
}
//当没有进入while循环时，preIndex没有变化，下面一句相当于给自己赋同样的值
arr[preIndex+1] = currentValue;
}
return arr;
}
var arr = [1,3,4,2,45,92,0];
console.log(insertSort(arr));
//1 3 4 2 -1 0
//第一趟:1 3 4 2 -1 0
//第二趟：1 3 4 2 -1 0
//第三趟：1 2 3 4 -1 0
//第四趟：-1 1 2 3 4 0
//第五趟：0 -1 1 2 3 4
//比如第四趟中，1 2 3 4是在while循环中一步一步跟current=0比较，
//大的就向前移动一步arr[preIndex+1] = arr[preIndex];这样前面的数肯定比current大，
//所以可以把current放在最前面

// 快速排序
function quickSort(arr, left, right) {
//为了防止剩一个数时再进行计算
if (left < right) {
//设置最左边的元素为基准点：pivot
let p = arr[left];
//把要排序的序列中比p大的放到右边，比p小的放到左边，p的下标位置为i
let i = left,
j = right;
while(i<j)
{
//j向左移，找到一个比p小的元素，直到找到小于p的数就停止在j下标上
while(arr[j] >= p && i < j){
j--;
}
//i向右移，找到一个比p大的元素
while(arr[i] <= p && i < j){
i++;
}
//当i和j不相等的时候交换
if (i<j){
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
arr[left] = arr[i];
arr[i] = p;
//i-1,i+1是为了让当前基准点继续参加排序
quickSort(arr,left,i - 1);
quickSort(arr, i + 1, right);
}
return arr;
}
var arr = [1,3,4,2,45,2,92,0,-2];
console.log(quickSort(arr,0,arr.length-1));