//快排
//思想联系
//冒泡每次只交换相邻元素，只可以消除一个逆序
//如果可以交换不相邻元素，可以一次消除多个逆序

include[HTML_REMOVED]

using namespace std;

int dividen(int data[],int low,int high){//传来的都是检查过的，是合法的
data[0]=data[low];//暂时存储，这里low就看做逻辑空了
while(low[HTML_REMOVED]=data[0]&&low[HTML_REMOVED]=high) return;//每次进入不会检查low和high合法，其中一个元素也直接退出
int mid=dividen(data,low,high);
quicksort(data,low,mid-1);
quicksort(data,mid+1,high);
}

int main()
{
int data[]={100,1,3,5,7,9,2,4,6,8,0};
for(int i=1;i<=10;i)
cout<<data[i]<<’ ‘;
quicksort(data,1,10);
cout<<endl;
for(int i=1;i<=10;i)
cout<<data[i]<<’ ‘;
}

//分析
//最好情况，每次都能一分为二（和归并分析一样了，但是归并元素均是叶子，快排枢轴元素
// 可以作为分支结点）
// 结合递归树，每层都会遍历一遍元素n,层数取决于树高，最好logn，总nlogn
//最坏情况，有序，那么每次划分都是一边空，一边n-1，树高n，复杂度n²
//空间复杂度，递归工作栈，根据树高 logn，n

//不稳定
//这里每次都可以确定枢轴元素的最终位置
//适合随机乱序，n很大情况

//这里用了随机存储，链表应该是不可以的