各类排序分析汇总
7大排序
以下代码全部由C++实现 ， 如果没学过c++ 可以把cout看成是printf ， 是用来输出的函数
①冒泡排序
i是标记左边的数组元素的下标，标记元素A[i] ，（同理j的作用也是如此）
假设A[0]是最大的元素 ，
所以先让j从0 ~ n - 1 遍历一次 ， 如果有元素比当前的元素A[i]更小 ， 则交换A[i]与A[j]
第一遍遍历：A[0] 与 A[1]，A[2] , A[3] 。。。A[ n - 1 ] 全部比较一次
所以第一次 j 从0 ~ n- 1 遍历完时 ， 数组首元素一定是最小的==接下来假设 A[1] 是最大的元素 ， j 又从 0 ~ n - 1 遍历一次 ，
当遍历完成时 ，A[1]与A[2] , A[3] 。。。A[ n - 1 ]又再次全部都比较了一次 ，
A[1] 一定时数组里面第二大的元素， 以此类推
数组元素慢慢变得有序
#include <iostream>
using namespace std;
typedef int *Int;//自定义一种指向int数据的指针类型的别名Int
const int MAX = 50;
inline Swap(Int a , Int b)
{
int tmp = *a;
*a = *b;
*b =tmp;
}
void BubbleSort(int A[] , int n)
{
for(int i = 0 ; i < n - 1 ; i++)
{
for(int j = i + 1 ; j < n ; j++)
{
if(A[j] < A[i])
{
Swap(A + i , A + j);
}
}
}
}
int main()
{
int A[MAX];
for(int i = 0 ; i < MAX ; i++)
A[i] = MAX - i;//数组元素为100 , 99 , 98依次降序排列
BubbleSort(A , MAX);
for(int i = 0 ; i < MAX ; i++)
cout << A[i] << '\n'; // 数组元素将为 1 , 2 , 3依次升序
return 0;
}
②选择排序
算法分析:
i ， j ， k 的作用:
i : 假设当前最大元素是A[i]
j 是拿来遍历用的从 0 ~ n - 1
k是拿来标记当前最大元素的下标 ，在遍历j的过程中如果有元素A[j]比A[k]还要小 ， 那么就让
k 等于 j ， 标记当前最大元素的下标 ， 并在j的遍历结束之后检查 k 是否和 i 相等如果k == i 那么说明在j遍历过的元素中没有元素比最开始假设的A[i]小 ， A[i]仍旧是最小的，无须交换
如果 k != i 说明 j 遍历过的元素中有A[k]比A[i]更小 ， 那么此时必须要把A[i] 和 A[k]交换
这样就得到了第i大的元素
#include <iostream>
using namespace std;
typedef int *Int;//自定义一种指向int数据的指针类型的别名Int
const int MAX = 50;
inline Swap(Int a , Int b)
{
int tmp = *a;
*a = *b;
*b =tmp;
}
void SelectSort(int A[] , int n)
{
int i , j , k ;
for(i = 0 ; i < n - 1 ; i++)
{
k = i ; 假设A[i] 是第 i + 1 大的元素 ， i == 0 时 ， 假设A[0]是目前最大的元素
for(j = i + 1 ; j < n ; j++)
{
if(A[j] < A[k])
k = j ; 把最小元素的下标 j 记录到 k 中
}
if(k != i)
{ 如果 k != i 说明 j 遍历过的元素中有A[k]比A[i]更小 ，
那么此时必须要把A[i] 和 A[k]交换
Swap(A + i , A + k);
}
}
}
int main()
{
int A[MAX];
for(int i = 0 ; i < MAX ; i++)
A[i] = MAX - i;//数组元素为100 , 99 , 98依次降序排列
SelectSort(A , MAX);
for(int i = 0 ; i < MAX ; i++)
cout << A[i] << '\n'; // 数组元素将为 1 , 2 , 3依次升序
return 0;
}
③插入排序
算法分析：
插入排序相当于是打扑克牌时给扑克牌的大小进行排序(可以想象一下自己的手指等于5张牌，抽出第2张牌)
先从手中抽出第二张牌开始与前面的牌的大小进行比较 ，（tmp = A【1】）（抽牌）
如果左边的牌大于右边的牌 ， 那么就把
左边的牌往右边错位（ A【 j 】 = A【j - 1】），意思就是把左边的牌放到右边 ， 再检查下一张牌(j–)是否比手中的牌大（A【j - 1】> tmp ？， 如果还是 true ， 继续错位A【j】 = A【j - 1】，直到没有下一张牌 j - 1 >= 0 为假 ，【防止越界用的】）
如果内循环为假 ， 就要把牌插入回去 ，A【j】 = tmp ， 接着开始抽第三张牌与前面的比较 ， 每次内循环都消除一些逆序对 ，循环结束之后就没有了逆序对 ， 也就有序了 ，实现代码如下：
#include <iostream>
using namespace std;
const int MAX = 50;
void InsertSort(int A[] , int n)
{
int i , j , tmp ;
for(i = 1; i < n ; i++)
{
tmp = A[i]; // 抽牌与前面的牌比较
for(j = i ; j >= 1 && A[j - 1] >= tmp ; j--)
// 没有下一张牌 ， 或者前面的牌都比手上的牌小就会跳出内循环
{
A[j] = A[j - 1]; // 前面的牌大于手上的牌就往后错位 ， 左边牌放到右边
}
A[j] = tmp; // 把手上的牌插入回正确的位置
}
}
int main()
{
int A[MAX];
for(int i = 0 ; i < MAX ; i++)
A[i] = MAX - i;//数组元素为50 , 49 , 48依次降序排列
InsertSort(A , MAX);
for(int i = 0 ; i < MAX ; i++)
cout << A[i] << '\n'; // 数组元素将为 1 , 2 , 3依次升序
return 0;
}
④希尔排序
算法分析：
希尔排序类似于前面的插入排序
先把区间的一些用增量隔开的数进行插入排序 ，接着当增量为1时 ， 执行插入排序 ， 此时的希尔排序就变成了插入排序 ，其实就只需要把前面插入排序的代码中的 1 全部替换成为 Increment（增量）就可 以啦
具体实现代码如下
#include <iostream>
using namespace std;
const int MAX = 1e1;
void ShellSort(int A[] , int n)
{
int i , j , tmp , Increament;
for(Increament = n / 2 ; Increament > 0 ; Increament /= 2)
{
for(i = Increament ; i < n ; i++)
{
tmp = A[i];
for(j = i ; A[j - Increament] > tmp && j - Increament >= 0 ; j -= Increament)
{
A[j] = A[j - Increament];
}
A[j] = tmp;
}
}
}
int main()
{
int A[MAX];
for(int i = 0 ; i < MAX ; i++)
A[i] = MAX - i;
ShellSort(A , MAX);
for(int i = 0 ; i < MAX ; i++)
cout << A[i] << "\n";
return 0;
}
⑤堆排序
算法分析：
如果是最小堆
主要就是插入的时候父节点一定比子节点小 ，这是堆的有序性 ， 也是排序的前提
要知道以下结论:
父节点的下标为 i ， 那么左儿子的下标一定是 2 * i ， 右儿子就是 2 * i + 1
其实堆排序就是对选择排序的一种改进 ， 选择排序需要线性地寻找最小元 ， 但是堆排序因为其有序性 ， 堆顶元素就是最小值 ， 直接就找到了 ， 所以可以把堆排序看成是选择排序的改进。
堆排序原理
删除的时候就是删除最小元 ， 删除最小元的时候会不断上溯 ，维护了堆的有序性 ， 使得
删除之后就是仍然会有一个根节点是最小元 ， 然后我们可以不断的删除当前堆里面的最小元（可以写一个删除并返回最小元的函数 ， 前提是堆不能为空!） ，不断地得到当前数组里面的最小元 不断地维护堆的有序性 ， 然后输出那个返回值（如果不输出的话可以考虑存到另外一个数组里面 ， 但是就是比较费时间 ，拖慢了堆排序往堆里面删除和插入的讲解最好就是看机械工业出版社的那本
<<数据结构与算法分析 ：C语言描述>>
讲的非常的不错
时间复杂度：
O(N log N)
堆排序实现代码有点长 ， 我把它放到头文件里面了。。。。
头文件（类声明）
#ifndef HEAP_H_INCLUDED
#define HEAP_H_INCLUDED
#include<cstdlib>
typedef int *Int;
class Heap
{
private:
int Size ;
int Capacity;
Int Array ;
public:
Heap(int Capacity_) : Size(0) , Capacity(Capacity_) , Array(new int[Capacity_])
{
if(!Array)
{
FatalError("Out of space.");
}
Array[0] = -1e8;
}
~Heap(){delete[] Array;}
bool isFull();
bool isEmpty();
int DeleteMin() ;
void AddElement(int Element);
void HeapSort() ;
void Error(const char * str)
{
std::cout << str << '\n';
}
void FatalError(const char * str)
{
std::cout << str << "\n";
exit(1);
}
};
#endif // HEAP_H_INCLUDED
类实现
#ifndef IMPLEMENTS_H_INCLUDED
#define IMPLEMENTS_H_INCLUDED
#include "heap.h"
bool Heap::isFull()
{
return Size >= Capacity;
}
bool Heap::isEmpty()
{
return Size == 0;
}
void FatalError(const char * str)
{
std::cout << str << "\n";
exit(1);
}
void Error(const char * str)
{
std::cout << str << '\n';
}
int Heap::DeleteMin()
{
int Child , Parent;
int LastElement , Min_Element;
if(isEmpty())
{
Error("The heap is empty.");
return 0;
}
LastElement = Array[Size--];
Min_Element = Array[1];
for(Parent = 1 ; Parent * 2 <= Size ; Parent = Child)
{
Child = Parent * 2 ;
if(Child + 1 <= Size && Array[Child + 1] < Array[Child])
{
Child++;
}
if(LastElement < Array[Child])
{ /**Easy to be forgotten!*/
break;
}
else
{
Array[Parent] = Array[Child];
}
}
Array[Parent] = LastElement;
return Min_Element;
}
void Heap::AddElement(int Element)
{
int i ;
if(isFull())
{
FatalError("Full Heap.");
}
for(i = ++Size ; i >= 1 && Array[i/2] > Element ; i /= 2)
{ /*Decrease swap times.*/
Array[i] = Array[i/2];
}
Array[i] = Element;
}
void Heap::HeapSort()
{
while(!isEmpty())
{
std::cout << DeleteMin() << '\n';
}
}
主函数
#include <iostream>
#include"heap.h"
#include "implements.h"
using namespace std;
const int MAX = 1e5;
typedef class Heap *PtrHeap;
int main()
{
{
Heap h(MAX + 1);
for(int i = 0 ; i < MAX ; i++)
h.AddElement(MAX - i);
h.HeapSort();
}
return 0;
}
⑥归并排序(MergeSort)
算法分析：
分治算法：
这种递归的算法最开始理解的时候就是比较费劲 ， 但是我们一定要用分治的思想去理解这种算法
先假装MergeSort的具体实现代码已经实现 ， 并可以直接调用
在 Merge_Sort(int A[] , int n)里面调用如下的具体的实际函数
MergeSort( A , tmp , Left , Center) ; // 先处理左边的子数组
MergerSort(A , tmp , Center + 1 , Right); // 后处理右边的子数组
MergeSort(A , tmp , Left , Right); // 合并两个数组
通过以上代码分别处理左右的子数组
时间复杂度分析：
数组都被分成是2个子数组 ， T(N) = T(N / 2 ) + T(N / 2 ) + O(N)
接着不断递归直到不能再分 ， 因此N / 2 又被分成了N / 4 ，然后就是不断递推啦
得到T(N) = O( N log N )归排并没有最好最坏平均时间复杂度， 任何情况下都是N log N ，归并排序都是稳定的算法
编码注意：
申请堆上的数组时 ， 一定要在归排序Merge_Sort那里申请一个数组就可以了，
不要在递归的函数里面申请 ， 否则会不断的申请空间和归还空间 ， 会严重拖慢排序 ，
而且容易申请空间失败
#include <iostream>
using namespace std;
const int MAX = 1e3;
void MergeArray(int A[] , int tmpArray[] , int Lpos , int Rpos , int RightEnd)
{ // 到这里才有具体的实现细节
// Lpos是Left Position 意思是左位置，就是标记左边子数组的下标用的啦 ， Rpos也是一样的
int LeftEnd = Rpos - 1; // 得到左边子数组的最后面的下标
int TmpC = Lpos ; // 动态申请的临时数组的下标为TmpC
int NumElement = RightEnd - Lpos + 1;
while(Lpos <= LeftEnd && Rpos <= RightEnd)
{
if(A[Lpos] <= A[Rpos])
tmpArray[TmpC++] = A[Lpos++];
else
tmpArray[TmpC++] = A[Rpos++];
}
while(Lpos <= LeftEnd) tmpArray[TmpC++] = A[Lpos++];
while(Rpos <= RightEnd)tmpArray[TmpC++] = A[Rpos++];
for(int i = 0 ; i < NumElement ; i++ , RightEnd--)
{
A[RightEnd] = tmpArray[RightEnd];
}
}
void MergeSort(int A[] , int tmp[] , int Left , int Right)
{
if(Left < Right)
{
int Center = (Left + Right) / 2 ; // 假装已经处理好了所有的细节，于是开始分治（&&递归）
MergeSort(A , tmp , Left , Center); //先处理左边的子数组
MergeSort(A , tmp , Center + 1 , Right);// 后处理右边的子数组
MergeArray(A , tmp , Left , Center + 1 , Right);// 合并两个数组
}
}
void Merge_Sort(int A[] , int n)
{
int * tmp = new int[n];
if(tmp != nullptr)
{
MergeSort(A , tmp , 0 , n - 1);
delete[] tmp;
}
}
int main()
{
int A[MAX];
for(int i = 0 ; i < MAX ; i++)
A[i] = MAX - i;//数组元素为100 , 99 , 98依次降序排列
Merge_Sort(A , MAX);
for(int i = 0 ; i < MAX ; i++)
cout << A[i] << '\n'; // 数组元素将为 1 , 2 , 3依次升序
return 0;
}
⑦快速排序（高度优化的快排）
算法分析：
快排比其他算法快的根本原因：
枢纽元在i 和 j 的遍历后被放到了最正确的位置 ， 左边所有元素都比枢纽元小
右边所有元素都比枢纽元大， 这是快排比其他排序更快的原因
因为枢纽元被一次性放到了最合适的位置 ，从此之后不需要再交换位置
但是其他的算法都可能需要不断的改变位置
时间复杂度：
跟前面的归并排序类似 ， 也是不断的把数组分为2个子数组 ， 所以也是O(N log N )
#include <iostream>
using namespace std;
const int CUTOFF = 3;
const int MAX = 1e2;
inline void Swap(int *a , int *b)
{
int tmp = *a;
*a = *b;
*b =tmp;
}
/**插入排序*/
void InsertSort(int A[] , int n)
{
int i , j , tmp;
for(i = 1 ; i < n ; i ++)
{
tmp = A[i];
for(j = i ; j >= 1 && A[j - 1] >= tmp ; j--)
{
A[j] = A[j - 1];
}
A[j] = tmp;
}
}
/**三数中值分割，哎，其实就是头中尾三个地方取中位数 ， 并把枢纽元藏在Right - 1这个位置
并且返回枢纽元的值*/
int Medium3(int A[] , int Left , int Right)
{
int Center = (Right + Left) / 2 ;
if(A[Left] > A[Center]) Swap(A + Left , A + Center);
if(A[Left] > A[Right] ) Swap(A + Left , A + Right );
if(A[Center] > A[Right]) Swap(A + Center, A + Right );
Swap(A + Center , A + Right - 1);
return A[Right - 1];
}
/**高度优化的快排*/
void QuickSort(int A[] , int Left , int Right)
{ /**只有当前的数组长度大于等于3时才能用中位数分割 ，否则就用插入排序*/
if(Left + CUTOFF <= Right)
{
int Privot = Medium3(A , Left , Right);
int i = Left ;
int j = Right - 1;
while(true)
{
while(A[++i] < Privot){} //如果小于枢纽元就迅速过，直到找到比枢纽元大的
while(A[--j] > Privot){} //j 是从Right - 2 的位置开始遍历 ，Right - 1的位置是枢纽元的
if(i < j) // 如果i 和 j 还没交错 ， 就直接交换
Swap(A + i , A + j);
else
break;
}
Swap(A + i , A + Right - 1); // 把枢纽元和刚刚开始交错的位置 i 交换位置 ，
// 此时枢纽元被放到了最正确的位置 ， 左边所有元素都比枢纽元小
// 右边所有元素都比枢纽元大， 这是快排比其他排序更快的原因
// 因为枢纽元被一次性放到了最合适的位置 ，从此之后不需要再交换位置
// 但是其他的算法都可能需要不断的改变位置
QuickSort(A , Left , i); /**分治 ， 分左边和右边分别处理*/
QuickSort(A , i + 1 , Right);
}
else
InsertSort(A + Left , Right - Left + 1);
}
void Quick_Sort(int A[] , int n)
{
QuickSort(A , 0 , n - 1);
}
int main()
{
int A[MAX];
for(int i = 0 ; i < MAX ; i++)
A[i] = MAX - i;//数组元素为100 , 99 , 98依次降序排列
Quick_Sort(A , MAX);
for(int i = 0 ; i < MAX ; i++)
cout << A[i] << '\n'; // 数组元素将为 1 , 2 , 3依次升序
return 0;
}
写在最后
CSDN的博客不太会格式，有的地方看起来会比较奇怪，如有问题可以在评论留言，我会更正的