对一个包含 a-z,A-Z以及数字的数组进行排序，最终排序后结果为小写字母，数字，大写字母的数组。 #8

Activity

1. CodeRookie262

   added

   算法

   排序

   on Dec 24, 2020
2. CodeRookie262

   changed the title [-]将数组进行排序，数组中的元素包含 a-z,A-Z以及数字，小写字母内部和大写字母内部不要求有序，最终排序后结果为小写字母，数字，大写字母的数组。[/-] [+]对一个包含 a-z,A-Z以及数字的数组进行排序，最终排序后结果为小写字母，数字，大写字母的数组。[/+] on Dec 24, 2020
3. CodeRookie262 commented on Dec 25, 2020

   

   CodeRookie262

   on Dec 25, 2020

   OwnerAuthor

   More actions

   /**
    * 对一个包含 a-z,A-Z以及数字的数组进行排序，最终排序后结果为小写字母，数字，大写字母的数组。
    * @param {Array<String | Number>} array
    * @returns {Array<String | Number>} [...lowerCase,...number,...upperCase]
    */
   // 解法一：桶排序
   // 缺点：空间复杂度大
   function BlendSort(array) {
     let buckets = Array(3)
         .fill(0)
         .map(() => []),
       temp = [];
   
     array.forEach(item => {
       if (typeof item === 'string') {
         if (item >= 'a') {
           buckets[0].push(item);
         } else {
           buckets[2].push(item);
         }
       } else {
         buckets[1].push(item);
       }
     });
   
     buckets.forEach(i => temp.push(...i));
   
     return temp;
   }
   
   // 解法二：双指针遍历
   // 空间复杂度：O(1)
   // 时间复杂度：O(n)
   function BlendSort(array) {
     let len = array.length,
       index = 0,
       left = 0,
       right = len - 1;
   
     // 终止条件
     if (len <= 1) return array;
   
     while (index <= right) {
       if (typeof array[index] === 'number') {
         index++;
       } else if (array[index] >= 'a') {
         swap(array, index++, left++);
       } else {
         swap(array, index, right--);
       }
     }
   
     return array;
   }
   
   /**
    * 交换元素
    * @param {Array} array 原数组
    * @param {Number} left 索引
    * @param {Number} right 索引
    */
   function swap(array, left, right) {
     if (left === right) return;
     [array[left], array[right]] = [array[right], array[left]];
   }