侧边栏壁纸
  • 累计撰写 57 篇文章
  • 累计创建 10 个标签
  • 累计收到 2 条评论

目 录CONTENT

文章目录

2、排序和顺序统计量

yilee
2023-04-04 / 0 评论 / 0 点赞 / 49 阅读 / 0 字 / 正在检测是否收录...
温馨提示:
本文最后更新于2024-05-31,若内容或图片失效,请留言反馈。 部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

第二部分 排序和顺序统计量

排序问题的算法:

​ 输入:一个n 个数的序列 (a1,a2,...,an)(a_1, a_2, ... , a_n)
​ 输出:输入序列的一个排列(重排)<a1,a2,...,an>\left<a'_1, a'_2, ... , a'_n\right>,使得 a1a2...ana'_1 \le a'_2 \le ... \le a'_n

输入序列通常是一个n 元数组,尽管它可以用链表等其他方式描述。

数据的结构

​ 待排序的数通常是称为记录(record) 的数据集的一部分。每个记录包含一个关键字(key) ,就是排序问
题中要重排的值。记录的剩余部分由卫星数据(satellite data) 组成,通常与关键字是一同存取的。

排序算法

​ 插入排序、归并排序、堆排序及快速排序都是比较排序算法:它们都是通过对元素进行比较操作来确定输入数组的有序次序。决策树模型,可以证明任意比较排序算法排序n 个元素的最坏情况运行时间的下界为O(nlgn), 即堆排序和归并排序是渐近最优的比较排序算法。

​ 如果通过比较操作之外的方法来获得输入序列有序次序的信息,就有可能打破 O(nlgn)O(nlgn) 的下界。计数排序、基数排序、桶排序的时间复杂度时间复杂度均为 O(n)O(n)

​ 下表总结了一些排序算法的运行时间,其中n 表示要排序的数据项数量。对于计数排序,数据项均在集合 {0,1,...,k}\{0,1,...,k\} 内。对于基数排序,每个数据项都是d 位数字的整数,每位数字可能取k 个值。对于桶排序,假定关键字是半开区间 [0,1)[0, 1) 内服从均匀分布的n 个实数。

image-20220928161343362

第六章 堆排序

6.1 堆

​ (二叉)堆是一个数组,它可以被看成一个近似的完全二叉树,树上的每一个结点对应数组中的一个元素。二叉堆可以分为两种形式:最大堆和最小堆。在这两种堆中,结点的值都要满足堆的性质。

​ 在最大堆中,最大堆性质是指除了根以外的所有结点i 都要满足:A[PARENT(i)]A[i]A[PARENT(i)] \ge A[i] ,即某个结点的值至多与其父结点一样大。堆中的最大元素存放在根结点中;并且,在任一子树中,该子树所包含的所有结点的值都不大千该子树根结点的值。

​ 最小堆的组织方国团式正好相反:最小堆性质是指除了根以外的所有结点 i 都有:A[PARENT(i)]A[i]A[PARENT(i)] \le A[i] ,最小堆中的最小元素存放在根结点中。

MAX-HEAPIFY

  • 维护堆,对于传入的元素调整堆,将该元素调整为满足最大对要求

  • 运行时间为 T(n)T(2n/3)+Θ(1)T(n) \le T(2n/3)+\Theta(1),即其时间复杂度为 O(lgn)O(lgn) , 它是维护最大堆性质的关键。

MAX-HEAPIFY(A, i)
  l = LEFT(i)
  r = RIGHT(i)
  if l <= A.heapSize and A[l] > A[i]
    largest = l
  else 
    largest = i
  if r <= A.heapSize and A[r] > A[largest]
    largest= r
  if target != i
    exchange A[i] with A[largest]
    MAX-HEAPIFY(A, largest)
public static void maxHeapify(int[] nums, int index, int length) {
    int tIndex = index;
    int left = 2 * index + 1, right = left + 1;

    if (index < 0)
        return;
    if (left < length && nums[left] > nums[tIndex]) {
        tIndex = left;
    }
    if (right < length && nums[right] > nums[tIndex]) {
        tIndex = right;
    }
    if (tIndex != index) {
        // 交换
        int temp = nums[index];
        nums[index] = nums[tIndex];
        nums[tIndex] = temp;
        // 下层继续交换
        maxHeapify(nums, tIndex, length);
    }
}

