常用内排序算法

￡神魔★判官ぃ 2022-12-17 07:12 167阅读 0赞

### 一、插入排序 ###

1.  **原理**：比较、插入。将未排序区的数逐一转移到排序区中的合适位置。
2.  **步骤**：从未排序区取一个数，插入到已排序区的合适位置，直到未排序区为空。(插入操作可以转化为从已排序区末尾比较交换)
3.  **时间复杂度**：O(n²)
4.  **空间复杂度**：O(1)
5.  **实现**（升序）
    
        /** * 插入排序 * 原理：比较、插入。将未排序区的数逐一转移到排序区中的合适位置。 * 步骤：从未排序区取一个数，插入到已排序区的合适位置，直到未排序区为空。(插入操作可以转化为从已排序区末尾比较交换) * 时间复杂度：O(n²) * 空间复杂度：O(1) */
        function insertSort(_arr) { 
          let len = _arr.length;
          for(let i=1; i<len; i++){ 
            for(let j=i; j>0; j--){ 
              // 从已排序区末尾比较、交换
              if(_arr[j]<_arr[j-1]) [_arr[j], _arr[j-1]] = [_arr[j-1], _arr[j]];
              else break; // 无需交换时说明已经排序完毕，退出本轮
            }
        
            // 打印排序过程
            console.log((i+1) + ': ' + JSON.stringify(_arr));
          }
        }

### 二、冒泡排序 ###

1.  **原理**：比较、交换。从数组尾部开始进行相邻比较，将较小(大)值往数组头部推，每一轮都能将当前未排序区的最小(大)值推到已排序区的尾部。
2.  **步骤**：从数组最右端开始，将当前比较的两个值中小的一个值交换到左边，整个过程相当于把当前数组未排序区最小的值一步步推到数组最左侧（已排序区），重复n-1轮
3.  **时间复杂度**：O(n²)
4.  **空间复杂度**：O(1)
5.  **实现**（升序）
    
        /** * 2. 冒泡排序 * 原理：从数组尾部开始进行相邻比较，将较小值往数组头部推，每一轮都能将当前未排序区的最小(大)值推到已排序区的尾部。 * 步骤：从数组最右端开始，将当前比较的两个值中小的一个值交换到左边，整个过程相当于把当前数组未排序区最小的值一步步推到数组最左侧（已排序区）,重复n-1次 * 时间复杂度：O(n²) * 空间复杂度：O(1) */
        function bubbleSort(_arr) { 
          let len = _arr.length;
          for(let i=0; i<len-1; i++){ 
            for(let j=len-1; j>=i+1; j--){ 
              if(_arr[j]<_arr[j-1]) [_arr[j], _arr[j-1]] = [_arr[j-1], _arr[j]];
            }
        
            // 打印排序过程
            console.log((i+1) + ': ' + JSON.stringify(_arr));
          }
        }

### 三、选择排序 ###

1.  **原理**：先进行一轮比较、每一轮只进行一次交换。每一轮都将当前未排序区中的最小(大)值找出来，并交换到合适的位置。（先选择，再交换，减少交换开销）
2.  **步骤**：扫描数组，记录下本轮最小值所在索引，交换到已排序区的下一位，重复n-1次
3.  **时间复杂度**：O(n²)
4.  **空间复杂度**：O(1)
5.  **实现**（升序）
    
        /** * 3. 选择排序 * 原理：每一轮都将当前未排序区中的最小(大)值找出来，并交换到合适的位置。（先选择，再交换，减少交换开销） * 步骤：扫描数组，记录下本轮最小值所在索引，交换到已排序区的下一位，重复n-1次 * 时间复杂度：O(n²) * 空间复杂度：O(1) */
        function selectSort(_arr) { 
          let len = _arr.length;
          for(let i=0; i<len-1; i++){ 
            let currIndex = i;
            for(let j=i+1; j<len; j++){ 
              if(_arr[j]<_arr[currIndex]) currIndex = j;
            }
            currIndex !== i && ([_arr[currIndex], _arr[i]] = [_arr[i], _arr[currIndex]]);
        
            // 打印排序过程
            console.log((i + 1) + ': ' + JSON.stringify(_arr));
          }
        }

### 四、Shell排序 ###

