#include <iostream>
#include <stack>
using namespace std;
class Sort
{
private:
int a[10];
public:
void setA();
void getA();
//冒泡排序
void bubble_sort();
//冒泡递归
void bubble_rec(int length);
//快速排序递归算法
void quick_sort(int low,int high);
int partition(int low,int high);
//快速排序非递归
void quick_unrec(int left, int right);
int quick_partition(int left, int right);
//堆排序非递归
void buildMaxHeap(int len);
void adjustDown(int k,int len);
void heapSort(int len);
//堆的递归算法
void heapSort_rec(int length);
void heap_adjust(int index, int length);
};
void Sort::heapSort(int len)
{
int t;
buildMaxHeap(len);
for(int i=len-1;i>0;i--)
{
t=a[i];
a[i]=a[0];
a[0]=t;
adjustDown(0,i-1);
}
}
void Sort::buildMaxHeap(int len)
{
for(int i=len/2-1;i>0;i--)
{
adjustDown(i,len-1);
}
}
void Sort::adjustDown(int k,int len)
{
int t=a[k];
for(int i=2*k+1;i<=len;i*=2+1)
{
if(i<len&&a[i]<a[i+1])
{
i++;
}
if(t>=a[i]) break;
else
{
a[k]=a[i];
k=i;
}
}
a[k]=t;
}
void Sort::setA()
{
int i;
for(i=0;i<10;i++)
{
cin>>a[i];
}
}
void Sort::getA()
{
for(int i=0;i<10;i++)
cout<<a[i]<<" ";
cout<<endl;
}
void Sort::bubble_sort()
{
int t;
for(int i=0;i<9;i++)
{
for(int j=0;j<9-i;j++)
{
if(a[j]>a[j+1])
{
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
}
}
}
//冒泡排序递归
void Sort::bubble_rec(int length)
{
if (length <= 1)
return;
int num = length;
for (int i = 0; i < length - 1; ++i)
{
if (a[i] > a[i + 1])
{
swap(a[i], a[i + 1]);
}
}
bubble_rec(--length);
}
//快速排序递归
void Sort::quick_sort(int low,int high)
{
if(low<high)
{
int pivotpos = partition(low,high);
quick_sort(low,pivotpos-1);
quick_sort(pivotpos+1,high);
}
}
int Sort::partition(int low,int high){
int pivot = a[low];
while(low<high){
while(low<high&&a[high]>=pivot) --high;
a[low]=a[high];
while(low<high&&a[low]<=pivot) ++low;
a[high]=a[low];
}
a[low]=pivot;
return low;
}
//快排非递归算法
void Sort::quick_unrec(int left, int right)
{
stack<int> t;
if(left<right)
{
int p = partition(left, right);
if (p-1>left)
{
t.push(left);
t.push(p-1);
}
if (p+1<right)
{
t.push(p+1);
t.push(right);
}
while(!t.empty())
{
int r = t.top();
t.pop();
int l = t.top();
t.pop();
p = partition(l, r);
if (p-1>l)
{
t.push(l);
t.push(p-1);
}
if (p+1<r)
{
t.push(p+1);
t.push(r);
}
}
}
}
int Sort::quick_partition(int left, int right)
{
double x = a[right];
int i = left-1, j = right;
for (;;)
{
while(a[++i] < x) { }
while(a[--j] > x) { if(j==left) break;}
if(i < j)
swap(a[i], a[j]);
else break;
}
swap(a[i],a[right]);
return i;
}
//堆排序递归算法
void Sort::heapSort_rec(int length)
{
int i = 0;
if (NULL == a || 0 == length)
{
return;
}
//构造大顶堆
for (i = length / 2 - 1; i >= 0; i--)
{
heap_adjust(i, length);
}
//从最后一个元素开始对数组进行调整，不断缩小调整的范围直到第一个元素
for (i = length - 1; i > 0; i--)
{
//交换第一个元素和当前的最后一个元素，保证当前的最后一个元素在当前数组中是最大的
swap(a[0], a[i]);
//调整完后的第一个元素是当前数组的最大元素
heap_adjust(0, i);
}
}
void Sort::heap_adjust(int index, int length)
{
int child;
int temp = a[index];
if (2 * index + 1 >= length)
{
return;
}
//子结点位置 = 2 * 父结点位置 + 1
child = 2 * index + 1;
//得到子结点中较大的结点
if (child < length - 1 && a[child + 1] > a[child])
{
++child;
}
//如果较大的子结点大于父结点那么把较大的子结点往上移动，替换它的父结点
if (temp < a[child])
{
a[index] = a[child];
}
else
{
return;
}
//最后把需要调整的元素值放到合适的位置
a[child] = temp;
heap_adjust(child, length);
}
int main()
{
Sort s;
cout<<"请输入10数字的待排序列：";
s.setA();
s.bubble_sort();
// s.quick_sort(0,9);
// s.heapSort(10);
// s.quick_unrec(0,9);
// s.heapSort_rec(10);
// s.bubble_rec(10);
cout<<"排序结果为：";
s.getA();
return 0;
}