BUILD-MAX-HEAP

  • 用自底向上的方法利用过程 MAX-HEAPIFY 把一个长度为 n 的数组转化为最大堆。 [A.length/21][A.length/2 … 1]

  • 具有线性时间复杂度 O(n)O(n),功能是从无序的输入数据数组中构造一个最大堆。

BUILD-MAX-HEAP(A)
  A.heapSize = A.length
  for i = A.length/2 downto 1
    MAX-HEAPIFY(A, i)
public static void buildMaxHeap(int[] nums, int index, int length) {
    for (int i = nums.length / 2; i >= 0; i--) {
        maxHeapify(nums, i, length);
    }
}

合并前两个过程

public static void maxHeap(int[] nums, int index, int length) {
    int tIndex = index;
    int left = 2 * index + 1, right = left + 1;

    if (index < 0)
        return;
    if (left < length && nums[left] > nums[tIndex]) {
        tIndex = left;
    }
    if (right < length && nums[right] > nums[tIndex]) {
        tIndex = right;
    }
    if (tIndex != index) {
        // 交换
        int temp = nums[index];
        nums[index] = nums[tIndex];
        nums[tIndex] = temp;
        // 下层继续交换
        maxHeap(nums, tIndex, length);
    }

    // 遍历
    maxHeap(nums, index - 1, length);
}

HEAPSORT

  • 不断利用 BUILD-MAX- HEAP 将长度为 n 的数组转化为最大堆,并选出并去除最大值,重新对剩余的元素继续调佣该函数,完成排序。 [A.length2][A.length … 2]

  • 其时间复杂度为 O(nlgn)O(nlgn), 功能是对一个数组进行原址排序。

HEAPSORT(A)
  BUILD-MAX-HEAP(A)
  for i = A.length downto 2
  	exchange A[1] with A[i]
  A.heapSize = A.heapSize - 1
  MAX-HEAPIFY(A, 1)
// 最大堆实现元素从小到大排列
for (int i = nums.length; i > 1; i--) {
    maxHeap(nums, i / 2, i);
    int tmp = nums[i - 1];
    nums[i - 1] = nums[0];
    nums[0] = tmp;
}

6.2 优先队列

​ 优先队列(priority queue) 是一种用来维护由一组元素构成的集合S 的数据结构,其中的每一个元素都有一个相关的值,称为关键字(key) 。一个最大优先队列支待以下操作:

INSERT(S, x):

  • 把元素x 插入集合S 中。这一操作等价于S = S U { x } 。
INSERT(A, key)
  A.heapSize = A.heapSize + 1
  A[A.heapSize] = -oo
  INCREASE-KEY(A, A.heapSize, key)

MAXIMUM(S):

  • 返回S 中具有最大键字的元素。
MAXIMUM(A)
  return A[1]

EXTRACT-MAX(S):

  • 去掉并返回S 中的具有最大键字的元素。
EXTRACT-MAX(A)
  if A.heapSize < 1
    error "heap underflow"
  max= A[1]
  A[1] = A[A.heapSize]
  A.heapSize = A.heapSize - 1
  MAX-HEAPIFY(A, 1)
  return max

INCREASE-KEY(S, x, k):

  • 将元素x 的关键字值增加到k, 这里假设k 的值不小于x 的原关键字值。
INCREASE-KEY(A, i, key)
  if key < A[i]
    error "new key is smaller than current key"
  A[i] = key
  while i > 1 and A[PARENT(i)] < A[i]
    exchange A[i] with A[PARENT(i)]
    i = PARENT(i)
    // i = (i + 1) / 2 - 1

第七章 快速排序

7.1 快速排序的描述

对一个典型的子数组 A[p...r]A[p ... r] 进行快速排序的三步分治过程:

QUICKSORTCA, p, r)
  if p<r
  q = PARTITION(A, p, r)
  QUICKSORT(A, p, q-1)
  QUICKSORT(A, q+ 1, r)

PARTITION(A, p, r)
  x = A[r]
  i = p - 1
  for j=p to r-1
    if A[j] <= x
      i = i + 1
    	exchange A[i] with A[j]
  exchange A[i + 1] with A[r]
  return i + 1

Java 实现