1.  **原理核心**：充分利用插入排序的最佳比较次数，对整个数组划分子序列分别进行插入排序，通过缩小子序列的组成间隔来逐步扩大子序列的规模，进而让数组整体逐步趋向有序。
2.  **步骤**：按间隔除以3递减依次划分出子序列，对每个子序列进行插入排序。  
    ![shell排序过程gif][shell_gif]
3.  **时间复杂度**：O(n^1.5) 间隔除以3递减
4.  **空间复杂度**：O(n) 子序列
5.  **实现**（升序）
    
        /** * shell排序（间隔以除以3递减） * 原理核心：充分利用插入排序的最佳比较次数，对整个数组划分子序列分别进行插入排序，通过缩小子序列的组成间隔来逐步扩大子序列的规模，进而让数组整体逐步趋向有序。 * 步骤：按间隔除以3递减依次划分出子序列，对每个子序列进行插入排序。 * 时间复杂度：O(n^1.5) * 空间复杂度：O(n) 子序列 */
        function shellSort(_arr) { 
          // 使用插入排序算法的辅助函数，_idxArr是_arr子序列索引值的列表，借此对_arr的子序列进行排序
          let helpInsSort = (_idxArr) => { 
            console.log('子序列: ' + JSON.stringify(_idxArr.map(v => _arr[v])));
            let len = _idxArr.length;
            for(let i=1; i<len; i++){ 
              for(let j=i; j>0; j--){ 
                if(_arr[_idxArr[j]]<_arr[_idxArr[j-1]]){   // 要交换_arr中值的位置，_idxArr中的索引值不能交换，_idxArr只起到定位子序列的作用
                  [_arr[_idxArr[j]], _arr[_idxArr[j-1]]] = [_arr[_idxArr[j-1]], _arr[_idxArr[j]]];
                }
                else break;
              }
            }
            console.log(' 结果: ' + JSON.stringify(_idxArr.map(v => _arr[v])) + '\n');
          }
          // 按除以3的递减间隔对子序列进行插入排序
          let len = _arr.length;
          let currIncrement; // 间隔
          while(true){ 
            // 计算当前间隔
            currIncrement = currIncrement === undefined ? Math.round(len / 3) : Math.round(currIncrement / 3);
            currIncrement === 0 && (currIncrement = 1); // 间隔最小为1
            console.log('----> 当前间隔: ' + currIncrement)
            // 对子序列执行插入排序
            for (let startIdx = 0; startIdx < currIncrement; startIdx++) {   // 有currIncrement个子序列
              // 构建子序列索引列表
              let idxArr = [];
              let currIdx = startIdx;
              while (currIdx < len){ 
                idxArr.push(currIdx);
                currIdx += currIncrement;
              }
              // 对子序列进行插入排序
              helpInsSort(idxArr);
            }
            if (currIncrement === 1) break;
          }
        }

### 五、归并排序 ###

1.  **原理**：分而治之，将数组逐步等分为子序列，最终子序列长度为1，然后将相邻子序列合并为有序子数组（从两个子序列头部开始取较小(大)的一个拼接为新序列）
2.  **递归法**
    
        /** * 5.1 递归法（分治法） * 步骤：递归对数组进行等分，并将等分的两个进行有序合并（不断从两个数组队头取较小(大)值）；递归的结束条件是数组不可再分(length<=1) * 时间复杂度：O(nlogn) * 空间复杂度：O(nlogn) */
        function mergeSort2(_arr) { 
          let merge = (_arr) => { 
            let len = _arr.length;
            if(len <= 1) return _arr;
            let leftArr = merge(_arr.slice(0, Math.ceil(len/2)));
            let rightArr = merge(_arr.slice(Math.ceil(len/2)));
            // 拼接两个子序列
            let leftLen = leftArr.length;
            let rightLen = rightArr.length;
            let leftIdx = rightIdx = 0;
            let sortedArr = [];
            while(true){ 
              if(leftIdx < leftLen && rightIdx < rightLen){ 
                if (leftArr[leftIdx] < rightArr[rightIdx]) sortedArr.push(leftArr[leftIdx++]);
                else sortedArr.push(rightArr[rightIdx++]);
              }
              else if(leftIdx < leftLen){ 
                while (leftIdx < leftLen){ 
                  sortedArr.push(leftArr[leftIdx++]);
                }
                break;
              }
              else { 
                while (rightIdx < rightLen) { 
                  sortedArr.push(rightArr[rightIdx++]);
                }
                break;
              }
            }
            return sortedArr;
          }
          // 此处为了和其他算法统一，深复制修改原数组_arr
          merge(_arr).forEach((v, i) => { 
            _arr[i] = v;
          })
        }
