案例1（以后再看，对堆排序了解不足） 已知一个几乎有序的数组，几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离不超过k，并且k相对于数组长度来说很小。问选什么方法对其排序比较好。 分析：时间复杂度从小到大分析 复杂度O(N)的排序算法： 计数排序、基数排序 不基于比较的排序算法的限制： 不适用所有情况
复杂度O(N^2)的排序算法： 冒泡排序、选择排序 这两个排序算法与数据原始序列无关，时间复杂度严格符合O(N^2)
插入排序 插入排序的过程与原始顺序有关 每个元素移动距离不超过k 对本题来说，插入排序O(N*k)
复杂度O(N*logN)的排序算法： 快速排序 与数据原始序列无关
归并排序 与数据原始序列无关
这题答案:改进后的推排序 每个元素移动距离不超过k 所以最小值位置 堆顶是最小值，放在数组首位。 数组加入一个数，插入堆顶。 递归完成，数组排序完毕。 每调整一个数O(logK),总共N个数 总的为O(N*logK)
案例2（以后再看，对堆排序了解不足） 判断数组中是否有重复值。必须保证额外空间复杂度为O(1)。 分析：若无空间复杂度限制，用哈希表实现。哈希表实现，时间复杂度为O(N),空间复杂度为O(N)。
若有限制，先排序，再判断。所以此题是考察经典算法的空间复杂度限制。
选择堆排序 推排序经典实现使用了递归的方式（函数栈），但这样，其空间复杂度为O(logN) 所以答案需要改写出一个非递归的排序。
案例3 把两个有序数组合并为一个数组。第一个数组空间正好可以容纳两个数组的元素。 A：2 4 6 空 空 空 B：1 3 5 6和5比，6大，6放最后； 4和5比，5大，5放倒数第二个位置 依次。 直到完成排序。 该题核心：从后向前覆盖数组A，保证数组A有用信息不会被覆盖掉
#include<iostream> #include<vector> using namespace std; void out(vector<int> arr,int n){ //数组输出 for(int k=0;k<n;k++){ cout<<"arr["<<k<<"]:"<<arr[k]<<endl; } } void sort(vector<int> &arr, int length,vector<int> &arr2, int length2){ for(int l=1;l<=length2;l++){//数组增大 arr.push_back(0); } int k=length+length2-1;//总长度 int i=length-1; //arr长度 int j=length2-1; //arr2长度 while(i>=0&&j>=0){ if(arr[i]>= arr2[j]){ arr[k] = arr[i]; i--; k--; } else{ arr[k] = arr2[j]; j--; k--; } } while(i>=0){ //若arr还没扫描完，将其全部复制到合并序列 arr[k] = arr[i]; i--; k--; } while(j>=0){ //若arr2还没扫描完，将其全部复制到合并序列 arr[k]=arr2[j]; j--; k--; } } int main(){ int num; vector<int>arr; cout<<"请输入第一个数组"<<endl; int n = 0;//n表示输入个数 while (cin >> num){ arr.push_back(num); n++; if(cin.get() == '\n') //遇到回车，终止 break; } int num2; vector<int>arr2; cout<<"请输入第二个数组"<<endl; int n2 = 0;//n2表示输入个数 while (cin >> num2){ arr2.push_back(num2); n2++; if(cin.get() == '\n') //遇到回车，终止 break; } sort(arr,n,arr2,n2); //排序 out(arr,n+n2); //输出数组 }代码注：方法源自《排序(1)》中的归并排序。
