尼采般地抒情

公告栏

此网站主题为本人手写主题, 主题待开源···

站点信息

文章总数目: 305
已运行时间: 1063
目录
  1. 一、插入类排序
    1. ✅直接插入
    2. 优化:折半插入
    3. 优化:希尔排序
  2. 二、交换类排序
    1. ✅ 冒泡排序
    2. 快速排序
  3. 三、选择类排序
    1. ✅ 简单选择排序
    2. 树形选择排序
    3. 堆排序
  4. 四、归并排序
    1. 2-路归并排序
  5. 五、分配类排序
    1. 基数排序
  6. 六、外部排序
    1. 基本方法
    2. 多路平衡归并
    3. 置换-选择排序
    4. 最佳归并树
  7. 参考

尼采般地抒情

尼采般地抒情

公告栏

此网站主题为本人手写主题, 主题待开源···

站点信息

文章总数目: 305
已运行时间: 1063


前言:排序按照所占用的计算机内部存储设备,可以分为:内部排序外部排序

  • 内部排序:占用的是内存,待排序序列全部放在内存加以排序处理
  • 外部排序:占用的是外存,数据量比较大,内存空间不足以一次性全部容纳数据的情况


本文章 通过912. 排序数组 题目,以此来总结内部排序的各种排序算法。


一、插入类排序

将无序的子序列插入到有序序列中

✅直接插入

将元素序列走一遍,走到某个元素时,将其插入到已走过的已排序序列中,这样可以保证走完所有元素,然后所有的元素都是排序好的。

数据结构选用的时顺序表

/**

- @param {number[]} nums
- @return {number[]}
  _/
  var sortArray = function(nums) {
  for (let i = 0; i<nums.length; i++) {
  let flag = i
  for(let j = flag-1;j>=0;j--) {
  if (nums[flag] < nums[j]) {
  let temp = nums[j]
  nums[j] = nums[flag]
  nums[flag] = temp
  flag--
  }
  }
  }
  return nums
  };

优化:折半插入

在直接插入的过程中,找到一个元素,然后再需要从后往前依次查找“该在”的位置,对其查找进行了折半优化

/_ 折半插入排序 _/
  void BinsertSort(SqList &S) {
  for (int i = 2; i <= S.length;i++) {
  S.data[0] = S.data[i];
  int low = 1;
  int high = i - 1;
  while (low <= high) {
  int m = (low + high) / 2;
  if (S.data[0]<S.data[m]) high = m - 1;
  else low = m + 1;
  }
  int j;
  for (j = i - 1; j >= high + 1;--j)
  S.data[j + 1] = S.data[j];
  S.data[high + 1] = S.data[0];
  }
  }

优化:希尔排序

/_ 希尔排序 \*/
  void ShellInsert (SqList &L, int dk) {
  for (int i = dk + 1; i <= L.length;++i) {
  if (L.data[i]<L.data[i-dk]) {
  L.data[0] = L.data[i];
  int j;
  for (j = i - dk; j > 0 && L.data[0] < L.data[j]; j -= dk)
  L.data[j + dk] = L.data[j];
  L.data[j + dk] = L.data[0];
  }
  }
  }
  void ShellSort (SqList &L, int dt[],int t) {
  for (int k = 0; k < t;++k) {
  ShellInsert(L, dt[k]);
  }
  }

二、交换类排序

✅ 冒泡排序

/\*\*
- @param {number[]} nums
- @return {number[]}
  _/
  var sortArray = function(nums) {
  for (let i = nums.length - 1; i>0; i--) {
  for (let j = 0; j<i; j++) {
  if (nums[j] > nums[j+1]) {
  let temp = nums[j]
  nums[j] = nums[j+1]
  nums[j+1] = temp
  }
  }
  }
  return nums
  };

快速排序

/_ 快速排序 \*/
  int Partition (SqList &L, int low, int high) {
  L.data[0] = L.data[low];
  int pivotkey = L.data[low];
  while (low < high) {
  while (low<high && L.data[high]>=pivotkey)
  --high;
  L.data[low] = L.data[high];
  while (low<high && L.data[low]<=pivotkey)
  ++low;
  L.data[high] = L.data[low];
  }
  L.data[low] = L.data[0];
  return low;
  }
  void Qsort(SqList &L, int low, int high) {
  if (low<high){
  int pivoloc = Partition(L, low, high);
  Qsort(L, low, pivoloc - 1);
  Qsort(L, pivoloc + 1, high);
  }
  }
  void QuickSort(SqList &L) {
  Qsort(L, 1, L.length);
  }

三、选择类排序

参考:ata.biancheng.net/view/72.html

✅ 简单选择排序

/\*\*
- @param {number[]} nums
- @return {number[]}
  \*/
  var sortArray = function(nums) {
  for (let i = 0; i<nums.length-1; i++) {
  for (let j = i+1; j<nums.length; j++) {
  if (nums[i] > nums[j]) {
  let temp = nums[i]
  nums[i] = nums[j]
  nums[j] = temp
  }
  }
  }
  return nums
  };

树形选择排序


堆排序

四、归并排序

2-路归并排序

给定一个序列,从左往右两两子序列进行归并


子序列归并的算法:加入有两个靠着的 a、b 序列,由上面可知,a、b 各自都是有序序列,现在就是将这两个合并为一个有序序列 k,将 a 和 b 序列的各个元素进行比较,小的依次放入 k 序列,当 a、b 两个中有一个序列为空了,就将那个不为空的序列直接加入到 k 序列即可,最后 k 序列就是目的序列。



五、分配类排序

基数排序

TODO: 扑克牌的花色排序

六、外部排序

基本方法

多路平衡归并

基本思想是内部排序中的 2-路归并排序

置换-选择排序

最佳归并树

参考

文章的动画演示

评论区

Twikoo giscus