数组排序
2024年04月06日
一、中文排序
1.1 通过 sort() 与 localeCompare()
let array = ['白鸽', '麻雀', '大象', '狗', '猫', "鸡"];
array = array.sort(function compareFunction(a, b) {
return a.localeCompare(b);
});
console.log(array);
二、混合排序
function pySegSort(array, field) {
if (array.length == 0) return;
if (!String.prototype.localeCompare) return null;
const letters = "*ABCDEFGHIJKLMNOPQRSTUVWXYZ".split("");
const zh = "阿八嚓哒妸发旮哈讥咔垃痳拏噢妑七呥扨它穵夕丫帀".split("");
let chineseReg = /[^\u4e00-\u9fa5]/;//中文正则
let specialCharacterReg = new RegExp("[`\\-~!@#$^&*()=|{}':;',\\[\\].<>《》/?~！@#￥……&*（）——|{}【】‘；：”“'。，、？12345678990]"); //特殊符号
let current;
let result = [];
letters.filter((value1, index1) => {
current = {
initial: '', //字母
data: [], //数据
};
array.map((value2, index2) => {
let value2Item = field ? value2[field] : value2;
// 特殊字符
if (specialCharacterReg.test(value2Item[0])) {
if ((!zh[index1 - 1] || zh[index1 - 1].localeCompare(value2Item) <= 0) && value2Item.localeCompare(zh[index1]) == -1) {
current.data.push(value2);
}
}
// 判断首个字是否是中文
if (chineseReg.test(value2Item[0])) {
// 英文
if (value2Item[0].toUpperCase() == value1) {
current.data.push(value2);
}
} else {
// 中文
if ((!zh[index1 - 1] || zh[index1 - 1].localeCompare(value2Item) <= 0) && value2Item.localeCompare(zh[index1]) == -1) {
current.data.push(value2);
}
}
})
if (current.data.length) {
current.initial = letters[index1]
current.data.sort((a, b) => {
let aItem = field ? a[field] : a;
let bItem = field ? b[field] : b;
return aItem.localeCompare(bItem);
});
current.data.forEach(item => {
result.push(item);
});
}
})
return Array.from(new Set(result)) //去重
}
const array = [
{ id: "v1", cityName: "阿里a" },
{ id: "v2", cityName: "试试s" },
{ id: "v3", cityName: "传参" },
{ id: "v4", cityName: "版本" },
{ id: "v5", cityName: "天津t" },
{ id: "v6", cityName: "安徽a" },
{ id: "v7", cityName: "阿道夫a" },
{ id: "v8", cityName: "匹配p" },
{ id: "v9", cityName: "海南h" },
{ id: "v10", cityName: "请求q" },
{ id: "v11", cityName: "问我" },
{ id: "v12", cityName: "恩恩" },
{ id: "v13", cityName: "让人" },
{ id: "v14", cityName: "英语" },
{ id: "v15", cityName: "已寄" },
{ id: "v16", cityName: "公共" },
{ id: "v17", cityName: "张家口z" },
{ id: "v17", cityName: "A张家口z" },
{ id: "v17", cityName: "CC张家口z" },
{ id: "v17", cityName: "D张家口z" },
{ id: "v17", cityName: "d张家口z" },
{ id: "v17", cityName: "d张家口z" },
{ id: "v17", cityName: "!张家口z" },
{ id: "v17", cityName: "-张家口z" },
{ id: "v17", cityName: "0张家口z" },
{ id: "v17", cityName: "=张家口z" },
{ id: "v17", cityName: "padsjfo" },
{ id: "v17", cityName: "放学" },
{ id: "v17", cityName: "Icons" },
];
console.log(pySegSort(array, 'cityName'));
三、中文排序并归类
四、混合排序并归类
function pySegSort(array, field) {
if (array.length == 0) return;
if (!String.prototype.localeCompare) return null;
const letters = "*ABCDEFGHIJKLMNOPQRSTUVWXYZ".split("");
const zh = "阿八嚓哒妸发旮哈讥咔垃痳拏噢妑七呥扨它穵夕丫帀".split("");
let chineseReg = /[^\u4e00-\u9fa5]/;//中文正则
let specialCharacterReg = new RegExp("[`\\-~!@#$^&*()=|{}':;',\\[\\].<>《》/?~！@#￥……&*（）——|{}【】‘；：”“'。，、？12345678990]"); //特殊符号
let current;
let segs = [];
letters.filter((value1, index1) => {
current = {
initial: '', //字母
data: [], //数据
};
array.map((value2, index2) => {
let value2Item = field ? value2[field] : value2;
// 特殊字符
if (specialCharacterReg.test(value2Item[0])) {
if ((!zh[index1 - 1] || zh[index1 - 1].localeCompare(value2Item) <= 0) && value2Item.localeCompare(zh[index1]) == -1) {
current.data.push(value2);
}
}
// 判断首个字是否是中文
if (chineseReg.test(value2Item[0])) {
// 英文
if (value2Item[0].toUpperCase() == value1) {
current.data.push(value2);
}
} else {
// 中文
if ((!zh[index1 - 1] || zh[index1 - 1].localeCompare(value2Item) <= 0) && value2Item.localeCompare(zh[index1]) == -1) {
current.data.push(value2);
}
}
})
if (current.data.length) {
current.initial = letters[index1]
segs.push(current);
current.data.sort((a, b) => {
return a[field].localeCompare(b[field]);
});
}
})
return Array.from(new Set(segs)) //去重
}
const array = [
{ id: "v1", cityName: "阿里a" },
{ id: "v2", cityName: "试试s" },
{ id: "v3", cityName: "传参" },
{ id: "v4", cityName: "版本" },
{ id: "v5", cityName: "天津t" },
{ id: "v6", cityName: "安徽a" },
{ id: "v7", cityName: "阿道夫a" },
{ id: "v8", cityName: "匹配p" },
{ id: "v9", cityName: "海南h" },
{ id: "v10", cityName: "请求q" },
{ id: "v11", cityName: "问我" },
{ id: "v12", cityName: "恩恩" },
{ id: "v13", cityName: "让人" },
{ id: "v14", cityName: "英语" },
{ id: "v15", cityName: "已寄" },
{ id: "v16", cityName: "公共" },
{ id: "v17", cityName: "张家口z" },
{ id: "v17", cityName: "A张家口z" },
{ id: "v17", cityName: "CC张家口z" },
{ id: "v17", cityName: "D张家口z" },
{ id: "v17", cityName: "d张家口z" },
{ id: "v17", cityName: "d张家口z" },
{ id: "v17", cityName: "!张家口z" },
{ id: "v17", cityName: "-张家口z" },
{ id: "v17", cityName: "0张家口z" },
{ id: "v17", cityName: "=张家口z" },
{ id: "v17", cityName: "padsjfo" },
{ id: "v17", cityName: "放学" },
{ id: "v17", cityName: "Icons" },
];
console.log(pySegSort(array, 'cityName'));
五、数组的相对排序
给你两个数组，arr1 和 arr2
- arr2 中的元素各不相同
- arr2 中的每个元素都出现在 arr1 中
5.1 计数排序
思路:
- arr2 中出现过的元素: 使用 countNums (长度为 arr1 中的最大值 - 最小值 + 1) , 记录 arr1 中每一个元素出现的此次数。随后遍历 arr2 , 当遍历到元素 x 时，将 countNums[x] 个 x 加入到答案中，并将 countNums[x] 清零。遍历结束后，所有在 arr2 中出现过的元素就已经有序了。
- arr2 中未出现的元素: 再次遍历 countNums ,当遍历到元素 x 时，如果 countNums[x] 不为0 ，就将 x 加入到答案中
function relativeSortArray(arr1,arr2){
let max=arr1[0];
let min=arr1[0];
for(let item of arr1){
if(max<item){
max=item;
}
if(min>item){
min=item;
}
}
let range=max-min+1;
let countNums=new Array(range).fill(0);
for(let item of arr1){
countNums[item-min]++;
}
let result=[];
let index=0;
for(let item of arr2){
for(let i=0;i<countNums[item-min];i++){
result[index++]=item;
}
countNums[item-min]=0;
}
for(let i=0;i<range;i++){
for(let j=0;j<countNums[i];j++){
result[index++]=i+min;
}
}
return result;
}
性能分析:
- 时间复杂度:O(m+n+countNums.length)
- 空间复杂度:O(countNums.length)