排序大法
1、基本概念
- 排序,就是重新排列表中的元素,使得表中的元素按照关键字有序的过程。
- 算法稳定性:如果两个元素关键字相同,排完序后在表中位置先后顺序和排序前一样,则称其排序为稳定的。
2、分类
内部排序
-
-
直接插入排序
时间复杂度:最好:,最坏:,平均:
空间复杂度:
稳定排序,适用线性表和链式表
-
折半插入排序
时间复杂度:最坏:,平均:
空间复杂度:
稳定排序
-
希尔排序
时间复杂度:最坏:,平均:(现代数学没法证明)
空间复杂度:
不稳定排序,只适用于线性表
-
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
for(int d = nums.size() / 2; d >= 1 ; d/=2){
for(int m = 0; m < d; m++){
for(int i = m+d; i < nums.size(); i+=d){
int j = i-d;
int temp = nums[i];
for(; j >= 0 && nums[j] > temp;j-=d){
nums[j+d]= nums[j];
}
nums[j+d] = temp;
}
}
}
return nums;
}
};
-
-
冒泡排序
时间复杂度:最好:,最坏:,平均:
空间复杂度:
稳定排序:适用于线性表和链式表
-
快速排序
时间复杂度:最坏:,平均:
空间复杂度:最好:,最坏:,平均:
不稳定排序
-
-
class Solution {
public:
int quick(vector<int> &nums, int left, int right){
swap(nums[left], nums[rand()%(right-left+1)+left]);
int pivot = nums[left];
while(left < right){
while(left <right && nums[right] > pivot) right--;
nums[left] = nums[right];
if(left < right && nums[left] == pivot) left++;
while(left < right && nums[left] < pivot) left++;
nums[right] = nums[left];
if(left < right && nums[right] == pivot) right--;
}
nums[left] = pivot;
return left;
}
void quickSort(vector<int> &nums,int left, int right){
if(left < right){
int mid = quick(nums, left, right);
quickSort(nums, left , mid-1);
quickSort(nums, mid+1, right);
}
}
vector<int> sortArray(vector<int>& nums) {
quickSort(nums, 0, nums.size()-1);
return nums;
}
};
- 选择排序
-
简单选择排序
时间复杂度:
空间复杂度:
不稳定排序:很明显没有元素的移动,那么交换很有可能导致后面的元素交换到前面来了
-
堆排序
时间复杂度:,其中建堆的时间复杂度为
空间复杂度:
不稳定排序:选择排序都不是稳定的,因为没有整体后移
-
class Solution {
public:
void buildMaxHeap(vector<int> &nums){
for(int i = nums.size() /2-1; i>=0;i--)
maxHeapify(nums, i, nums.size()-1);
}
void maxHeapify(vector<int> &nums, int root, int right){
int rval = nums[root];
for(int i = 2*root+1; i <= right; root = i,i = 2*root+1){
if(i < right && nums[i] < nums[i+1]) i++;
if(rval >= nums[i]) break;
nums[root] = nums[i];
}
nums[root] = rval;
}
vector<int> sortArray(vector<int>& nums) {
buildMaxHeap(nums);
for(int i = nums.size()-1; i > 0; i--){
swap(nums[0], nums[i]);
maxHeapify(nums, 0,i-1);
}
return nums;
}
};
-
时间复杂度:
空间复杂度:
稳定排序
class Solution {
public:
vector<int> space;
void merge(vector<int> &nums, int left,int mid, int right){
for(int i = left; i<= right;i++) space[i] = nums[i];
int l = left, r = mid+1, i = left;
while(l <= mid && r <= right){
if(space[r] < space[l]) nums[i++] = space[r++];
else nums[i++] = space[l++];
}
while(l <= mid) nums[i++] = space[l++];
while(r <= right) nums[i++] = space[r++];
}
void mergeSort(vector<int> &nums,int left, int right){
if(left < right){
int mid = (left + right)/2;
mergeSort(nums, left, mid);
mergeSort(nums, mid+1, right);
merge(nums, left, mid, right);
}
}
vector<int> sortArray(vector<int>& nums) {
space.resize(nums.size());
mergeSort(nums, 0, nums.size()-1);
return nums;
}
};
-
时间复杂度:
空间复杂度:
稳定排序
外部排序
常用的是归并排序的方法,并且不仅仅是二路归并,常用的是多路归并。
败者树
- 作用:优化多个归并段在内存中的比较次数
- 设归并路数为k,归并趟数为S,每趟归并的元素有n个(每次输出到磁盘中),总共有r个归并段,计算
- 使用败者树后,内部比较次数与归并路数k无关了,所以可以增加归并路数k
- 但是,如果归并路数k太大,那么由于内存不够,会导致缓冲区数量减少,最终还是会影响比较次数
置换-选择排序
- 作用:用于生成更长的归并段,以缩小归并段的数量
最佳归并树
-
作用:将若干的归并段生成读写次数最少的归并树,使用哈夫曼树
-
步骤:设为度为0节点个数,也就是归并段的数量。k为归并路数
1、如果,正好可以构成k叉归并树,直接使用构造哈夫曼树的方法构造即可
2、如果,则再加上
k-u-1
个空的虚拟归并段进行构造哈夫曼树