public static void quickSort(int[] nums, int left, int right) {
    if (left < right) {
        int j = left;
        for (int i = left; i < right; i++) {
            if (nums[i] <= nums[right]) {
                int temp = nums[j];
                nums[j] = nums[i];
                nums[i] = temp;
                j++;
            }
        }

        int temp = nums[j];
        nums[j] = nums[right];
        nums[right] = temp;

        quickSort(nums, left, j - 1);
        quickSort(nums, j + 1, right);
    }
}

7.2 快速排序的性能

最坏情况划分

​ 当划分产生的两个子问题分别包含了 n-1 个元素和 0 个元素时,发生了快速排序的最坏情况,此时算法复杂度为 Θ(n2)\Theta(n^2)

最好情况划分

​ 当划分产生的两个子问题的规模都不超过 n/2\lfloor n/2 \rfloor时,发生了快速排序的最好情况,此时算法复杂度为 Θ(nlgn)\Theta(n lgn)

平衡的划分

​ 快速排序的平均运行时间更接近千其最好情况,而非最坏情况。

7.3 快速排序的随机化版本

​ 采用一种称为随机抽样(random sampling) 的随机化技术,使得算法实现随机化。将 A[r]A[r] 与从 A[p...r]A[p...r] 中随机选出的一个元素交换,在执行上述的快速排序数据。

RANDOMIZED-PARTITION (A, p, r)
 i = RANOOM(p, r)
 exchange A[r] with A[i]
 return PARTITION(A, p, r)

Java 实现

public static Random rand = new Random();
public static void quickSort(int[] nums, int left, int right) {
    if (left < right) {
        int tIndex = rand.nextInt(right - left + 1) + left;
        int temp = nums[right];
        nums[right] = nums[tIndex];
        nums[tIndex] = temp;

        int j = left;
        for (int i = left; i <= right; i++) {
            if (nums[i] <= nums[right]) {
                int temp = nums[j];
                nums[j] = nums[i];
                nums[i] = temp;
                j++;
            }
        }

        quickSort(nums, left, j - 2);
        quickSort(nums, j, right);
    }
}

第八章 线性时间排序

​ 在排序的最终结果中,各元素的次序依赖于它们之间的比较。我们把这类排序算法称为比较排序。任何比较排序在最坏情况下都要经过 O(nlgn)O(nlgn)

8.1 排序算法的下界

决策树模型

​ 比较排序可以被抽象为一棵决策树。决策树是一棵完全二叉树,它可以表示在给定输入规模情况下,某一特定排序算法对所有元素的比较操作。

image-20220927160735389

最坏情况的下界

​ 在最坏情况下,任何比较排序算法都需要做, Ω(nlgn)\Omega(nlgn) 次比较。

8.2 计数排序

​ 计数排序假设n 个输入元素中的每一个都是在0 到 k 区间内的一个整数,其中k 为某个整数。当 k=O(n)k=O(n) 时,排序的运行时间为 Θ(n)\Theta(n)

​ 计数排序的基本思想是:对每一个输入元素x, 确定小于x 的元素个数。利用这一信息,就可以直接把x 放到它在输出数组中的位置上了。

​ 假设输入是一个数组 A[1...n]A[1... n], A.length = n 。我们还需要两个数组: B[1...n]B[1... n] 存放排序的输出,$ C[0…k] $ 提供临时存储空间。

COUNTING-SORT(A, B, k)
  let C[0 .. k] be a new array
  for i= 0 to k
    C[i] = O
  for j = 1 to A.length
    C[A[j]]=C[A[j]]+ 1
  //C[i] now contains the number of elements equal to i.
  for i = 1 to k
    C[i]=C[i]+C[i-1]
  //C[i] now contains the number of elements less than or equal to i.
  for j = A.length downto 1
    B[C[A[j]]]=A[j]
    C[A[j]]=C[A[j]]-1

Java 实现

public static void countingSort(int[] nums) {
    int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
    for(int num : nums){
        min = Math.min(min, num);
        max = Math.max(max, num);
    }
    
    int len = max - min + 1;
    int[] count = new int[len];
    for (int num : nums) {
        count[num - min]++;
    }
    for (int i = 1; i < len; i++) {
        count[i] += count[i - 1];
    }

    int last = 0;
    for (int i = 0; i < len; i++) {
        while (last < count[i]) {
            nums[last] = i + min;
            last++;
        }
    }
}

8.3 基数排序

​ 基数排序(radix sort) 是一种用在卡片排序机上的算法,假设n 个d 位的元素存放在数组A中,其中第1 位是最低位,第d 位是最高位,时间复杂度为 Θ(n+k)\Theta(n+k)

