1. 每一单趟都能确定一个数字的最终位置的排序
答案: C.
解析:
这个题目选啥呢?
我们挨个选项进行分析.
①: 选择排序, 选择排序每次选一个最值放在一端, 也可以选两个/多个最值… 因此是满足条件的.
②: 归并排序, 归并排序是逐步分割, 分割完之后回归的时候才开始合并的, 而且每次合并的结果并不是最终结果, 因此归并排序不满足条件.
③: 快速排序, 快排每次都选一个关键字, 使得关键字左边比key小, 右边比key小…因此快排是满足条件的.
④: 堆排, 每次堆排都是首尾交换, size–, 因此最后一个数是确定位置的, 因此说堆排也是满足条件的.
综上, 答案是①, ③, ④.
2. 根据序列变化确定排序方式
答案: D.
解析:
这个挨个根据排序特性去试一下就好了. 直接看快排.
变化过程如下:
3. 排序顺序对哪些排序效率影响不大?
答案：B
解析：
快排： 初始顺序影响较大，有序时，性能最差. n*logn -> n^2
插入: 接近有序，性能最好.
希尔：希尔是对插入排序的优化，这种优化是在无序的序列中才有明显的效果，如果序列接近有序，反而是插入最优。
堆排，归并，选择对初始顺序不敏感
4. 对有序序列排序最费力的排序方式是什么?
答案: D
解析: 快排选key, 然后递归很吃亏.
5. 对接近有序序列排序最快的排序方式是什么?
答案: A
解析: 前面提到过, 归并和堆排以及选择排序对排序效率影响不大. 直接插入排序是对接近有序序列效率最高的了, 希尔排序的话是借用了直接插入排序对接近有序序列排序很高的效率这一想法, 弄了"预排", 希尔排序的作用就是原先直接插入排序对接近有序的序列效率很好, 希尔加入了预排之后, 扩大了插入排序的使用范围, 使的插入排序即使面对不太有序的序列也可以从容应对.
6. 最好时间复杂度 与 最坏时间复杂度差异最大的是?
答: A.
解析: 快排算是一种非常不稳定的排序. 在大部分情况下都比较快, 效率接近n*logn, 但是在特殊情况下, 效率会达到N^2的一个情况. 比如说对有序序列进行排序.
7. 各个排序方式的最坏时间复杂度是多少?
答案: A.
解析:
堆排算是一种效率比较稳定的排序, 最好时间复杂度是O(N), 最差时间复杂度是O(NlogN).
快排是一种非常不稳定的排序, 一般情况下效率是O(NlogN), 但是特殊情况下效率是O(NN).
选择排序是一种特别稳定的排序, 稳定到永远是O(NN)的时间复杂度.
插入排序是一种对数据适应性特别强的排序方式, 如果数据接近有序, 那么效率很高, 如果数据直接逆序, 那么时间复杂度是O(N*N).
8. 最占空间的排序方式?
答案: A.
解析: 归并在合并的时候, 不是直接在原数据上操作的, 而是申请一块新空间, 在新空间上合并完了再拷贝回去.
为啥不直接再原数组上操作? ①因为不好操作(代码不好写). ②很难控制归并排序的稳定性问题.
9. 各排序方式的时间复杂度
答案: D.
10. 不稳定的排序算法?
答案: C.
解析:
首先要理解我们说的排序算法什么是稳定的?
所谓稳定, 就是排序前和排序后尽量使得各个元素前后的相对位置不变.
我们知道, 快排是出了名的不稳定, 包括效率和相对位置. 除此之外, 其他排序稳定性如下:
- 直接插入一般可以从前向后进行元素的插入，相同元素的相对位置可以不发生变化。
- 归并也可以保证相对位置不变。
- 冒泡排序在元素相同的情况下也可以不进行交互，也可以保证稳定。
- 选择排序的思想是每次选出最值，放在已排序序列的末尾，如果最值有多个，而选出的为最后一个最值，会导致相对位置发生变化。
当然选择排序也可以变成稳定的，只要保证相同的值选择第一个就可以。
11. 快排的特性
答案：C
解析：
快排的非递归是在模拟递归的过程，所以时间复杂度并没有本质的变化，但是没有递归，可以减少栈空间的开销。栈和队列都可以实现。这个地方用队列实现快排也可以, 因为队列跟栈的区别就是出入顺序的不同, 对于快排来说, 先后都可以.
12. 三数取中对快排影响的理解
答案: D.
解析: 见上图.
13. 快排的空间复杂度
答案: C.
解析: 这里的额外空间大小并不是一个准确的空间值, 这里说的是空间复杂度. 也就是要重点去看思想.
如果是递归算法，所递归的深度大概为二叉树的深度，即logn
如果是非递归算法，需要模拟递归的过程，即需要保存子区间的索引，每次都会成对的保存，最多保存的索引也和二叉树的高度有关：2 * logn
所以空间复杂度为logn
14. 快排过程
答案: C.
解析: 见上图.
15. 快排的过程
答案: B
解析:
16. 实现一下选择排序
// 选择排序
void SelectSort(int* a, int n);
答案:
void SelectSort(int* a, int n)
{
int begin = 0;
int end = n - 1;
// 2.多趟控制
while (begin <= end)
{
// 1.先控制单趟
int maxi = begin;
int mini = begin;
for (int j = begin; j <= end; j++)
{
if (a[maxi] < a[j]) maxi = j;
if (a[mini] > a[j]) mini = j;
}
swap(a[begin], a[mini]);
if (maxi == begin) maxi = mini; //更新特殊情况
swap(a[end], a[maxi]);
begin++, end--;
//PrintArray(a, 12);
}
}
17. 实现一下堆排序
// 堆排序
void AdjustDwon(int* a, int n, int root);
void HeapSort(int* a, int n);
答案:
// 假设要升序, 那我们就建立大堆.
void AdjustDwon(int* a, int n, int root)
{
int child = 2 * root + 1; //默认是左孩子
while (child <= n - 1)
{
if (child + 1 <= n - 1 && a[child + 1] > a[child])
{
child += 1;
}
if (a[child] > a[root])
{
swap(a[child], a[root]);
root = child;
child = 2 * root + 1;
}
else break;
}
}
// 假设要升序, 那我们就建立大堆.
void HeapSort(int* a, int n)
{
// 1.建堆
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDwon(a, n, i);
}
// 2.首尾交换
int end = n - 1;
while (end)
{
swap(a[0], a[end]);
AdjustDwon(a, end, 0);
end--;
PrintArray(a, 12);
}
}
18. 简单实现一下冒泡排序
// 冒泡排序
void BubbleSort(int* a, int n);
答案:
void BubbleSort(int* a, int n)
{
// 控制多趟, 冒多少次?
for (int i = 0; i < n - 1; i++)
{
int f = false;
// 单趟控制
for (int j = 0; j < n - i - 1; j++)
{
if (a[j] > a[j + 1])
{
swap(a[j], a[j + 1]);
f = true;
}
}
if (!f) break;
}
}
19. 实现一下快排
// 快速排序递归实现
// 快速排序hoare版本
int PartSort1(int* a, int left, int right);
// 快速排序挖坑法
int PartSort2(int* a, int left, int right);
// 快速排序前后指针法
int PartSort3(int* a, int left, int right);
void QuickSort(int* a, int left, int right);
// 快速排序 非递归实现
void QuickSortNonR(int* a, int left, int right);
答案:
// 快速排序递归实现
// 三数取中
static int getMid(int* arr, int begin, int end)
{
int midi = (begin + end) / 2;
//找一个较大的值
if (arr[begin] < arr[end]) // begin < end
{
if (arr[midi] < arr[begin]) return begin;
else if (arr[midi] > arr[end]) return end;
else return midi;
}
else // end < begin
{
if (arr[midi] < arr[end]) return end;
else if (arr[midi] > arr[begin]) return begin;
else return midi;
}
}
// 快速排序hoare版本
int PartSort1(int* a, int left, int right)
{
int l = left;
int r = right;
int keyi = getMid(a, left, right);
swap(a[keyi], a[left]);
keyi = left;
while (l < r)
{
while (l < r && a[r] >= a[keyi])
{
r--;
}
while (l < r && a[l] <= a[keyi])
{
l++;
}
swap(a[r], a[l]);
}
swap(a[r], a[keyi]);
keyi = r;
return keyi;
}
// 快速排序挖坑法
int PartSort2(int* a, int left, int right)
{
int holei = getMid(a, left, right);
swap(a[holei], a[left]);
holei = left;
int r = right;
int l = left;
int hole = a[holei];
while (l < r)
{
while (l < r && a[r] >= hole) r--;
swap(a[holei], a[r]);
holei = r;
while (l < r && a[l] <= hole) l++;
swap(a[holei], a[l]);
holei = l;
}
a[holei] = hole;
return holei;
}
// 快速排序前后指针法
int PartSort3(int* a, int left, int right)
{
int keyi = getMid(a, left, right);
swap(a[keyi], a[left]);
keyi = left;
int prev = left;
int pcur = left + 1;
while (pcur <= right)
{
if (a[pcur] < a[keyi]) swap(a[pcur], a[++prev]);
pcur++;
}
swap(a[prev], a[keyi]);
keyi = prev;
return keyi;
}
void QuickSort(int* a, int left, int right)
{
if (right - left + 1 <= 1) return;
//int keyi = PartSort1(a, left, right);
//int keyi = PartSort2(a, left, right);
int keyi = PartSort3(a, left, right);
PrintArray(a, 12);
QuickSort(a, left, keyi - 1);
QuickSort(a, keyi + 1, right);
}
// 快速排序 非递归实现
void QuickSortNonR(int* a, int left, int right)
{
stack<pair<int, int>> st;
st.push({ left, right });
// [begin, keyi-1] keyi [keyi+1, end]
while (!st.empty())
{
pair<int, int> t = st.top();
st.pop();
//int keyi = PartSort1(a, t.first, t.second);
//int keyi = PartSort2(a, t.first, t.second);
int keyi = PartSort3(a, t.first, t.second);
if (((keyi - 1) - t.first) + 1 > 1) st.push({ t.first, keyi - 1 });
if ((t.second - (keyi + 1)) + 1 > 1) st.push({ keyi + 1, t.second });
}
}
20. 实现一下直接插入排序
static void InsertSort(int* arr, int n)
{
// 2.再写整体
for (int i = 0; i < n - 1; i++)
{
// 1.先写单趟排序 [0, end] end+1
int end_i = i;
int t_i = end_i + 1;
while (end_i >= 0)
{
// 如果arr[t_i] < arr[end_i], 两者交换
if (arr[t_i] < arr[end_i])
{
swap(arr[t_i], arr[end_i]);
end_i--;
t_i--;
}
// 如果arr[t_i] >= arr[end_i], 直接跳出循环即可.
else
{
break;
}
}
PrintArray(arr, n);
}
}
21. 简单实现以下希尔排序
static void ShellSort(int* arr, int n)
{
// 1.预排
int gap = n;
while (gap >= 1)
{
// 2.gap == x的情况下, 控制多组直接插入排序
for (int i = 0; i < gap; i++)
{
// 3.具体到每一组的一个直接插入排序
for (int j = 0 + i; j < n - gap; j+=gap)
{
int end_i = j;
int t_i = end_i + gap;
// 4. 具体的一个数插入到数组中去
while (end_i >= 0)
{
// 如果arr[end_i] <= arr[t_i]
if (arr[end_i] <= arr[t_i])
break;
else
{
swap(arr[end_i], arr[t_i]);
t_i -= gap;
end_i -= gap;
}
}
}
}
printf("gap == %d: ", gap);
gap /= 2;
PrintArray(arr, n);
}
}
22. 简单实现归并排序
static void MergeSort(int* arr, int begin, int end)
{
vector<int> v(end - begin + 1);
_MergeSort(arr, begin, end, v);
}
static void _MergeSort(int* arr, int begin, int end, vector<int>& v)
{
if (begin >= end) return;
int midi = (begin + end) / 2;
// 递归
// [begin, midi] [midi+1, end]
_MergeSort(arr, begin, midi, v);
_MergeSort(arr, midi + 1, end, v);
// 合并
int begin1 = begin, end1 = midi;
int begin2 = midi + 1, end2 = end;
int i = begin;
while (begin1 <= end1 && begin2 <= end2)
{
if (arr[begin1] < arr[begin2]) v[i++] = arr[begin1++];
else v[i++] = arr[begin2++];
}
while (begin1 <= end1) v[i++] = arr[begin1++];
while (begin2 <= end2) v[i++] = arr[begin2++];
// 拷贝赋值
for (int i = begin; i <= end; i++)
{
arr[i] = v[i];
}
}
static void MergeSortNonR(int* a, int n)
{
// 1. 开一块空间, 用来合并
vector<int> v(n+1);
int gap = 1; //每组多少个元素
while (gap < n)
{
// 控制所有组的起点
for (int i = 0; i < n; i += 2 * gap)
{
int begin1 = i, end1 = i + gap - 1;
int begin2 = i + gap, end2 = i + 2 * gap - 1;
// [begin1, end1][begin2, end2] 归并
// 边界的处理
if (end1 >= n || begin2 >= n) break;
if (end2 >= n) end2 = n - 1;
int j = begin1;
int left1 = begin1, right1 = end1;
int left2 = begin2, right2 = end2;
while (left1 <= right1 && left2 <= right2)
{
if (a[left1] < a[left2]) v[j++] = a[left1++];
else v[j++] = a[left2++];
}
while (left1 <= right1) v[j++] = a[left1++];
while (left2 <= right2) v[j++] = a[left2++];
for (int k = begin1; k <= end2; k++)
{
a[k] = v[k];
}
}
gap *= 2;
}
}
EOF.
