排序 #
概念
稳定 不稳定
时间开销
- 关键字比较次数KCN
- 记录交换次数RSN
一般按照平均情况进行大略估算。
- 对于那些受对象初始排列&对象个数影响较大的，需要按最好情况和最坏情况估算。
算法执行时所需的附加存储：
评价算法好坏的另一标准
静态排序 #
物理重排
动态排序 #
链接指针 逻辑结构先后更改
内部排序 #
全部在内存中完成
外部排序 #
整个排序过程不可能只在内存中完成
- IO访问对时间的影响
基础排序 #
选择 冒泡 插入
希尔排序 #
对序列预处理，使得序列尽可能接近正序，再调用插入排序算法？
分为若干（d组）子序列，对每个子序列进行插入排序，多趟完成整个排序
缩小增量排序
不稳定, 无附加存储
Shell: d=n/2 d=d/2
Knuth: d=n/3+1 d=d/3+1
Knuth: n super 大时，KSN RSN n^1.25 , 1.6n^1.25
归并排序 #
merge #
将两个（及以上）有序子序列“归并”为一个有序序列。两路/多路归并。
template <typename E, typename Comp>
void mergesort(E A[], E temp[], int left, int right) {
if (left == right) return; // List of one element
int mid = (left+right)/2;
mergesort<E,Comp>(A, temp, left, mid);
mergesort<E,Comp>(A, temp, mid+1, right);
// 两路合并
for (int i=left; i<=right; i++) // Copy subarray to temp
temp[i] = A[i];
// Do the merge operation back to A
int i1 = left; int i2 = mid + 1;
for (int curr=left; curr<=right; curr++) {
if (i1 == mid+1) // Left sublist exhausted
A[curr] = temp[i2++];
else if (i2 > right) // Right sublist exhausted
A[curr] = temp[i1++];
else if (Comp::prior(temp[i1], temp[i2]))
A[curr] = temp[i1++];
else A[curr] = temp[i2++];
}
}
- 原始序列A分为子序列A[0~N/2-1] A[N/2~N-1]
- 两边归并排序
- 合并
- $$O(nlog_2n)$$
-
附加空间
-
稳定的
优化1
- 临时数组两边向中间走 不会出现子序列耗尽情况
- 1234|9876
优化2
- 初始插入排序 + 2路归并 一趟一次
- 数据量较小时better
堆排序 #
利用堆的特性
建大堆->重复removeFirst直到堆空
template <typename E, typename Comp>
void heapsort(E A[], int n) { // Heapsort
E maxval;
heap<E,Comp> H(A, n, n); // Build the heap
for (int i=0; i<n; i++) // Now sort
maxval = H.removefirst(); // Place maxval at end
}
- $$O(nlog_2n)$$
- 不稳定
- 不需要附加存储
- 找K个最大元素$$O(n+klogn)$$
快速排序 #
目标：找一个记录，以它的关键字作为枢轴
行为：凡key小于枢轴的记录均移动至该记录之前，反之，移至它之后
结果：处理之后，无序的记录序列R[s…t]以R[i]为界分割成两部分
$$R[s..i-1]\leq R[i] \leq R[i+1..t]$$template <typename E, typename Comp>
void qsort(E A[], int i, int j) { // Quicksort
if (j <= i) return; // Don’t sort 0 or 1 element
int pivotindex = findpivot(A, i, j);
swap(A, pivotindex, j); // Put pivot at end
// k will be the first position in the right subarray
int k = partition<E,Comp>(A, i-1, j, A[j]);
swap(A, k, j); // Put pivot in place
qsort<E,Comp>(A, i, k-1);
qsort<E,Comp>(A, k+1, j);
}
// 划分
template <typename E, typename Comp>
inline int partition(E A[], int l, int r, E& pivot) {
do { // Move the bounds inward until they meet
while (Comp::prior(A[++l], pivot)); // Move l right and
while ((l < r) && Comp::prior(pivot, A[--r])); // r left
swap(A, l, r); // Swap out-of-place values
} while (l < r); // Stop when they cross
return l; // Return first position in right partition
}
e.g. 一次划分
1 7 2 6 5 3 4
1 7 2 4 5 3 6
1 3 2 4 5 7 6
快速排序 继续对左右划分
1 2 3 | 4 | 5 6 7
- 最理想 左右侧子序列长度相等
- $$O(nlog_2n)$$
- 平均也是$$O(nlog_2n)$$
- 就平均计算时间而言，n很大时，快排是我们所讨论算法中最好的
- 最坏情况
- 排序序列已经有序，总比较次数将达到$$n^2/2$$，退化到简单排序，比直接排序还慢
- 不需要附加存储
- 不稳定
优化1 pivot
- 选择基准对象使得每次划分所得子序列对象个数尽可能接近
- 难以做到
- 其它思路 选择中间元素，选择最左边元素
- 简单实用 取每个待排序列第一个对象、最后一个对象、位置接近正中的3个选项中大小居中者
优化2
- 小规模全用插入排序
分配（桶）排序 基数排序 #
bin #
排序记录关键字在A[n]，结果在B[n]
-
迭代进行B[A[i]]=A[i]
- 关键字取值不能重复
- 最大取值<=待排序数组尺寸-1
- 关键字为非负整数
- $$O(n)$$
-
加强版
- 确定最大取值Max
- 定义数组LList
B[Max+1] - 关键字为K的记录放在链表B[K]中
- 从B[0]开始，顺序访问每个Bin的每个记录，放入A[]中
- $$O(n+max(Max,n))$$
-
需要额外空间
-
稳定的
基数排序 #
- 按位排序
- 确定最大取值Max和位数k
- 从低位到高位，进行k趟，第i趟根据第i位对上一趟结果binsort，原始序列记作0趟结果
- $$O(kn)$$
- $$O(nlog_rn)$$大
- $$O(n)$$小
- 额外空间
- 链表：nE + (n + r)P
- 数组：(n + r) * E
template <typename E, typename getKey>
void radix(E A[], E B[],
int n, int k, int r, int cnt[]) {
// cnt[i] stores number of records in bin[i]
int j;
for (int i=0, rtoi=1; i<k; i++, rtoi*=r) { // For k digits
for (j=0; j<r; j++) cnt[j] = 0; // Initialize cnt
// Count the number of records for each bin on this pass
for (j=0; j<n; j++) cnt[(getKey::key(A[j])/rtoi)%r]++;
// Index B: cnt[j] will be index for last slot of bin j.
for (j=1; j<r; j++) cnt[j] = cnt[j-1] + cnt[j];
// Put records into bins, work from bottom of each bin.
// Since bins fill from bottom, j counts downwards
for (j=n-1; j>=0; j--)
B[--cnt[(getKey::key(A[j])/rtoi)%r]] = A[j];
for (j=0; j<n; j++) A[j] = B[j]; // Copy B back to A
}
}
小总结 #
快排yyds