RADIX-SORT(A, d)
 for i = 1 to d
   use a stable sort to sort array A on digit i

Java 实现

public static void radixSort(int[] nums) {
    int max = Arrays.stream(nums).max().getAsInt();

    int unit = 1, len = nums.length;
    while (max != 0) {
        int[][] count = new int[10][len + 1];
        for (int i = 0; i < len; i++) {
            int d = nums[i] / unit % 10;
            count[d][count[d][len - 1]++] = nums[i];
        }

        int k = 0;
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < count[i][len - 1]; j++) {
                nums[k++] = count[i][j];
            }
        }

        max /= 10;
        unit *= 10;
    }
}

8.4 桶排序

​ 桶排序(bucket sort) 假设输入数据服从均匀分布,平均情况下它的时间代价为 O(n) 。

​ 假设输入是一个包含n 个元素的数组A, 且每个元素 A[i]A[i] 满足 $0 \le A[i] \lt l $。需要一个临时数组 $B[0…n-1] $来存放链表(即桶),并假设存在一种用于维护这些链表的机制。

BUCKET-SORT(A)
  n = A.length
  let B[0.. n-1] be a new array
  for i = 0 to n-1
    make B[i] an empty list
  for i = 1 to n
    insert A[i] into list B[nA[i]]
  for i = 0 to n-1
    sort list B[i] with insertion sort
  concatenate the lists B[0], B[1], ... , B[n-1] together in order

Java 实现

public static void bucketSort(int[] nums) {
    int max = Arrays.stream(nums).max().getAsInt();
    int unit = 1, len = nums.length;
    while (max > 10) {
        max /= 10;
        unit *= 10;
    }

    int[][] count = new int[10][len + 1];
    for (int num : nums) {
        int d = num / unit % 10;
        int index = 0;
        while (count[d][index] != 0 && count[d][index] < num) {
            index++;
        }

        for (int i = count[d][len]; i > index; i--) {
            count[d][i] = count[d][i - 1];
        }

        count[d][index] = num;
        count[d][len]++;
    }

    int k = 0;
    for(int i = 0 ; i < 10; i++){
        for (int j = 0; j < count[i][len]; j++) {
            nums[k++] = count[i][j];
        }
    }
}

第九章 中位数和顺序统计量

选择问题:

  • 输入:一个包含n 个(互异的)数的集合A 和一个整数 i, 1in1 \le i \le n
  • 输出:元素 xAx\in A, 且 A 中恰好有 i1i-1 个其他元素小于它。

9.1 最小值和最大值

​ 依次遍历集合中的每个元素,并记录下当前最小元素。假设该集合元素存放在数组A 中,且 A.length = n:

MINIMUM(A)
  min= A[l]
  for i = 2 to A.length
    if min > A[i]
      min = A[i]
  return min

9.2 线性时间的选择算法

​ 以快速排序算法为模型,仍然将输入数组进行递归划分,但只处理划分的一边,算法是时间复杂度为 O(n)O(n)。它返回数组 A[p..r]A[p.. r] 中第 i 小的元素。

RANDOMIZED-SELECT (A, p, r, i)
  if p == r
    return A[p]
  q = RANDOMlZED-PARTITION(A, p, r)
  k = q - p + 1
  if i == k // the pivot value is the answer
    return A[q]
  else if i < k
    return RANOOMIZED-SELECT(A, p, q-1, i)
  else 
    return RANOOMIZED-SELECT(A, q+l, r, i-k)

java实现

public static Random rand = new Random();
public static int randomizedSelect(int[] nums, int left, int right, int index) {
    if (left == right) {
        return nums[left];
    }

    int tIndex = rand.nextInt(right - left + 1) + left;
    int temp = nums[right];
    nums[right] = nums[tIndex];
    nums[tIndex] = temp;

    int j = left;
    for (int i = left; i <= right; i++) {
        if (nums[i] <= nums[right]) {
            temp = nums[j];
            nums[j] = nums[i];
            nums[i] = temp;
            j++;
        }
    }

    if (j == left) {
        return nums[left];
    } else if (index < j) {
        return randomizedSelect(nums, left, j - 2, index);
    } else {
        return randomizedSelect(nums, j, right, index - j);
    }
}
0
  1. 支付宝打赏

    qrcode alipay
  2. 微信打赏

    qrcode weixin

评论区