3.  **非递归法**
    
        /** * 4.2 迭代法实现（逆分治法） * 步骤：下边的算法不是采用递归方法逐步等分切割子序列，而是以迭代方法从子序列长度为1开始逐步合并相邻子序列（主要注意越界的处理方法） * 时间复杂度：O(nlogn) * 空间复杂度：O(n) */
        function mergeSort1(_arr) { 
          let len = _arr.length;
          let subLen = 1; // 1, 2, 4... 当前的子序列最大长度
          while(subLen < len){ 
            let currArr = []; // 该轮排序后的数组，最终长度为原数组长度
            for(let head=0; head<len; head+=(2*subLen)){ 
              // 依次比较相邻子序列的队头，将较小值依次压入currArr中
              let left = head;
              let right = head + subLen;
              let times = subLen*2; // 最大比较次数，2倍子序列最大长度
              while(times--){ 
                // 越界处理（右序列先越界）
                if(right >= len) {   // 右子序列越界
                  while(left < len && left < (head+subLen)){   // 左子序列全部压入currArr
                    currArr.push(_arr[left]);
                    left++;
                  }
                  break;
                }
                // 取两个子序列队头的较小值
                if(left < head + subLen && (right >= (head + 2 * subLen) || _arr[left] < _arr[right])){ 
                  currArr.push(_arr[left]);
                  left++;
                }
                else{ 
                  currArr.push(_arr[right]);
                  right++;
                }
              }
            }
            // 此处为了和其他算法统一，深复制修改原数组_arr
            currArr.forEach((v, i) => { 
              _arr[i] = v;
            })
            subLen *= 2;
        
            // 打印排序过程
            console.log(JSON.stringify(_arr));
          }
        }

### 六、快速排序 ###

1.  **原理核心**：分治法，与归并排序不同的是，快排是从数组中随机取一个值(pivot)，其余值通过与pivot比较大小来拆分为2个子数组，并对子数组采取同样的方法，直到不可分割。
2.  **步骤**：逐层递归，每层使用双指针法。
3.  **时间复杂度**：O(nlogn)
4.  **空间复杂度**：O(logn) 递归
5.  **实现**（升序）
    
        /** * 5. 快速排序 * 原理：分治法，与归并排序不同的是，快排是从数组中随机取一个值(pivot)，其余值通过与pivot比较大小来拆分为2个子数组，并对子数组采取同样的方法，直到不可分割 * 步骤：逐层递归，每层使用双指针法。 * 时间复杂度：O(nlogn) * 空间复杂度：O(logn) 递归 */
        function quickSort(_arr) { 
          let quickSortHelp = (_arr) => { 
            let len = _arr.length;
            if(len <= 1 || _arr.every(item => item === _arr[0])) return _arr;
            let pivot = _arr[Math.floor(len * Math.random())];  // 随机取pivot
            // 双指针法
            let left = 0, right = len - 1;
            while(true){ 
              while(_arr[left] <= pivot) left++;
              while(_arr[right] > pivot) right--;
              if(left<right){ 
                [_arr[left], _arr[right]] = [_arr[right], _arr[left]];
                left++;
                right--;
              }
              else break;
            }
            return quickSortHelp(_arr.slice(0, left)).concat(quickSortHelp(_arr.slice(left)));
          }
          // 此处为了和其他算法统一，深复制修改原数组_arr
          quickSortHelp(_arr).forEach((v, i) => { 
            _arr[i] = v;
          })
        }

### 七、堆排序 ###

1.  **原理**：利用最大堆或最小堆。
2.  **步骤**：先建堆，然后取堆头元素，进行堆元素删除操作(siftdown)，继续取堆头。
3.  **时间复杂度**：O(nlogn)
4.  **空间复杂度**：O(1)

[shell_gif]: /images/20221123/bcdd5bae4ca540b1bfe4e2f6656858c5.png