基础排序算法总结 + 代码实现总结
目录
快速排序的基本实现
快速排序算法
是一种基于交换的高效的排序算法，它采用了分治法的思想：
1、从数列中取出一个数作为基准数（枢轴，pivot）。
2、将数组进行划分(partition)，将比基准数大的元素都移至枢轴右边，将小于等于基准数的元素都移至枢轴左边。
3、再对左右的子区间重复第二步的划分操作，直至每个子区间只有一个元素。
快排最重要的一步就是划分了。划分的过程用通俗的语言讲就是“挖坑”和“填坑”。
快速排序时间复杂度
快速排序的时间复杂度在最坏情况下是O(N2)，平均的时间复杂度是O(N*lgN)。
这句话很好理解：假设被排序的数列中有N个数。遍历一次的时间复杂度是O(N)，需要遍历多少次呢？至少lg(N+1)次，最多N次。
(01) 为什么最少是lg(N+1)次？快速排序是采用的分治法进行遍历的，我们将它看作一棵二叉树，它需要遍历的次数就是二叉树的深度，而根据完全二叉树的定义，它的深度至少是lg(N+1)。
因此，快速排序的遍历次数最少是lg(N+1)次。
(02) 为什么最多是N次？这个应该非常简单，还是将快速排序看作一棵二叉树，它的深度最大是N。因此，快读排序的遍历次数最多是N次。
快速排序稳定性
快速排序是不稳定的算法，它不满足稳定算法的定义。
算法稳定性 -- 假设在数列中存在a[i]=a[j]，若在排序之前，a[i]在a[j]前面；并且排序之后，a[i]仍然在a[j]前面。则这个排序算法是稳定的！
总结
1. Quick Sort 更快
2. 而且是就地排序，空间复杂度为O(1)，
3. 是递归算法，在不希望使用递归时，Quick Sort 又不是好的选择了。
4. Quick Sort并不是稳定的算法。原先的次序会被打乱。
5. 虽然完全逆序的情况下，快速排序会降到选择排序的速度，不过从概率角度来说（参考信息学理论，和概率学），不对算法做编程上优化时，快速排序的平均速度比堆排序要快一些。
6.面试官还会问到同样的nlogn算法，你是会使用快速排序，还是使用Merge Sort：
一般来讲，Quick Sort的速度还是要快一点，而且Merge Sort 还会使用额外的空间。另外就是MergeSort是稳定的排序。而快速排序是不稳定的。
代码实现思路：（其实我觉得挺容易写错的）
图文参考这个博客，很清晰：https://blog.****.net/nrsc272420199/article/details/82587933
int partition(int nums[], int left, int right){
int pivot = nums[left];
// 注意这里从left开始
int low = left, high = right;
while(low < high){
// 注意下面low < high的判断
while(low < high && nums[high] >= pivot) high--;
nums[low++] = nums[high];
while(low < high && nums[low] <= pivot) low++;
nums[high--] = nums[low];
}
// low的位置放High，high的位置放low，最后low的位置放high
nums[low] = pivot;
return low;
}
void quickSort(int nums[], int left, int right){
if(left > right) return;
int j = partition(nums,left,right);
// 对左右递归
quickSort(nums,left,j-1);
quickSort(nums,j+1,right);
}
int main(){
int nums[5] = {3,4,2,7,1};
quickSort(nums,0,4);
for(auto &i:nums) cout << i << endl;
}
归并排序
归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
总结：
归并排序是稳定排序，它也是一种十分高效的排序，能利用完全二叉树特性的排序一般性能都不会太差。java中Arrays.sort()采用了一种名为TimSort的排序算法，就是归并排序的优化版本。
时间复杂度
每次合并操作的平均时间复杂度为O(n)，而完全二叉树的深度为|log2n|。总的平均时间复杂度为O(nlogn)。而且，归并排序的最好，最坏，平均时间复杂度均为O(nlogn)。
空间复杂度：O(n)
归并排序主要分为两部分：
1、划分子区间
2、合并子区间
现在以 9,6,7,22,20,33,16,20 为例讲解上面两个过程：
第一步，划分子区间：每次递归的从中间把数据划分为左区间和右区间。原始区间为[start,end],start=0,end=[length-1],减一是因为数组的下标从0开始,本例中length=8,end=7.现在从中间元素划分，划分之后的左右区间分别为 [start,(end-start+1)/2+start],右区间为[(end-start+1)/2+start+1,end],本例中把start和end带入可以得到[0,7]，划分后的左右子区间为[0,4],[5,7],然后分别对[start,end]=[0,4]和[start,end]=[5,7]重复上一步过程，直到每个子区间只有一个或者两个元素。整个分解过程为:
子区间划分好以后，分别对左右子区间进行排序，排好序之后，在递归的把左右子区间进行合并，整个过程如下图所示：
void merge(int *nums,int left,int right,int *result){
int left_end = (left+right)/2;
int right_end = right;
int res_idx = left;
right = left_end+1;
//对分别已经排好序的左区间和右区间进行合并,放入result中
while(left <= left_end && right <= right_end){
if(nums[left] <= nums[right]){
result[res_idx++] = nums[left++];
}else{
result[res_idx++] = nums[right++];
}
}
while(left <= left_end) result[res_idx++] = nums[left++];
while(right <= right_end) result[res_idx++] = nums[right++];
}
void merge_sort(int *nums,int left,int right,int *result){
if(left == right) return;
if(left + 1 == right){
if(nums[left] > nums[right]) swap(nums[left],nums[right]);
return;
}
// 分治
merge_sort(nums, left, (left+right)/2,result);
merge_sort(nums, (left+right)/2+1,right,result);
merge(nums,left,right,result);
for(int i = left;i <= right;i++) nums[i] = result[i];
}
int main(){
int nums[8] = {9,6,7,22,20,33,16,20};
const auto length = 8;
int result[length];
merge_sort(nums,0,7,result);
for(auto &i:nums) cout << i << endl;
}在递归的把左右子区间进行合并，整个过程如下图所示：
堆排序
堆
堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。如下图：
同时，我们对堆中的结点按层进行编号，将这种逻辑结构映射到数组中就是下面这个样子
该数组从逻辑上讲就是一个堆结构，我们用简单的公式来描述一下堆的定义就是：
大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]
堆排序
基本思想：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了