#include<iostream>
#include<vector>
#include<math.h>
using namespace std;
class sort
{
public:
//交换两个变量的值
void swap(int &a,int &b)
{
int temp = a;
a = b;
b = temp;
}
//冒泡算法1：固定一个，让其替换为最小的值 时间复杂度O(n^2)
//稳定性：稳定
void BubbleSort0(vector<int> &L)
{
for(int i = 0; i < L.size();++i)
for(int j = i +1; j < L.size();++j)
{
if(L[i] > L[j]) swap(L[i],L[j]);
}
}
//冒泡算法2：正宗的冒泡排序算法，两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。时间复杂度O(n^2)
void BubbleSort(vector<int> &L)
{
for(int i = 1; i < L.size();++i)
for(int j = 0; j < L.size() - i;++j)
{
if(L[j] > L[j+1]) swap(L[j + 1],L[j]);
}
}
//冒泡算法3：冒泡的改进算法 ，增加FLAG标志位 时间复杂度O(n^2)，但是性能会好
void BubbleSort2(vector<int> &L)
{
for(int i = 1; i < L.size();++i)
{
bool flag = true;
for(int j = 0; j < L.size() - i;++j)
{
if(L[j] > L[j+1])
{
swap(L[j + 1],L[j]);
flag = false;
}
}
if(flag) break;
}
}
//选择排序：基本思想为一趟在n - i + 1个记录中选取关键字最小的记录作为有序的第i个记录。交换的次数少了，交换需要的时间比较大
//交换的次数少了，性能优于冒泡排序 时间复杂度O(n^2)
//稳定性：稳定
void SeleteSort(vector<int> &L)
{
for(int i = 0 ;i < L.size() ; ++i)
{
int minIndex = i;
for(int j = i + 1; j < L.size(); ++j)
{
if(L[minIndex] > L[j])
minIndex = j;
}
if(minIndex != i)
swap(L[i],L[minIndex]);
}
}
//直接插入排序：将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1的有序表。时间复杂度O(n^2)
//稳定性：稳定
void InsertSort(vector<int> &L)
{
int temp;
//有序表是一点一点增加的，刚开始只有一个元素，则循环是从元素下标1开始的
//有序表区间为[0,i - 1] j下标是要和temp替换的那个
for(int i = 1; i < L.size() ; ++i)
{
if( L[i] < L[i - 1] )
{
temp = L[i];
int j = i - 1;
while(j >= 0 && temp < L[j])
{
L[j + 1] = L[j];
--j;
}
L[j + 1] = temp;
}
}
}
//希尔排序：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，
//然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。
//因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高。
//时间复杂度：O(nlogn)~O(n^2)
//稳定性：不稳定
void ShellSort(vector<int> &L)
{
int increment = L.size();
while( increment > 1 )
{
increment = increment/3 + 1; //关于增量序列的选择，目前还是数学难题，迄今为止没有人能够找到好的增量序列
//把这个L分成increment个子序列了，下面是对每个子序列进行插入排序
for(int i = 0;i < increment; i++)
{
//每个子序列的插入排序，原理同上
for( int j = i + increment; j < L.size(); j +=increment)
{
if(L[j] < L[j - increment])
{
int temp = L[j];
int k = j - increment;
while(k >= 0 && temp < L[k])
{
L[k + increment] = L[k];
k -=increment;
}
L[k + increment] = temp;
}
}
}
}
}
//堆排序：
/* 完全二叉树：
如果从下标从1开始存储，则编号为i的结点的主要关系为：
双亲：下取整 （i/2）
左孩子：2i
右孩子：2i+1
如果从下标从0开始存储，则编号为i的结点的主要关系为：
双亲：下取整 （(i-1)/2）
左孩子：2i+1
右孩子：2i+2
堆：堆是具有特殊性质的二叉树，特殊性质指的是：
每个节点的值都大于或等于其左右孩子结点的值，称为大顶堆；
每个节点的值都小于或等于其左右孩子结点的值，成为小顶堆。
思想：1.将待排序的序列构成一个大顶堆（以大顶堆为例）；
2.将堆顶的根结点与末尾元素交换；
3.将剩下的n-1个序列重新构建成一个堆；
返回第2步循环
时间复杂度：O(nlogn)
稳定性：不稳定 */
//对每个非叶结点，需要进行调整成为堆，顺序为：从下往上，从右到左
void HeapAdjust(vector<int> &L,int s,int m)
{
int temp = L[s];
for(int j = 2 * s + 1;j <= m - 1;j = 2 * j + 1) //沿关键字较大的孩子结点向下筛选
{
if(j < m - 1 && L[j] < L[j + 1]) ++j; //j为关键字中较大的记录下标
if(temp >= L[j]) break;
L[s] = L[j];
s = j;
}
L[s] = temp;
}
void HeapSort(vector<int> &L)
{
for(int i = ceil(L.size()/2.0); i >= 0; i--)
{
HeapAdjust(L,i,L.size());
}
swap(L[0],L[L.size() - 1]);
for(int i = L.size();i > 1 ;i--)
{
HeapAdjust(L,0,i );
swap(L[0],L[i - 1]);
}
}
//归并排序 先递归的分解数列，再合并数列就完成了归并排序。
// 时间复杂度：O(nlogn)
// 稳定性：稳定，但是比较占内存，因为要递归
//归并排序递归版
//合并数组，注意下标指针，并创建一个临时数组
void Merge(vector<int> &A,int l,int mid,int r)
{
vector<int> C(r - l + 1,0);
int i = l;
int j = mid + 1;
int m = mid,n = r;
int k = 0;
while(j <= n && i <= m)
{
if(A[i] > A[j]) C[k++] = A[j++];
else C[k++] = A[i++];
}
while(i <= m)
{
C[k++] = A[i++];
}
while(j <= n)
{
C[k++] = A[j++];
}
for(int i = 0;i < k;i++)
A[l + i] = C[i];
}
//拆分与合并排序
void SplitMerge(vector<int> &D,int l,int r)
{
if(l < r)
{
int mid = (l + r) / 2;
SplitMerge(D,l,mid); //左边有序
SplitMerge(D,mid + 1,r); //右边有序
Merge(D,l,mid,r); //将左右合并为一个有序序列
}
}
void MergeSort(vector<int> &L)
{
SplitMerge(L,0,L.size() - 1);
}
//归并排序非递归版，直接写在一个函数中，
void MergeSort2(vector<int> &L)
{
int size = 1,l,mid,r; //size为间隔，l,mid,r分别为左中右指针
while(size < L.size())
{
l = 0; //左指针为0
while( l + size < L.size() )
{
mid = l + size - 1;
r = mid + size;
if( r > L.size() - 1 ) r = L.size() - 1;
Merge(L,l,mid,r);
l = r + 1;
}
size *= 2;
}
}
//快速排序：通过一趟排序将待排序记录分割成独立的两部分，其中一部分的关键字均比另一部分的关键字小，则可分别对这两部分继续进行排序，以达到整个序列有序的目的。
// 算法时间复杂度：O(nlogn)
// 稳定性：不稳定
int Partition(vector<int> &L,int l,int r)
{
int midKey = L[l];
int keyIndex = l;
while(l < r)
{
//先从右边按顺序开始找一个数比midKey小，再从左边按顺序找一个比midKey大 ,左边和右边的指针分别+1,-1
while(l < r && L[r] >= midKey) r--; //从右边开始找比midKey小的数，如果找到则退出，L【r】即为当前比midKey小的数
swap(L[l],L[r]); //交换他们的数值
keyIndex = r;
while(l < r && L[l] < midKey) l++;
swap(L[l],L[r]); //交换他们的数值
keyIndex = l;
}
return keyIndex;
}
void Qsort(vector<int> &L,int l,int r)
{
if(l < r)
{
int keyIndex = Partition(L,l,r);
Qsort(L,l,keyIndex - 1);
Qsort(L,keyIndex + 1,r);
}
}
void QuickSort(vector<int> &L)
{
Qsort(L,0,L.size() - 1);
}
//快速排序简洁版本
void quickSort(vector<int> &L,int l,int r)
{
if(l >= r) return;
int left = l;
int right = r;
int midKey = L[l];
while(left < right)
{
while(left < right && L[right] >= midKey) right--;
L[left] = L[right];
while(left < right && L[left] <= midKey) left++;
L[right] = L[left];
}
L[left] = midKey;
quickSort(L,l,left - 1);
quickSort(L,left + 1,r);
}
};
int main()
{
sort *p= new sort;
int A[10] = {6,9,5,3,8,7,1};
vector<int> L(7,0);
for(int i = 0;i < L.size();++i)
L[i] = A[i];
p->MergeSort2(L);
cout << endl;
for(int i = 0;i < L.size();++i)
cout << L[i] << " ";
delete p;
vector<int> E;
return 0;
}
