Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

深入理解Array.prototype.sort() #229

Open
FrankKai opened this issue Jun 18, 2020 · 0 comments
Open

深入理解Array.prototype.sort() #229

FrankKai opened this issue Jun 18, 2020 · 0 comments

Comments

@FrankKai
Copy link
Owner

FrankKai commented Jun 18, 2020

  • 初识sort()
  • sort() demo
  • sort() 语法
  • sort() 升降序规则(重点)
  • 创建、展示和排序数组
  • 排序non-ASCII字符
  • map()结合sort()一起使用
  • 对象根据value给key排序

初识sort()

  • sort()函数会**原地(in place)**排序数组中的元素,返回排序的数组。(原地意味着在原数组的基础上做修改,不会开辟新的空间
  • sort()函数默认的排序顺序为升序,默认排序建立在将元素转换为字符串的基础上,然后比较UTF-16单位的序列。
  • sort()函数的时间复杂度和空间复杂度无法保证,因为依赖于实现。在sort()函数内部,采用了插排和快排以及一系列排序优化,因此时间复杂度和空间度是跟着情况变化的。 更多可以查看:发现算法之美-排序

举例说明"将元素转换为字符串":

  • 例如["a","A"].sort()//["A","a"]这是因为a的码为97,A的码为65
  • [111, 2].sort();//[111, 2]这是因为1的码为49 "111".charCodeAt();//49,2的码为50"2".charCodeAt();//50

sort() demo

const months = ['March', 'Jan', 'Feb', 'Dec'];
months.sort();
console.log(months);
// ["Dec", "Feb", "Jan", "March"]
const array1 = [1, 30, 4, 21, 100000];
array1.sort();
console.log(array1);
// [1, 100000, 21, 30, 4]

sort() 语法

arr.sort([compareFunction])

比较函数compareFunction

  • 比较函数是可选的
  • 比较函数用来定义排序的顺序
  • 调用sort()后,数组的元素会转为字符串
  • 排序规则按照每个字符的Unicode,通常是根据头字符:“foo”中的“f”,111中的“1”
  • 比较函数中一共有两个参数,第一个参数firstEl第二个参数secondEl,定义升降序
  • sort()的返回值是一个排序好的原数组,排序后原数组的元素顺序发生变化,

sort() 升降序规则(重点)

  • 无论比较函数有没有指定,所有的undefined元素会被排在数组的尾部
  • 如果比较函数没有指定,非undefined数组会被转为字符串并且按照UTF-16编码进行排序。例如 "banana"在"cherry"前;9出现在80之前,但是由于被转换为字符串,所以"80"排在了"9"之前
  • 如果比较函数明确声明了,数组所有的非undefined元素根据比较函数的返回值进行排序。假设a和b是需要比较的2个元素,排序规则如下:
    • 如果compareFunction(a, b)的返回值小于0,a的index值比b小,升序排列。[1,9,2,3,4,5,6,"foo","bar","baz"].sort((a,b)=>a-b);// [1, 2, 3, 4, 5, 6, 9, "foo", "bar", "baz"]
    • 如果compareFunction(a, b)的返回值等于0,保持a和b的相对位置不变,再对其他不同的元素进行排序。
    • 如果compareFunction(a, b)返回的值大于0,b的index值比a小,降序排列。
    • compareFunction(a, b)必须总是返回相同的值,当给定一对特定的元素a和b作为它的两个参数时。如果返回的结果不一致,则未定义排序顺序。

比较函数伪代码:

function compare(a, b) {
  if (a is less than b by some ordering criterion) {
    return -1;
  }
  if (a is greater than b by the ordering criterion) {
    return 1;
  }
  // a must be equal to b
  return 0;
}

为了比较数字而不是字符串,可以对a,b做减法运算

// 升序排列
function compareNumbers(a, b) {
  return a - b;
}
// 降序排列
function compareNumbers(a, b) {
  return b - a;
}

sort函数可以直接运行匿名函数:

var numbers = [4, 2, 5, 1, 3];
numbers.sort(function(a, b) {
  return a - b;
});
console.log(numbers);

// [1, 2, 3, 4, 5]

箭头函数写法:

let numbers = [4, 2, 5, 1, 3];
numbers.sort((a, b) => a - b);
console.log(numbers);

// [1, 2, 3, 4, 5]

根据对象的一个属性排序:

var items = [
  { name: 'Edward', value: 21 },
  { name: 'Sharpe', value: 37 },
  { name: 'And', value: 45 },
  { name: 'The', value: -12 },
  { name: 'Magnetic', value: 13 },
  { name: 'Zeros', value: 37 }
];

// sort by value
items.sort(function (a, b) {
  return a.value - b.value;
});

// sort by name
items.sort(function(a, b) {
  var nameA = a.name.toUpperCase(); // ignore upper and lowercase
  var nameB = b.name.toUpperCase(); // ignore upper and lowercase
  if (nameA < nameB) {
    return -1;
  }
  if (nameA > nameB) {
    return 1;
  }

  // names must be equal
  return 0;
});

创建、展示和排序数组

  • 全是字符串(普通字符)
  • 全是字符串(数字字符)
  • 全是数字
  • 既有数字也有普通字符串
var stringArray = ['Blue', 'Humpback', 'Beluga'];
var numericStringArray = ['80', '9', '700'];
var numberArray = [40, 1, 5, 200];
var mixedNumericArray = ['80', '9', '700', 40, 1, 5, 200];

function compareNumbers(a, b) {
  return a - b;
}

console.log('stringArray:', stringArray.join());
console.log('Sorted:', stringArray.sort());

console.log('numberArray:', numberArray.join());
console.log('Sorted without a compare function:', numberArray.sort());
console.log('Sorted with compareNumbers:', numberArray.sort(compareNumbers));

console.log('numericStringArray:', numericStringArray.join());
console.log('Sorted without a compare function:', numericStringArray.sort());
console.log('Sorted with compareNumbers:', numericStringArray.sort(compareNumbers));

console.log('mixedNumericArray:', mixedNumericArray.join());
console.log('Sorted without a compare function:', mixedNumericArray.sort());
console.log('Sorted with compareNumbers:', mixedNumericArray.sort(compareNumbers));
stringArray: Blue,Humpback,Beluga
Sorted: Beluga,Blue,Humpback

numberArray: 40,1,5,200
Sorted without a compare function: 1,200,40,5
Sorted with compareNumbers: 1,5,40,200

numericStringArray: 80,9,700
Sorted without a compare function: 700,80,9
Sorted with compareNumbers: 9,80,700

mixedNumericArray: 80,9,700,40,1,5,200
Sorted without a compare function: 1,200,40,5,700,80,9
Sorted with compareNumbers: 1,5,9,40,80,200,700

排序non-ASCII字符

对于类似e, é, è, a, ä这样的字符来说,可以通过String.localeCompare进行排序。

var items = ['réservé', 'premier', 'communiqué', 'café', 'adieu', 'éclair'];
items.sort(function (a, b) {
  return a.localeCompare(b);
});

// items is ['adieu', 'café', 'communiqué', 'éclair', 'premier', 'réservé']

map()结合sort()一起使用

// the array to be sorted
var list = ['Delta', 'alpha', 'CHARLIE', 'bravo'];

// temporary array holds objects with position and sort-value
var mapped = list.map(function(el, i) {
  return { index: i, value: el.toLowerCase() };
})

// sorting the mapped array containing the reduced values
mapped.sort(function(a, b) {
  if (a.value > b.value) {
    return 1;
  }
  if (a.value < b.value) {
    return -1;
  }
  return 0;
});

// container for the resulting order
var result = mapped.map(function(el){
  return list[el.index];
});
// ["alpha", "bravo", "CHARLIE", "Delta"]
[
  {
    "index": 1,
    "value": "alpha"
  },
  {
    "index": 3,
    "value": "bravo"
  },
  {
    "index": 2,
    "value": "charlie"
  },
  {
    "index": 0,
    "value": "delta"
  }
]

条件改为if (a.value < b.value) { return 1; } if (a.value > b.value) { return -1; }时,变为降序。

[
  {
    "index": 0,
    "value": "delta"
  },
  {
    "index": 2,
    "value": "charlie"
  },
  {
    "index": 3,
    "value": "bravo"
  },
  {
    "index": 1,
    "value": "alpha"
  }
]

也可以加一个meta,改为:

// the array to be sorted
var list = ['Delta', 'alpha', 'CHARLIE', 'bravo'];

// temporary array holds objects with position and sort-value
var mapped = list.map(function(el, i) {
  return { index: i, value: el.toLowerCase(), meta: el, };
})

// sorting the mapped array containing the reduced values
mapped.sort(function(a, b) {
  if (a.value > b.value) {
    return 1;
  }
  if (a.value < b.value) {
    return -1;
  }
  return 0;
});
var result = mapped.map(function(el){
  return el.meta
});
// ["alpha", "bravo", "CHARLIE", "Delta"]

对象根据value给key排序

有一个高级用法:对象根据value给key排序

const items = {
   foo: 2,
   bar: 1,
   baz: 3,
};
// 降序
const sortKeys = Object.keys(items).sort((a,b)=>items[b]-items[a])
// ["baz", "foo", "bar"]

leetcode347.前K个高频元素可以通过这个特性做出来:

var topKFrequent = function (nums, k) {
    /**
     * 解法1:统计排序法
     */
    const obj = {};
    for (let num of nums) {
        if (!obj[num]) {
            obj[num] = 1
        } else {
            obj[num]++;
        };
    }
    // {1:3, 2:2, 3:1} => [1, 2, 3]
    // {8:2, 3:5, 2:4} => [3, 2, 8]
    const descKeys = Object.keys(obj).sort((a, b) => obj[b] - obj[a]);
    const result = descKeys.splice(0, k);
    return result;
};

题解位于:https://github.com/FrankKai/leetcode-js/blob/master/347.Top_K_Frequent_Elements.js

总结

  • 对于数值型可以通过减法运算。a-b(升序),b-a(降序)进行排序
  • 对于字符型需要通过大于小于等于进行排序。a>b时1,a<b时-1,a===b时0为升序;a<b时1,a>b时-1,a===b时0为降序

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

1 participant