#include <iostream>
using namespace std;
/*排序过程都是直接在内存中完成，统称为内排序*/
//=======================交换排序================
/*冒泡排序:时间复杂度为O(n^2)，空间复杂度为O(1)
依次比较相邻两个元素，首先比较第1个位置和第2个位置的数，大的放后面，小的放前面，然后比较第2个位置第3个位置的数，重复进行到第n个位置，经过这一轮，数组中最大元素交换到第n个位置；
重复上一步骤，直到第n-1个位置；依次重复执行，直到第1个位置*/
void bubbleSort(int arr[], int len)
{
int temp;
for (int i = len - 1; i > 0; i--)
{
for (int j = 0; j < i; j++)
{
if (arr[j] > arr[j + 1])
{
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
/*鸡尾酒排序: 冒泡排序改进算法
双向冒泡排序*/
void cocktailSort(int arr[], int len)
{
int head = 0, tail = len - 1;
int temp, k;
while (head < tail)
{
for (k = head; k < tail; k++)
{
if (arr[k] < arr[k + 1])
{
temp = arr[k];
arr[k] = arr[k + 1];
arr[k + 1] = temp;
}
tail--;
for (k = tail; k>head;k--)
{
if (arr[k - 1]>arr[k])
{
temp = arr[k-1];
arr[k - 1] = arr[k];
arr[k] = temp;
}
}
head++;
}
}
}
/*改进冒泡排序，设置标志:
若在一轮扫描过程中没有交换元素，则表示已经排序完成，没必要继续执行*/
void bubbleFlagSort(int arr[], int len)
{
int temp, flag = 1;
for (int i = len - 1; i > 0 && flag; i--)
{
flag = 0;
for (int j = 0; j < i; i++)
{
if (arr[j] < arr[j + 1])
{
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
flag = 1;
}
}
}
}
/*快速排序：O（N*log2N）
首先数组根据中枢值分成两个部分，左边元素小于等于中枢值，右边元素都大于中枢值；然后每个部分被递归的排序。
优化：消除递归；
选择基于三中值分区的中枢值；
设定一个切分数组长度的最小值，如果小于这个值就直接使用插入排序；*/
void qSort(int* a, int left, int right)
{
if (left >= right)
return;
int zsv = a[left];//选取第一个元素为中枢值
int last = left, temp;
for (int p = left + 1; p <= right; p++)
{
if (a[p] < zsv)
{
++last;
temp = a[p];
a[p] = a[last];
a[last] = temp;
}
}
a[left] = a[last];
a[last] = zsv;
//递归
qSort(a, left, last - 1);
qSort(a, last + 1, right);
}
void quickSort(int* a, int len)
{
qSort(a, 0, len - 1);
}
//============================选择排序===================
/*选择排序：每次从未排序的序列中挑选出最大（最小）的元素，重复这个过程直到所有元素都被挑完。O(n^2)*/
void selectSort(int* a, int len)
{
int minpos, min;
for (int i = 0; i < len; i++)
{
min = a[i];
minpos = i;
for (int j = i; j < len; j++)
{
if (a[j] < min)
{
min = a[j];
minpos = j;
}
}
a[minpos] = a[i];
a[i] = min;
}
}
/*堆排序：堆实际上是一棵完全二叉树
堆的基本操作分为向上调整和向下调整，利用向上调整操作构建堆，堆顶元素和堆尾交换后，堆长度减1，
利用向下调整操作从堆顶开始调整生成新堆。*/
inline void swap(int* arr, int a, int b)
{
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
void HeapAdjust(int* L, int s, int m)//构建大顶堆
{
int temp, j;
temp = L[s];
for (j = 2 * s; j < m; j *= 2)//沿关键字较大的孩子结点向下筛选
{
if (j < m && L[j] < L[j + 1])//lchild<rchild
++j; //j为关键字中较大的记录的小标
if (temp>=L[j])//parent>=rchild
break;
L[s] = L[j];
s = j;
}
L[s] = temp;//交换parent与lchild
}
//对顺序表L进行堆排序
void HeapSort(int* L,int len)
{
int i;
for (i = len/ 2; i > 0; i--)//把L构建成一个大顶堆
HeapAdjust(L, i-1, len);
/*for (i = 0; i < len; i++)
cout << L[i] << " ";
cout << endl;*/
for (i = len-1; i > 0; i--)
{
swap(L, 0, i);//将堆顶记录和当前未经排序子序列的最后一个记录交换
HeapAdjust(L, 0, i - 1);//将L[0--i-1]重新调整为大顶堆
}
/*for (i = 0; i < len; i++)
cout << L[i] << " ";
cout << endl;*/
}
//================插入排序===============
/*插入排序：O(n^2)
将一个数组分为两个部分，前一部分为已排序，后一部分为乱序，
每次将乱序部分第一个元素插入到有序部分中，从插入点开始有序部分元素依次后移，
如此重复直至乱序元素个数为0，则完成整个排序过程。*/
void insertSort(int* arr, int len)
{
for (int i = 1; i < len; i++)
{
int pos = i - 1;
int temp = arr[i];
while (pos >= 0 && arr[pos]>temp)
{
arr[pos + 1] = arr[pos];
pos--;
}
arr[pos + 1] = temp;
}
}
/*希尔（Shell）排序 ：一种递减增量分组插入排序
将比较的全部元素分为几个区域来提升插入排序的性能*/
void ShellSort(int* arr, int len)
{
// 以 N/2^k（k从1开始）为步长，直至步长为1
for (int step = len / 2; step > 0;step/=2)
{
// 各组内简单插入排序
for (int i = step; i < len;i++)
{
int temp = arr[i];
int j = i - step;
for (; j >= 0 && arr[j]>temp; j -= step)
arr[j + step] = arr[j];
arr[j + step] = temp;
}
}
}
//=======================合并排序=====================
/*归并排序：
假设初始序列含有n个记录，则可以看成是n个有序的子序列，每个子序列的长度为1，
然后两两归并，得到[n/2]([x]表示不小于x的最小整数)个长度为2或1的有序子序列；再两两归并，.......，
如此重复，直到得到一个长度为n的有序序列为止，即2路归并排序*/
//合并两个有序部分
void mergeArray(int a[], int first, int mid, int last, int temp[]) {
if (first >= last) {
return;
}
int i = first, j = mid + 1;
int k = first;
while (i <= mid && j <= last) {
if (a[i] > a[j]) {
temp[k++] = a[j++];
}
else {
temp[k++] = a[i++];
}
}
while (i <= mid) {
temp[k++] = a[i++];
}
while (j <= last) {
temp[k++] = a[j++];
}
// 回写到原来数组中
for (k = first; k <= last; k++) {
a[k] = temp[k];
}
}
//递归调用归并
void mSort(int* a, int first, int last, int *temp) {
if (first < last) {
int mid = (first + last) >> 1;
mSort(a, first, mid, temp);
mSort(a, mid + 1, last, temp);
mergeArray(a, first, mid, last, temp);
}
}
//归并排序算法
void MergeSort(int* a, int len)
{
int* temp = new int[len];
mSort(a, 0, len - 1, temp);
delete[] temp;
}
int main()
{
int a[] = {50,10,90,30,70,40,80,60,20};
MergeSort(a, 9);
for (int i = 0; i < 9; i++)
cout << a[i] << " ";
system("pause");
return 0;
}
