尼采般地抒情

尼采般地抒情

尼采般地抒情

音乐盒

站点信息

文章总数目: 313
已运行时间: 1541


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

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


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


一、插入类排序

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

直接插入

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

数据结构选用的时顺序表

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]);
    }
}

二、交换类排序

冒泡排序

function sortArray(nums: number[]): number[] {
  for (let i = 0; i < nums.length - 1; i++) {
    for (let j = 0; j < nums.length - 1 - i; j++) {
      if (nums[j] > nums[j + 1]) {
        const temp = nums[j]
        nums[j] = nums[j + 1]
        nums[j + 1] = temp
      }

}

}
return nums
};

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
};

快速排序

function sortArray(nums: number[]): number[] {
  const rec = (arr: number[]) => {
    if (arr.length <= 1) return arr
    const left = []
    const mid = arr[0]
    const right = []
    for (let i = 1; i < arr.length; i++)
      (arr[i] < mid ? left : right).push(arr[i])
    return [...rec(left), mid, ...rec(right)]
  }
  return rec(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);
}

三、选择类排序

简单选择排序

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]) {
        const temp = nums[j]
        nums[j] = nums[i]
        nums[i] = temp
      }
    }
  }
  return nums
};

树形选择排序


堆排序

四、归并排序

直接归并

var sortArray = function (nums) {
  const rec = (arr) => {
    if (arr.length === 1) return arr
    const mid = Math.floor(arr.length / 2)
    const left = arr.slice(0, mid)
    const right = arr.slice(mid, mid.length)
    const orderLeft = rec(left)
    const orderRight = rec(right)
    const res = []
    while (orderLeft.length || orderRight.length) {
      if (orderLeft.length && orderRight.length) {
        res.push(orderLeft[0] > orderRight[0] ? orderRight.shift() : orderLeft.shift())
      } else if (orderLeft.length) {
        res.push(orderLeft.shift())
      } else if (orderRight.length) {
        res.push(orderRight.shift())
      }
    }
    return res
  }
  return rec(nums)
};

2-路归并排序

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


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



五、分配类排序

基数排序

TODO: 扑克牌的花色排序

TODO: 六、外部排序

基本方法

多路平衡归并

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

置换-选择排序

最佳归并树

评论区