计算各元素在 a[0:n-1] 中的 名次, 最小的元素名次为 0, 最大的为 n-1. 再将 名次 作为 下标 ( index ) 存放进新数组.
1.2. 节中我们借助空间 (利用一个新的数组) 实现名次排序; 而 1.3. 节不借助空间实现名次排序, 称之为原地重拍.
1.1. 名次 ( rank ) 计算
在 名次排序 之前先要计算一个序列中所有元素的 名次.
一个元素在一个序列中的 名次 是 所有比它小的元素个数 加上 在它左边出现的与它相同的元素个数.
e.g. 数组 a=[4,3,9,3,7] 是一个序列, 其名次为 r=[2,0,4,1,3].
实际上, 一个元素的 名次 就是该元素在排序完成后的数组中的下标.
以下代码实现 名次 计算:
template
void rank(const T a[], int n, int r[]) {
// Initialize r[0:size-1].
for (int i = 0; i < n; i++)
r[i] = 0;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (a[j]
对于每个 i, 比较次数为 i. 因此总 比较次数为:
[1+2+3+…+(n-1)=\frac{n(n-1)}{2} ]
1.2. 借助空间实现名次排序
创建一个新数组 u[0:n-1], 把 a[] 中元素按照 名次 存入 u[].
template
void rearrange(T a[], int n, int r[])
{
rank(a, size, r); // Store the ranks of "a[]"'s elements in "r[]".
T* u = new T[n];
for(int i = 0; i < n; i++)
u[r[i]] = a[i];
for (i = 0; i < n; i++)
a[i] = u[i];
delete[] u;
}
由于排序本身没有执行比较, 因此总比较次数为名次计算的 比较次数, 即:
[\frac{n(n-1)}{2} ]
而元素 移动 的步数为:
[2n ]
1.3. 原地重排
直接举个例子:
template
void inPlaceRearrange(T a[], int n, int r[])
{
rank(a, n, r); // Store the ranks of "a[]"'s elements in "r[]".
for (int i = 0; i < n; i++) {
while (r[i] != i) {
int t = r[i];
std::swap(a[i], a[t]);
std::swap(r[i], r[t]);
}
}
}
最好的情况下, 总 交换次数为 (0).
最坏的情况下, 需要进行 n-1 次交换才能使所有元素完成重排, 再加上同时进行的名次交换, 总 交换次数为 (2(n-1)).
原地重排 在 较差情况 移动步数 (每次交换有 3 次移动) 会大于 名次排序, 但 原地重排 总是能节省 空间.
对 a[0:n-1] 的选择排序可以看作寻找了 n-1 次 最大元素的下标, 每次找到后把 最大元素 移动到末尾.
第 1 次: 在 a[0:n-1] 中找出 最大元素, 把它的值和 a[n-1] 的值交换;
第 2 次: 在 a[0:n-2] 中找出 最大元素, 把它的值和 a[n-2] 的值交换;
……
第 n-1 次: 在 a[0:1] 中找出 最大元素, 把它的值和 a[1] 的值交换.
2.1. 找出 a[0:n-1] 的最大元素下标
template
int indexOfMax(T a[], int n) {
int indexOfMax = 0;
for(int i = 1; i < n; i++){
if (a[indexOfMax] < a[i])
indexOfMax = i;
}
return indexOfMax;
}
总 比较次数为 (n-1).
2.2. 实现简单的选择排序
template
void selectionSort(T a[], int n) {
for(int size = n; size > 1; size--){
int j = indexOfMax(a, size);
std::swap(a[j], a[size-1]);
}
}
由于调用 indexOfMax(a, i) 要执行 (i-1) 次比较, 因此总 比较次数为:
[(n-1)+(n-2)+…+1=\frac{n(n-1)}{2} ]
2.3. 及时终止的选择排序
在将最大元素与末尾元素互换时, 同时检查先前元素是否已经有序.
如果 indexOfMax 始终从 0 开始依照迭代器递增而递增, 那说明 a[0:i-1] 是有序的, 则及时终止.
template
void stopSelectionSort(T a[], int n)
{
bool sorted = false; // Assume that "a[0:n-1]" is unsorted at first.
// Loop_1 If:
// & "a[0:size-1]" is unsorted
// & the iterator is in range
// To:
// & sort the array
for (int size = n; !sorted && (size > 1); size--) {
int indexOfMax = 0;
sorted = true;
// Loop_2 To:
// & get the index of the largest element in "a[0:size-1]"
// & checks whether "a[0:size-1]" is sorted.
for (int i = 1; i < size; i++) {
if (a[indexOfMax]
最好情况是: 当初始数组 “a[0:n-1]” 有序, Loop_2 在比较了 (n-1) 次后就将 sorted 赋值为 true, 因此总比较次数为 (n-1).
最坏情况是: sorted 始终为 false, 则需要比较 (\sum_{i=1}^{n-1}{n-i}=n(n-1)/2) 次.
但是额外的步骤被用来维护变量 sorted.
对 a[0:n-1] 的冒泡排序可以看成执行了 n-1 次冒泡过程.
第 1 次: 将 a[0:n-1] 内最大的元素移动到 a[n-1];
第 2 次: 将 a[0:n-2] 内最大的元素移动到 a[n-2];
……
第 n-1 次: 将 a[0:1] 内最大的元素移动到 a[1];
最后剩下最小的 a[0].
3.1. 一次冒泡过程
遍历 a[0:n-1]; 如果 a[i] 大于 a[i+1] 则交换它们的值, 使每次循环到末尾时 i 指向的元素小于 i+1 指向的.
template
void bubble(T a[], int n) {
for(int i = 0; i < n-1; i++) {
if (a[i] > a[i+1])
std::swap(a[i], a[i+1]);
}
}
总 比较次数为:
[n-1 ]
3.2. 实现冒泡排序
template
void bubbleSort(T a[], int n) {
for(int i = n; i > 1; i--)
bubble(a, i);
}
由于调用一次 bubble(a, i) 要执行 (i-1) 次比较, 所以总 比较次数为:
[(n-1)+(n-2)+…+1=\frac{n(n-1)}{2} ]
在 有序数组 ( sorted array ) a[0:n-1] 中插入一个元素
目前数组 a[0:n-1] 中有 n 个元素. 因为要插入一个元素, 我们需要假设数组 a[] 的容量大于 n.
template
void insert(T a[], int& n, const T& x){
// Suppose the capacity of "a[]" is bigger than "n".
for(int i = n - 1; i >= 0 && x < a[i]; i--)
a[i+1] = a[i]; // Move the elements which are bigger than "x" to the right.
a[i+1] = x;
n++;
}
3.3. 及时终止的冒泡排序
通过在 a[0:i-1] 的冒泡过程中添加一个 bool 类型变量 swapped, 我们可以知道该次冒泡过程中 是否有 交换的步骤.
如果没有交换的步骤, 那么说明 a[0:i-1] 是 有序的, 则及时终止冒泡排序.
template
bool stopBubble(T a[], int n)
{
bool swapped = false;
for (int i = 0; i < n - 1; i++) {
if (a[i] > a[i + 1]) {
std::swap(a[i], a[i + 1]);
swapped = true;
}
}
return swapped;
}
template
void stopBubbleSort(T a[], int n)
{
// Loop_1 If:
// & swap happened in stopBubble(a,i)
for (int i = n; i > 1 && stopBubble(a, i); i--);
}
最坏情况下, 与原来的冒泡排序相同, 依旧需要 比较 (n(n-1)/2) 次;
而在最好情况下, 只需 比较 (n-1) 次.
但是额外的步骤被用来维护变量 swapped.
从 i = 1 开始, 将 a[i] 插入 a[0:i-1] 中, 确保插入完后 a[0:i] 是有序的.
template
void insertionSort(T a[], int n)
{
// Loop_1 To:
// Iterate from "a[1]" to "a[n-1]".
for (int i = 1; i < n; i++) {
T t = a[i]; // Insert "a[i]" to "a[0:i-1]".
// Loop_2 If:
// "a[j]" is larger than "a[i]=t"
for (int j = i - 1; j >= 0 && a[j] > t; j--) {
a[j + 1] = a[j];
}
a[j + 1] = t;
}
}
最好情况 比较 (n-1) 次;
最坏情况 比较 (n(n-1)/2) 次.
Original: https://www.cnblogs.com/jamesnulliu/p/dsaaincpp-sort.html
Author: JamesNULLiu
Title: 排序算法
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/605009/
转载文章受原作者版权保护。转载请注明原作者出处！