js 排序

1.快速排序1（纯数字数组）

// 快速排序1（纯数字数组）
function devide(array, start, end) {
    if(start >= end) return array;
    var baseIndex = Math.floor((start + end) / 2), // 基数索引
         i = start,
         j = end;

    while (i <= j) {
        while (array[i] < array[baseIndex]) {
            i++;
        }
        while (array[j] > array[baseIndex])  {
            j--;
        }

        if(i <= j) {
            var temp = array[i];
            array[i] = array[j];
            array[j] = temp;
            i++;
            j--;
        }
    }
    return i;
}

function quickSort(array, start, end) {
    if(array.length < 1) {
        return array;
    }
    var index = devide(array, start, end);
    if(start < index -1) {
        quickSort(array, start, index - 1);
    }
    if(end > index) {
        quickSort(array, index, end);
    }

    return array;
};

var arr = [12,2.5,22,.5,6,8,10];
console.log('排序前：',arr);

var sorted = quickSort(arr, 0, arr.length-1);
console.log('排序后：',sorted);

image.png

2.快速排序2（对象数组）

// 快速排序2（对象数组）
function devide(array, start, end, item) {
    if(start >= end) return array;
    var baseIndex = Math.floor((start + end) / 2), // 基数索引
         i = start,
         j = end;

    while (i <= j) {
        while (array[i][item] < array[baseIndex][item]) {
            i++;
        }
        while (array[j][item] > array[baseIndex][item])  {
            j--;
        }

        if(i <= j) {
            var temp = array[i][item];
            array[i][item] = array[j][item];
            array[j][item] = temp;
            i++;
            j--;
        }
    }
    return i;
}

function quickSort(array, start, end, item) {
    if(array.length < 1) {
        return array;
    }
    var index = devide(array, start, end, item);
    if(start < index -1) {
        quickSort(array, start, index - 1, item);
    }
    if(end > index) {
        quickSort(array, index, end, item);
    }

    return array;
}

var arr = [{v:25},{v:3},{v:12},{v:2.5},{v:12.5},{v:5}];
var arrDeepCopy = JSON.parse(JSON.stringify(arr));// 深拷贝
console.log('排序前：',arrDeepCopy);

quickSort(arr, 0, arr.length-1, 'v');
console.log('排序后：',arr);

image.png

注意：这地方有个坑，只会调换排序的属性，其他属性不变。比如：

现在有三个人对象，对象属性包括姓名、年龄，现在需要安装年龄进行排序。
var arr = [{age:15,name:'张三'},{age:17,name:'王五'},{age:14,name:'李四'}];
按照age，quickSort 排序后结果为：
arr = [{age:14,name:'张三'},{age:15,name:'王五'},{age:17,name:'李四'}];
显然不是我们想要的结果。

我们想要的是：
arr = [{age:14,name:'李四'},{age:15,name:'张三'},{age:17,name:'王五'}];
下面介绍另一中排序：
/**
 * 按对象属性排序
 * @param arr 对象数组
 * @param attribute 需要排序的属性
 * @returns {*}
 */
export function sortedByAttribute(arr, attribute){
    if(arr == null || arr == undefined || arr.length == 0){
        return arr;
    }
    if(typeof arr[0][attribute] == "string"){// 字符排序：正序
        arr.sort(function (a,b) {
            return a[attribute].localeCompare(b[attribute]);
        });
    }else if(typeof arr[0][attribute] == "number"){// 数字排序：正序
        arr.sort(function (a,b) {
            return a[attribute] - b[attribute];
        });
    }
    return arr;
}