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

排序问题的算法：

输入：一个n 个数的序列 $(a_1, a_2, ... , a_n)$ 。
输出：输入序列的一个排列（重排） $\left<a'_1, a'_2, ... , a'_n\right>$ ，使得 $a'_1 \le a'_2 \le ... \le a'_n$ 。

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

数据的结构

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

排序算法

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

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

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

第六章堆排序

6.1 堆

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

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

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

MAX-HEAPIFY ：

维护堆，对于传入的元素调整堆，将该元素调整为满足最大对要求
运行时间为 $T(n) \le T(2n/3)+\Theta(1)$ ，即其时间复杂度为 $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/2 … 1]$
具有线性时间复杂度 $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.length … 2]$
其时间复杂度为 $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]$ 进行快速排序的三步分治过程：

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 个元素时，发生了快速排序的最坏情况，此时算法复杂度为 $\Theta(n^2)$ 。

最好情况划分

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

平衡的划分

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

7.3 快速排序的随机化版本

采用一种称为随机抽样(random sampling) 的随机化技术，使得算法实现随机化。将 $A[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)$ 。

8.1 排序算法的下界

决策树模型

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

最坏情况的下界

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

8.2 计数排序

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

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

假设输入是一个数组 $A[1... n]$ , A.length = 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 位是最高位，时间复杂度为 $\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]$ 满足 $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, $1 \le i \le n$ 。
输出：元素 $x\in A$ , 且 A 中恰好有 $i-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)$ 。它返回数组 $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);
    }
}

目录CONTENT

2、排序和顺序统计量

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

第六章堆排序

6.1 堆

6.2 优先队列

第七章快速排序

7.1 快速排序的描述

7.2 快速排序的性能

7.3 快速排序的随机化版本

第八章线性时间排序

8.1 排序算法的下界

8.2 计数排序

8.3 基数排序

8.4 桶排序

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

9.1 最小值和最大值

9.2 线性时间的选择算法

评论区

2、排序和顺序统计量

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

第六章 堆排序

6.1 堆

6.2 优先队列

第七章 快速排序

7.1 快速排序的描述

7.2 快速排序的性能

7.3 快速排序的随机化版本

第八章 线性时间排序

8.1 排序算法的下界

8.2 计数排序

8.3 基数排序

8.4 桶排序

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

9.1 最小值和最大值

9.2 线性时间的选择算法

评论区

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

第六章堆排序

第七章快速排序

第八章线性时间排序

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